問題リンク Quest of Merchant 解法 市場から街をぐるっと巡って帰ってくるので、1回目の仕入れと2回目の仕入れは互いに影響しません。よってDPの形にできそうだと考えました。 dp[T]: 残り時間Tを使って得られる最大利益 1回の仕入れで同じ街に2回訪れるの…

問題リンク Rectangular Stamps 解法 幅優先探索で解きました。 スタンプを押す順番をそのまま考えると状態数がえらいことになりますが、押す順番の逆を考えると状態数が減ります。各マスに対して、まだスタンプを押していない場所をビットで覚えておきます…

問題リンク Starting Line 解法 シミュレーションのような感じで解きました。 人参に関して言えることは、 加速状態にない場合、すぐ食べたほうが良い。既に加速状態の場合、人参は所持したほうが良い。ただし、人参が既にK本ある場合はその場で食べたほうが…

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

問題リンク The Enemy of My Enemy is My Friend 解法 探索+枝刈りで解きました。 まず、国に番号付けをします。自国が0なら他の国はどんな番号でもいいです。 次に、i番の国に隣接している国をビットマスクの形で保持します。これをadj[i]とします。 更に s…

問題リンク Janken 解法 すっげぇ強い手の集合を作って、その中から適当に出せば350点くらい稼げるだろう、というのが方針です。 強い手の集合は次のようにして作ってみました集合のどれかの手を使えば、全ての手に対して負けない(あいこか勝ちになる) 上を…

問題リンク Power 解法 貪欲法で解けます。 現在カバーできている部屋の右端をfとしたとき、 a を満たす教授の中で、f なお、最初はどの部屋もカバーしていないので、fの初期値は0とします。 最終的にf ソース

問題リンク Social 解法 b[i] にi番のうさぎが何番のボートに乗っているかを格納します。 うさぎpとqが仲が悪いとき、b[p] == b[q]となっていたら、これらのうさぎは気分を悪くします。 ソース

問題リンク Simple Othello 解法 両端の駒の状態だけ見て、O(1)で判定できます。 結論から言うと、両端がともにxのときだけxが勝ち、それ以外はoが勝ちます。 両端がoとxのとき、先攻はx側に駒を置いて両端がoになります。xはどちらに駒を置いても、次のター…

問題リンク Al dente 解法 1番目の砂時計から順番に[T-E, T+E]の区間のどこかを図れるかを調べます。 T+Eが3000弱なので単純なループでも余裕ですが、 T-E となるような最小のkを k = (T-E-1)/x + 1 として求めて、 T-E となっているかを調べるとO(1)でチェ…

問題リンク Programming Contest Challenge Book 解法 探索+枝刈りが方針です。 3本の棒A, B, C (A A+B の三角不等式を満たすかを調べればOKです。 色々ノートで思考していると、1個目の三角形で使う棒を決めると、2個目の三角形で周辺の和が最大になるよう…

問題リンク Bara-Bara Manju 解法 深さ優先探索+枝刈りが方針です。 何をどう深さ優先探索したのかという話になりますが、ずばり、「10の作り方」です。 10を和で表現する方法は調べてみると41通りあります。この10の作り方それぞれに番号を振り、k番の10の…

問題リンク Filling Game 解法 深さ優先探索+枝刈りで解きました。 まず、最初から隣接している同色のパネルはくっつけてグループにしておきます。そして、グループ間の隣接リストを作っておきます。 1度くっついたグループは以降離れることはないので、bool…

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

問題リンク Time Sale 解法 メモ化再帰で解くのが方針です。 dp[ i ][ j ][ S ]: 商品の状態がSで(i, j)にいるための最小時間 という表を埋めて解きます。Sは、手に取った商品の番号のビットが立っているような整数です。 この問題の厄介な部分は、移動しな…

問題リンク Hot Spring Trip 解法 頂点を少し拡張してダイクストラするのが方針です。頂点を 0: まだ無料の権利を使っていない 1: 無料の権利を使い始めた 2: 無料の権利を使い終わった という状態に拡張します。 状態0からは0か1 状態1からは2 状態2からは2…

問題リンク Input Candidates 解法 出現単語ごとに登場回数をカウントし、最後に登場回数、辞書式の順でソートすればOKです ソース

問題リンク Quaternion Multiplication 解法 (x1 + y1*i + z1*j + w1*k) * (x2 + y2*i + z2*j + w2*k) を頑張って展開すると (x1*x2 - y1*y2 - z1*z2 - w1*w2) +(x1*y2 + y1*x2 + z1*w2 - w1*z2)i +(x1*z2 - y1*w2 + z1*x2 + w1*y2)j +(x1*w2 + y1*z2 - z1*y…

問題リンク Interest Rates 解法 単利と複利の場合の計算方法があるので計算し、最大値をとる銀行を求めるだけです ソース

問題リンク Calorie Counting 解法 p[i] を満たすお菓子が食べてよいお菓子です ソース

問題リンク Time to Study 解法 区間[s, f)はどれも重ならないので勉強時間はf-sの総和になります ソース