問題リンク 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となります。計算時間の心配は要りませ…