問題概要 カレンダーを1日進めるか1ヶ月進めるか選ぶことができる。ふたりで交互に手を選んだとき、自分の番で特定の日付に遷移できるかどうか判定する問題。 解法 基本的には典型的なゲーム木探索。日付の存在判定なんかは適当に頑張る。サイズが小さいので…

問題概要 ビット列->数字の変換テーブルが与えられるので、それにしたがってビット列を変換する問題。

問題概要 数字のペアの列(長さN 解説 某所で日本語解説を見てしまっていたので殆ど自分で考えずに解いてしまった。 Dilworthの定理より、最小パス被覆を求める代わりに最大反鎖のサイズを求める。これはペアをソートした後第二要素の最長狭義減少列を求めれ…

問題概要 いわゆる連鎖行列積。復元もあり。 解法 [from, to)型のDPの典型例。

問題概要 ある数aがb個ある。それぞれの数を分割する作業を繰り替えした結果が与えられる。aとして考えられる最小値を求める問題。 解法 探索で頑張る。 長い順に調べた方が枝刈りしやすそうであることは直感的に分かる。 最初は、長い順に元はどの木片であ…

問題概要 1*1, 2*2, ..., 6*6の板を6*6マスの盤に埋め込む。盤は最小いくつ必要か求める問題。 解法 だいたい直感通りに貪欲に詰めていく。こういうのは場合分けを減らしたいんだけど難しい。

問題概要 ふたつの数A,B(A BからA^k(k>0)を引く。 BをB%Aで置き換える。 のいずれかの操作を施す。どちらかが0の状態で自分の番になったら負ける。勝つのが先手か後手か判定する問題。A,B 解法 (B%A, A)が負けの状態であるとき、その状態に遷移できるので(A,…

問題概要 よく分からない。 解法 状態がN^3程度に収まるように注意しながらDPする。

結果。 1/5完。Aは読んでない。Bは問題文がよく分からなかったので適当にエスパーしながら通した。Cは、まあ実験ゲーだよなあと思いながら実験コードを書いて結果をじっと眺める。周期があるような気がしたけどTLE&WAなコードしか仕上げられなかった。 CodeF…

問題概要 K個のポストがある。ポストを壊すのに爆弾が最低いくつ必要かをしりたい。最低爆弾をいくつ用意する必要があるか求める問題。 解法 状態を(残りポスト、下限、上限)としてDP。

問題概要 8円のコーラをN( 解法 動的計画法。dp[i本買った][残り1円][残り5円][残り10円]=最小枚数とすると状態数が多くてTLEしそう。残り硬貨の枚数を全部覚えておく必要はなくて、2種類について枚数が分かれば残りの枚数は引き算で求められる。これで状態…

問題概要 N

問題概要 キング+上下に動くようなクイーンに対して、Nクイーンが何通りあるか求める問題。いくつかのクイーンは配置が指定されている。 解法 ごくごく素直なDPだとO(N^3)。?のとき全部に配るのを止めて、全体に配って近くだけ差っ引くというやりかたをすれ…

問題概要 LIS。N 解法 練習のつもりでO(N*log N)解を書く。入力の変換が最も面倒。

問題概要 整数の集合A,B(濃度はいずれも100以下)がある。A、Bからいくつかの要素を除いて、Bの任意の要素がAのどの要素の倍数にもなっていないようにしたい。最小でいくつ取り除く必要があるか求める問題。 解法 二部グラフを構成すると、求めるものは最小点…

問題概要 人がN( 考えたこと 速い順にソートする。1番速い人と2番目に速い人の位置とライトの位置とそれ以外の人が何人残っているか、という4つの組を状態としてメモ化再帰する。3番目以降の人の動かし方は、遅い方から動かしていけば良い。

問題概要 Crossing Riverの類題

問題概要 ノード数N( 解法 ICPCの国内予選に出たAnd Then. How Many Are There?に似てる。ビットDPするだけ。

問題概要 長さL( 解法 strとrev(str)のLCSを計算する。LCSに含まれない部分だけを追加すればよい。LCSの復元の方法はちゃんと文字が一致するかどうか確かめないと駄目。

問題概要 前進、後進、回転の操作列を適切に並び替えて原点からの距離を最大化する問題。 解法 前進、後進は全部まとめた方が良い。後は回転をその間にどう挟むか。つくれる角度は超簡単なDPで計算しておく。

問題概要 あなたは原点にいて4近傍のどれかに移動できる。いくつか点があって全ての点を1度以上尋ねて最後はどれかの点で終わるようなパスを考える。そのパスの経路長が指定された偶奇にできるかどうか判定する問題。 解法 最後の点をどれにするかでパリティ…

結果。 2完。easyは、見た瞬間「何これ超簡単じゃん」と思って、「%2を探すゲーになるなあ」とか思いながらサクッと書いた。mediumは久しぶりの幾何で、解法はちょっと考えたら正しそうなのが思い浮かんで証明せずに突っ込んだ。提出した後easyを見直したら…

問題概要 長さN( 各項に決まった値がxorされる。 値にある置換が施される。 のどちらかの操作が行われる。K( 解法 xorとかはビット毎にばらしてやれば良い。後は確率のDPをやればよい。「確率で」やると考えた方が分かりやすく、本当は同じことをしているは…

難易度見積りを完全に読み間違えてご迷惑をおかけしました。問題はAizu Online Judgeの2350~2361に収録されているので解いてもらえると嬉しいです。 ジャッジデータはここでダウンロードできます。不備が見つかった場合は指摘していただけると助かります。 …

問題概要 A*p + B*q (p, q ≧ 0)の集合をX*p + Y*qが含むようにしたい。そのようなA,B,X( 解法 XがA,Bの約数なら無数に存在する。それ以外の時、X*p+Y*qによってA、Bが少なくとも作れなければならない。また、A、BがつくれたらA*p + B*qは自然に作ることがで…

結果。 275が割と早めに解けたおかげで500に時間をかけられた。500はDPを確率ベースで考えたらわかりやすかったのに期待値ベースで考えて混乱してしまった。残り時間が少なくなって適当にコードをいじっていたらサンプル全部通ったのでダメモトで提出してい…

問題概要 N( 解法 部分和問題のNが大きい番。半分全列挙は使えないが、値が小さいのでDPで作ることのできる部分和を全て求める。

問題概要 モールス信号を使った簡単な暗号をデコードする問題。 解法 ルールに従って実装するだけ。

問題概要 長さL[i]の棒がN( 解法 長さの順にソートしておいて、短い2辺を全探索する。三角形が作れないような第3辺がいくつあるかは二分探索で求めることができる。

問題概要 置換σ(N 解法 各iについて、何乗したら戻ってくるかを求めてそれの最小公倍数が答えになる。