問題概要 カードがN( 後から考えたこと この問題は本番中解けなかったので、大体の解法(メモ化のキーをどうするか)を知った後で解きなおした。 本番中は、状態が(メモリの値, どのカードを使ったか)だと全然間に合わないとか考えていた記憶がある。 改めて考…

問題概要 W*H(W,H

問題概要 N*M(N,M必用なターン数の期待値を求める問題。 考えたこと これN*M以外の値関係あるのか？長方形に配置とか問題設定上意味ない様な気がするんだけど…。 N*Mがあまり大きな素数を含まないとかが効いてくるのかなあ？ 細かいことを気にせず普通に解き…

以下の内容は間違いを含んでる可能性が高い。 状態数が少ない問題ではDPやメモ化再帰による解法が結構あるけど、少し整理してみよう。 まず、大前提としてDPやメモ化再帰が使える必要条件はDAGになっていることだろう。ここで考えているグラフは、各状態を頂…

問題概要 リンゴが落ちるゲーム(リンゴの個数=N( 考えたこと 各板は独立に考えてよい。 板の長さは大したことないので、1ずつ動かす方針でやろう(O(N*M*LENGTH))。 これ計算量下げることもできる(O(N*M))だろうけど、植木算っぽくなって確実にバグ埋め込むの…

やっぱり花形のalgorithmで赤くなりたい。

前回書いた記事の続きというか補足というか。 何かまた思いついたら追加で書くかもしれない。 具体的な補足と反省 候補文字列列挙のやり方 ここはかなりクリティカルに効いてくる部分だと思う。そしてこの部分のやり方はあまり賢くなかった。特に、エラー率…

結果が出たら追記する予定 解法 重要なのは2ヶ所だけ。落穂拾いも大事だけど。 基本線略はBFS+枝刈り。 探索を真面目にやると状態数が爆発するので、(圧縮率)*(正しい割合)をキーにして、大きい順にいくつか調べた。 候補となる文字列の列挙 何番目のスロッ…

問題概要 黒か白の帽子を被ったものがN( 解法1 出てくる数字が何種類あるか場合分けして、正当性をチェックして合っているかどうかを判定する。 解法2 場合分けとかミスの可能性が増えるだけなので、多少計算量が悪くなっても時間内に動くなら一緒だよ、とい…

keyword BruteForce C++ 問題概要 N*M(N,M 解法 まず、不可能な場合は王子と姫が隣接しているとき。それ以外の時、最大でも4つ置けばよいことがわかる（4近傍を全て潰す）。なので、0,1,2,3について調べればよい。3箇所の選び方はたかだか(N*M)^3程度しかな…

問題概要 二次元の整数テーブルが与えられる。同じ行、列からはひとつずつしかとらない、という制約の元でできるだけ多くマスを選ぶ。どのように選んでもマスに書かれた数字の和が等しくなるかどうか判定する問題。 解法 テーブルが正方形の時はPOJで解いた…

keyword 最大公約数 動的計画法 C++ 問題概要 整数列X(X[i] 解法 M=1のときは1。それ以外の時、まずgcd(X)を求めて全てXで割る。このとき、1が含まれていたら答えは1で、それ以外の時、SをXの部分集合とするとgcd(S)=1となる最小の濃度が答えになりそう（ax …

keyword BruteForce C++ 問題概要 いくつかボタンが壊れたリモコンがある。そのリモコンの壊れてないボタンとinc, decを最低何度押したら目的の値を出せるか求める問題。 解法 探す値が大きくないので全探索する。

問題概要 ノード数N( 解法 問題が分かってしまえば、O(N*N)のメモ化解法が素直に実装できる。強連結成分分解も必要そうだけど実はいらない。この問題では、ノード数が2500以下というのを50以下と勘違いしたせいでTLEやら範囲外アクセスやらで落ちまくった。

keyword 動的計画法 C++ 問題概要 バナナがK[i]本A[i]円(K[i], A[i] 解法 典型的DP。計算量O(M*N^2)(M=Aの長さ)。

keyword 連立一次方程式 期待値 C++ 問題概要 N*M(N,M 解法 蟻本に載ってるランダムウォークの問題とほとんど同じ。ゴールが複数あるという違いくらいしかない。

keyword 最小支配集合 C++ 問題概要 ノード数12+12以下の2部グラフが与えられる。最小支配集合を求める問題。ただし孤立点がある場合を除く。 解法 各ノードに対して、そのノードが支配するノードをビットで持っておく。後は2^24通り全探索するだけ。2部グラ…

問題概要 小数点3桁目以降が切り捨てられた小数が与えられる。考えられる分母の最小数を求める問題。 解法 まず、1000が上限であることが分かる。なので、あとは分母を全探索する。分母を決めれば、分子は[1..分母]まで全部試して、入力を全部カバーするかど…

keyword 動的計画法 C++ 問題概要 N*M(N,M 解法 dp[N][M][K] = (N,M,Kのときの答え)とする。このとき、最も右側の列に注目すると、最も右側にルークが0,1,2個配置されてる場合が考えられるので、それをすべて足し合わせればよい。 感想 結構シンプルに書けた…

keyword 探索 C++ 問題概要 N( 解法 桁数は増えないので到達可能な数はMAX_N以下。また、各数から到達可能な数の列挙はO((log N)^2)でできる。なのでDFSなりBFSなりで全ての到達可能なノードを調べられるので、最大のものを返せばよい。 感想 再帰関数でDFS…

keyword greedy C++ 問題概要 月/日または日/月の形で日付が複数与えられる。昇順になるような辞書順最低の日付を月/日のフォーマットで出力する問題。 解法 辞書順最小、と聞いたらまず貪欲を考える。前のものより大きく、有効な日付であるかどうかが前提条…