問題リンク ICPC Ranking 解法 Comparableなクラスを作成して、ソートかけると楽そうでした ソース

問題リンク Integral Rectangles 解法 大小関係を比較する関数1個作っておくと楽でした。 解の範囲が明確なので、1 ソース

問題リンク ICPC: Intelligent Congruent Partition of Chocolate 解法 チョコレートの総数をNとします。チョコのグループをAとBと呼びます。Aのチョコレートに所属するチョコをN/2個決めたら、AとBのチョコレートがそれぞれ連結しているか調べて解とします…

問題リンク Dr. Podboq or: How We Became Asymmetric 解法 入力文字列を構文解析して木を作ってから、木の根から順番に題意を満たすように子を入れ替えて行きます。 木には次の情報を持たせておきます。 rep: このノードを根とする木の文字列表現 sub: この…

問題リンク Chain-Confined Path 解法 ダイクストラで解きました。 頂点は両端の円の中心と、円の交点たちです。 面倒なのが、点Pと点Qの線分全体が円の内部にあるかという判定です。 図を見ると、円の内部を通るような線分は、2つの交点の間を通っています…

問題リンク Nets of Dice 概要 5*5の大きさのサイコロの展開図が与えられる。0はサイコロの面でなく、1〜6なら目の面である。次の3つの条件を全て満たすとき、サイコロの正しい展開図とする。 1〜6の面が1回ずつ登場する 組み立てた時に立方体の形になる、更…

問題リンク Railway Connection 解法 利用する路線会社を1つに限定して、全駅間の最短距離をまず求めます。距離が求まったら料金の計算ができます。すると全ての路線会社を利用する場合の全駅間の最小賃金が求まるので、最小賃金を辺のコストにしたグラフで…

問題リンク Biased Dice 解法 サイコロのシミュレート問題です。 h[i][j]: 座標(i, j)に積み重なっているサイコロの数 state[i][j]: 座標(i, j)の一番上にあるサイコロの上の面の数字 これらの状態を管理すればデータは十分です。サイコロの動かし方はライブ…

問題リンク Recurring Decimals 解法 a_iからa_(i+1)を同じ整数が得られるまで続けます。 a_iからa_(i+1)を得る手順は 1. 文字列S = a_iとします 2. |S| 3. Sを文字列配列cにしてソートする 4. cを先頭から読むと最大値、後ろから読むと最小値 5. a_(i+1)が…

問題リンク Millennium 解法 1000年1月1日になるまで1日ずつ動かすことで解けます。 サンプルの1番目が最悪のケースでその答えは約20万です。テストケースは100個までしかないので最悪計算回数は2*10^5 * 10^2 = 2*10^7となります。計算時間の心配は要りませ…

問題リンク Missing Numbers 概要 (p+1)行(s+1)列からなる売上表がある。各行のs+1列目はその行の売上合計、各列のp+1行目はその列の売上合計を表す。 売上表の一部が欠損しており復元したい。復元の仕方がただ1通りに求まるならば復元し、復元方法が複数あ…

問題リンク 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 解法 交換するカードを全通り試します。 ソース

問題リンク 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つがあると思います。自分のソースは後者で判定しています。 ソ…