問題リンク Cards 解法 青のカードと赤のカードを2部グラフにした時の最大マッチング数が求めるべき答えとなります。 ソース

問題リンク Discrete Speed 解法 (都市、進入時の速度)のノードのダイクストラで解けます。 出だしと、ゴール時の速度が1だという点に注意しましょう。 ソース

問題リンク Verbal Arithmetic 解法 全探索＋枝刈りです。 数字の割り当て方が10!あるので枝刈りしないと少々厳しいと思います。 まず、0-leadingになるような割り当ては刈れます。 N-1番目の式について、1の位から見ていき、0〜N-2の和の結果sumと見比べな…

問題リンク How Many Islands? 解法 ストレートな塗りつぶし問題です。 探索の基本練習に持ってこいかもしれません。 ソース

問題リンク Next Mayor 解法 そのままシミュレートするだけです。 ソース

問題リンク Roll-A-Big-Ball 解法 幾何問題です。 N個のブロックについて通過できる最大の半径rを求めます。これらrの最小値が即ちボールの取りうる半径の最大となります。ただし、コースの線分がブロックの内部にあるもしくは交差していたらボールの半径は0…

問題リンク Twirling Robot 解法 (現在位置、向き)をノードにしたダイクストラで解きます。 向きをベクトルの形にすることで複雑なif文の羅列を避けることができます。 ソース

問題リンク How can I satisfy thee? Let me count the ways... 解法 構文解析です。 (P, Q, R)に割り当てる値を{0, 1, 2}全て試すので3^3=27回構文解析します。 ソース

問題リンク Monday-Saturday Prime Factors 解法 素数の列挙と同様に月曜土曜素数を列挙するだけです。 ソース

問題リンク Equal Total Scores 解法 交換するカードを全通り試します。 ソース

問題リンク Poor Mail Forwarding 解法 シミュレーション問題です。 郵便局iから宛先jの手紙を出すときの転送先の郵便局は常に同じなので、前計算してしまいましょう。 e[i][j]でi->jの最短経路。ワーシャルフロイドで求めます。 adj[i][j]でi->jの直接転送…

問題リンク Dragon Fantasy 解法 全探索＋枝刈りです。訪れた状態と最後に訪れた場所の対をノードにした幅優先だと、状態数が2^N*Nになってメモリが足りません。 探索の枝刈りの条件として、未訪問の場所のうち、1つでも訪れることができなくなった場所があ…

問題リンク Make Purse Light 解法 店員がお釣りを返す部分は貪欲法で硬貨の枚数を計算できます。 硬貨の種類が4枚で各々高々20枚までしかないので、20^4通りの支払い方を試しました。 ソース

問題リンク Keitai Message 解法 文字の表を作ってしまえば勝ちです。 ソース

問題リンク Water Pipe Construction 解法 全点間の最短距離をワーシャルフロイドで求めます。 次に基地kを選び、wf[s][k]+wf[k][g1]+wf[k][g2]が最小となるkを探します。このkはs, g1, g2になっても何ら構わないです。 ソース

問題リンク Data Center on Fire 解法 エレベータのシミュレーション問題です。 まずはエレベータクラスの説明をします。 エレベータは[エレベータの識別ID, 容量, 停止時間, 現在のデバイス量, *状態*, 目標階, 現在位置の高さ, 速さ]のメンバを持ちます。 …

問題リンク Railroad Conflict 解法 新路線と既存路線の交点を全て求め、新路線のどちらか片側の端点に近くなる順番でソートします。新路線のその端点から、交点を辿っていって出口の数をカウントします。端点は地上と地下どちらでもよいので、一番最初の交…

問題リンク X-Ray Screening System 解法 r[i][4]: i番目の品物が出現した座標の範囲 を作りました。以降、品物iが長方形の形をしているかどうかの判定はこの範囲内のみを調べればよいことになります。 品物は最大で7個、なので品物の上下関係を7!通り試しま…

問題リンク Amida, the City of Miracle 解法 あみだくじのシミュレーションです。 r[h][p]: 縦棒pにいるときに高さhに差し掛かった時の移動先の棒 というデータ構造を作り、hを上から下まで動かしました。 ソース

問題リンク Misterious Gems 解法 20*20の座標をロボットを1歩ずつ動かしてシミュレーションします。 得られた宝石の数を調べてYES, NOの判定をします。 ソース

問題リンク 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種類の運用方法で得られるお金を全部計算して最大値を出すだけです。 ソース