mini notes

競技プログラミングの解法メモを残していきます。

ARC008 C - THE☆たこ焼き祭り2012

問題:C - THE☆たこ焼き祭り2012

解答:Submission #13652774 - AtCoder Regular Contest 008

解法:投げ手をi、受け手をjとすると、iは自分が投げれる最も速い速度でかつjが受け取れる最も投げれる速い速度で投げればよいので、投げるスピードはmin(t[i], r[j])となる。よって各投げ手、受け手(i, j)の組み合わせごとに上記速度をコストとする辺を張り、ダイクストラ法で0からの到達コストをまず求める。

次に考えるべき点として、たこ焼きは同時に投げるのでなく1つずつ投げる。これは遠い順に投げるのが最適らしい。(要証明)
注意点として、投げる対象から0は除かなくてはならない(ここに気づかず3WA…)