C - Cell Inversion 解法 各マスの操作のされ方は、 自分より左のマスとペアになって、1つの反転操作区間の終点になる 自分より右のマスとペアになって、1つの反転操作区間の始点になる のどちらかです。そして各マスがそのどちらになるかは、実は端から順番…

お題箱より。 A - YahooYahooYahoo 解法 「編集距離DP」を知ろう まずは「編集距離DP」なるものを説明します。2つの文字列 の編集距離とは、文字列 に以下の操作を好きな順序で行って文字列 に一致させるための、操作回数の最小値です。 置換： の任意の1文…

お題箱より。 D - Digits Parade 「与えられた条件に従って各桁の数字を決められる」「出来上がる整数のうち、余りが特定の条件を満たすものを数える」という、是非とも押さえておきたい問題パターンの入門としてぴったりです。いつも以上に丁寧めに書きたい…

F - Coincidence 解法 考察も実装もそこそこ重い問題です。順に考えていきましょう。 記法について 剰余演算を記号 、XOR演算を記号 で表すことにします。 またこの記事では数え上げの対象である2数のペアを ではなく の順番で記載しています。 ビットだけの…

お題箱より。 H - Union Sets 「公式解説で省略されている並列二分探索について知りたい」というリクエストだったのですが、私も実装したことがなかったので調べて書いてみました。私にとっても勉強になりました。 参考資料 参考にしました。 Parallel Binar…

D - Gathering Children 私の解法をTwitterに流したらわりと好評だったので記事にまとめておきます。 解法 ある程度動きをシミュレーションしてみると、十分に時間が経った後は全ての子供が RL の2マスで振動するということが分かります。最終状態を求めるた…

F - Enclosed Points 解説 数え上げの軸を変える 個の部分集合それぞれについて、その集合に対応する長方形に 個の点のうちいくつ含まれるかを考え、それを全て合計したものを求めよ。 という問題です。部分集合の数が多すぎますね。まともに列挙するのは到…

お題箱より。 B - Sum of Three Integers 計算量の考え方に入門するのにとてもいい問題です。 解法について知りたい…というリクエストだったので、色々な計算量で解く方法を解説してみました。 解法 全ての基本、全探索です。 を満たす を全て試します。和が…

お題箱より。 Aizu Online Judge Arena 解法 答えとなる金額の払い方の必要条件を考える ある金額 について貪欲な払い方よりも真に枚数が少ない払い方が存在することを、単に「金額 は条件を満たす」と書くことにします。そして条件を満たす最小の金額（答え…