かわらさんがものすごく星をつけてくださるので、自分もお世話になったブログには星を飛ばしていくことにしよう
AOJ 1149 ケーキカット
http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=1149&lang=ja
テストケースを見てAC。いや気づけるかよ
あるピースがいつ切って手に入ったものかと縦の長さと横の長ささえ記憶しておけばケーキを適切に切ることができる。ソート部分はうまくCompare関数を定義して頑張る。sはケーキの周囲を1周以上する！ 注意！！！
こういう行間をエスパーする能力は競技プログラミング力に含まれますか……？
AOJ 1248 The Balance
http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=1248
今年のICPC国内予選Cに似てる気がする。天秤に乗せることで表現する重りのパターンは（片側Aと量るもの、もう片側Bだけ）、（片側Aだけ、もう片側Bと量るもの）、（片側AとB、もう片側量るものだけ）の3ケースだけ。前半2つについてはテキトーなところで計算を打ち切りつつ片側固定して全探索（ユークリッド互除法で上界が分かりそう）し、最後のひとつはループ回数に気をつけつつやはり全探索で解ける。最後の解の出し方、重要なことが書いてあるのでちゃんと"Output"を読むこと。
テキトーに読み飛ばした英語が実は重要だったケース。
AOJ 2021 お姫様の危機
http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=2021
若干バグって時間を溶かしたが自力。300にしては難しい。
残量と場所を添え字として dp[i][j]=場所iで残量jとなるための最短時間 というdpテーブルのようなものを置き、ダイクストラやdfsを使って解く。自分は冷却施設とスタートとゴール以外を考えなくても良いようにワーシャルフロイドで縮約したがしなくても解けるかもしれない。縮約した場合は嬉しいことにその街で冷却できない可能性について考えなくても良くなるので少し嬉しい。したがってdfsも冷却時間が持つ状態の中で最も時間が短くなるものを引き出してくればよくなり、再帰回数が大幅に減らせる。縮約しなかった場合はO(N4)くらい？ 縮約するとO(N3+M2)くらいになるかな？
こういう問題すき。今日はこの問題が解きたかった。
AOJ 2005 Water Pipe Construction
http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=2005
これも多分典型。
「2つのルートを辿るとき2つのルートで使う道のコストの和を最小化してください」という問題では全点間最短路を求めたあと共通部分を全探索が鉄板。
以前yukicoderで解いた問題なのに忘れていた。以下その問題。
