J: Spin Doctor
問題
n人の個人情報が与えられる。i番目の人の情報は
- a_i : 覚えている円周率の桁数 0 ~ 2000000
- b_i : 髪の毛の本数 0 ~ 2000000
- c_i : 候補者Xに投票したかどうか 0/1
実数のパラメータS, Tを適切に決めて人々を (a_i * S + b_i * T) の値でソートし、その順番で c_i == 1の人がなるべく集まるようにしなさい。
ACM-ICPC World Finals 2016 I解法
I: Road Times
問題
n 頂点 m 辺の有向グラフが与えられる。
各辺は距離[km]が与えられる。
あなたが頂点uからvへ移動するときには、必ず距離が最短に成るように移動する。
各辺は速度が定数で制限されており、それは時速30km以上60km以下の実数の定数で、あなたはその辺を通るときはちょうどその速度で移動する(要はx[km]の辺はx~2x[min.]の実数の定数時間が掛かる)。
その速度の定数は分からないが、情報としてr個のヒント(出発点、到達点、時間[min.])が与えられる。
q個の質問:「頂点sからdに移動するときに掛かる、最短時間と最長時間を出力」に答えよ。
ACM-ICPC World Finals 2016 G解法
G: Oil
問題
地面水平方向x軸。垂直方向下向y軸。y=0が地表の2次元座標上の問題。
油井は地中にあり、地表と水平な線分で表される。
n個の油井のいち情報が与えられる。
地表から1本の直線状に任意の角度でドリルで掘って、接するか交差した油井の油を得ることができる。
油井の量はその長さに比例する。
ドリルで掘る位置・角度を適切に求め油量の最大値を出力せよ。
題意は図を見れば一発なので。
ACM-ICPC World Finals 2016 F解法
F: Longest Rivers
問題
n+m+1頂点、葉がn個の重み付き根付き木が与えられる。
各葉は川の源流で、川は辺にそって根の方向に続く。すべての辺はただ一つの川に属する。
(辺をn個の川に分割する、一つの川はつながって枝分かれしない。合流した川はいずれか一つの川の名前を持って根に向かって伸びる。)
どの辺がどの川に属するかはわからない。
長い川のランキングを作るとき、各葉から伸びる川は最良で何位になるか求めよ。
同じ長さに成る時は任意の順番で良い。
ACM-ICPC World Finals 2016 E解法
E: Forever Young
問題
私はY歳です。
適切なBを求めて、「YをB進数で表した時全ての桁は0~9であり、その表示を十進数とみなすとL以上である」ようにしなさい。
その最大のBを出力しなさい。
ACM-ICPC World Finals 2016 D解法
D: Clock Breaking
問題
7セグデジタル時計がある。4桁とコロンの2セルの計30箇所のセグの表示がある。
この時計は壊れている可能性があり、各セグは
- 正しく動作する
- 常に0を表示する
- 常に1を表示する
のどれかである。
