コンテストページ
AtCoder Regular Contest 008 - AtCoder
解法
✔A - たこ焼き買えるかな？
丁度買う場合と多めに買う場合を両方試して、安い方を採用です。
✔B - 謎のたこ焼きおじさん
2 つの文字列それぞれについて、各文字種の登場回数をカウントして切り上げ除算です。
✔C - THE☆たこ焼き祭り2012
これ好きです。各参加者さんについて、その方に最速であつあつのたこ焼きをお届けするお時間を計算です。
実は、これを 1 秒ずつずらひて遠い順に実行していくだけで、途中でたこ焼きが渋滞することはありません。 なぜなら、各中継さんと各たこ焼きについて、そのたこ焼きは最速タイムでその中継ポイントを通過します。したがって、高橋くんが投げてからその中継者さんに届くまでのラグはたこ焼きの個性に依存しません。
気がつくと当たり前に思えてしまいますが、思いつかないとなかなかむずかしそうです。
お手つき
1000 頂点で Floyd -- Warshall をして TLE をしました。初心者さんですか！？！？
✔D - タコヤキオイシクナール
有名問題です。一次関数の合成をセグツリーに乗せましょう。
結果
なんと、本番 2 位相当です！ 惜しかったです……
