C - THE☆たこ焼き祭り2012 Editorial by maspy
まず,次を無視して解きます.
参加者はつまようじを 1 人につき 1 本しか持っていないので同じタイミングで複数のたこ焼きを投げることはできず、たこ焼きを投げてから 1 秒間は次のたこ焼きを投げることができません。
これを無視すると,各時刻に「あなた」が投げたたこ焼きの動きを,たこ焼きごとに独立に考えることができるようになります.
\(i\) から \(j\) にたこ焼きを \(t\) 秒かけて渡せるとき,\(i\) から \(j\) にコスト \(t\) の有向辺を張ったグラフを考え,始点から各頂点への最短路を求めておきます.これは dijkstra 法で \(O(N^2\log N)\) 時間や \(O(N^2)\) 時間でできます.
上記の前提のもとでは各参加者に対して最短経路長に等しい時間でたこを渡せるので,問題は次のようになります:
- \((t_1, \ldots, t_N)\) が与えられる.これらを並べ替えて,\(\max_i (t_i + i)\) を最小化せよ.
これは,\(t\) を降順ソートすることで最適化できます.
次を思い出します.
参加者はつまようじを 1 人につき 1 本しか持っていないので同じタイミングで複数のたこ焼きを投げることはできず、たこ焼きを投げてから 1 秒間は次のたこ焼きを投げることができません。
実は, これを考慮しても最適解は変化しません.つまり,次の戦略は「1秒ルール」に違反しないことが証明できます.
- 時刻 \(i\) にたこ焼きを動かし始め,最短経路のひとつに沿って人 \(i\) まで届ける.
このことは,次の事実から分かります:
- 頂点 \(i\) まで最短経路で移動するとき,経路上の頂点 \(j\) を通る時刻は \(j\) までの最短経路長に等しい.
(そうでないとすると容易に矛盾が得られます.)
このことより,人 \(j\) がたこ焼きを受け取る時刻は,どのたこ焼きについても移動開始から \(t_j\) 経った時点であることが分かります.どの 2 つのたこ焼きについても移動開始時刻が 1 秒間以上離れているならば,どの人が受け取る 2 つのタコ焼きについても受け取る時刻は 1 秒間離れていることになります.
posted:
last update: