ARC#008 問題C

「問題Cの解説をもっと詳しく書いてほしい」という要望が多かったので、詳しめに書きます。

問題文： http://arc008.contest.atcoder.jp/tasks/arc008_3

STEP 1
まず、それぞれの参加者について、自分が食べるたこ焼きが投げられてからそれを受け取るまでにかかる最短時間を求めます。求め方として、ダイクストラ法というものを使います。ダイクストラ法は始点から各点までの最短経路を求めるアルゴリズムですが、各点を参加者として、各辺の長さを「その二人の間の距離/投げる側の投げる速さの上限と受ける方の受ける速さの上限の小さい方」とすることで、ダイクストラ法を用いて最短時間を求めることができます。
http://ja.wikipedia.org/wiki/%E3%83%80%E3%82%A4%E3%82%AF%E3%82%B9%E3%83%88%E3%83%A9%E6%B3%95
http://www.deqnotes.net/acmicpc/dijkstra/

かかる最短時間を配列tに入れます。最初は、たこ焼きを投げる人についてt=0、参加者についてt=∞を入れておきます。そして、すでにその人について最短時間が求まったかどうかをflagで管理します。最初は全ての人についてflag=falseです。
そして、「最短時間がまだ求まっていない人、すなわち、flag=falseとなっている人の中でtの値が最小の人(この人をAとする)について、全ての人に対してAからその人に投げた時にその人が受け取る時間を計算し、その結果がその人についてのtの値よりも小さい場合はtをその値に更新する」という操作を参加者の人数の回数だけ繰り返します。
これでそれぞれの参加者について、自分が食べるたこ焼きが投げられてからそれを受け取るまでにかかる最短時間を求めることができます。

このC問題において、全ての参加者にたこ焼きを投げてから最短時間でたこ焼きを届けることができます。言い換えると、全ての参加者に最短時間でたこ焼きを届けようとすると途中で中継する参加者が1秒以内に2個以上のたこ焼きを投げなければならないので不可能である、となる可能性は無いということです。何故ならば、最短時間で参加者にたこ焼きを投げる時、各中継者にも最短時間でたこ焼きが届くはずであり、同じ中継者に届く2個のたこ焼きがa秒の間を空けて最初に投げる人に投げられた場合、そのたこ焼きは必ず中継者にa秒の間を空けて届くはずだからです。したがって、全ての参加者にたこ焼きを投げてから最短時間でたこ焼きを届けることが可能なのです。

STEP 2
STEP1で、各参加者について自分が食べるたこ焼きが投げられてからそれを受け取るまでにかかる最短時間を求めました。しかし、これは最初にたこ焼きが投げられてから各参加者が受け取るまでの時間ではありません。何故ならば、「投げる人はたこ焼きを投げてから1秒間は次のたこ焼きを投げてはいけない」という制約があるからです。
ある参加者について、自分の食べるたこ焼きが投げられてから受け取るまでの最短時間をt、そして、自分のたこ焼きが最初のたこ焼きが投げられてからi番目に投げられた時、最初のたこ焼きが投げられてから自分のたこ焼きが投げられるまでの時間はi-1であり、最初のたこ焼きが投げられてから自分がたこ焼きを受け取るまでの時間はi+t-1です。したがって、全ての参加者についてのi+t+1の値の最大値がたこ焼きを配り終えるまでにかかる時間となるわけです。
i番目に自分のたこ焼きが投げられた人のtの値をt_iとします。たこ焼きを配り終えるまでにかかる時間が最小となるようにたこ焼きを配った時に、k番目の人が最後にたこ焼きを受け取る場合、t_k+k-1の値がたこ焼きを配り終えるまでにかかる時間となります。
ここで、t_kは全てのtのうちk番目に大きな値であるということを示します。

すべてのmより大きなkについて、t_k>t_mとなる。(kt_k+k-1となり、k番目の人よりも後にたこ焼きを受け取る人が存在することになるので矛盾。)
すべてのmより小さなkについて、t_kmについて、t_k>t_mとなるようなmが存在すると仮定すると、k番目とm番目の人のたこ焼きを投げる順序を入れ替えると、t_k+m-1
以上より、t_m>t_kとなるmの個数はちょうどk-1個あることがわかるので、t_kは全てのtのうちk番目に大きな値であることがわかる。

ここで、全てのa,bについて、at_bとなるように投げる。そうすると、全てのiについて、i番目の人のtの値t_iはすべての参加者のtの中でi番目に大きな値となります。したがって、kの値がわかっていなくても、t_kの値をk番目に大きな値とすることができます。すなわち、
投げてから受け取るまでの時間のかかる人から順に優先的に配達する
ようにすればいいのです。

注意
自分にたこ焼きを投げないように注意。STEP1では最初に投げる人を考慮しますが、STEP2では除かなければいけません。

2
0 0 100 100
1 0 100 100

正
0.01

誤
1.00

各問題の解答ソースコード例
http://asi1024.hatenablog.com/entry/2012/09/22/220805

質問等あれば何でもコメントorリプライ下さい。

(o_o)

ブログ。

ARC#008 問題C