問題リンク Name the Crossing 解法 「通りの名前」を頂点にしたグラフを作って解いていきます。 まず、XとYが違う方向の通りかを判定するためのグラフを作ります。これは色塗り問題と考えることができます。同じ色で塗られていたらそれは同じ方向です。ただ…

問題リンク Cliff Climbing 解法 最短経路問題です。「座標(i, j)、どちらの足を掛けてそこへ到着したか」の対をノードにしたダイクストラで解けます。足を掛けた方とは逆の足を次のステップで動かします。右足、左足で行くことができる位置は移動ベクトルに…

問題リンク Cut the Cakes 解法 シミュレーション問題です。ケーキはクラスにしておくと楽になると思います。 ケーキをカットする位置を求め、それがケーキのどこの辺かで場合分けすると処理が書きやすいです。また、sはケーキの周長よりも長いこともあるの…

問題リンク Analyzing Login/Logout Records 解法 ある学生のログイン時間さえ分かればいいのでコンピュータを区別する必要はないです。 時間の範囲が狭いので、ログインしているかいないかの時間の配列を作ればいいと思います。 ソース

問題リンク ICPC Score Totalizer Software 解法 最高点と最低点を除いて平均を出すだけです。 ソース

問題リンク Cleaning Robot 解法 巡回セールスマン問題と考えて解くのがたぶん想定解だと思います。けれど、ごり押しでも通せます。 訪れる頂点間の最短距離をBFSで前計算しておき、訪れる順番を全通り試します。O(10!)くらいになるのですが、何とかなります…

問題リンク Traveling by Stagecoach 解法 最短経路問題です。(町、残っている馬車券)をノードにしたダイクストラで解けます。 ソース

問題リンク Numeral System 解法 MCXI→整数、整数→MCXIに変換するメソッドを作ってしまえば勝ちです。 ソース

問題リンク Polygonal Line Search 解法 図形の合同判定問題です。 座標を回転させて、オリジナルのものと一致するか判定する方法と、曲がった方向と進んだ長さの列が一致するか判定する方法の2つがあると思います。自分のソースは後者で判定しています。 ソ…

問題リンク Ohgas' Fortune 解法 N種類の運用方法で得られるお金を全部計算して最大値を出すだけです。 ソース