ARMERIA

Rubyと競技プログラミングの話 AtCoderやCodeforcesの問題解説記事が多め。

ABC122 D - We Like AGC

D - We Like AGC

解法

問題文の条件を満たすためには、具体的にどのような部分文字列が含まれていてはダメでしょうか。NGパターンを列挙してみましょう。

  • 3文字のNGパターン
    • もちろん AGC はNGです。また、隣り合う2文字を入れ替えて AGC となる GACACG もNGです。3文字のNGパターンはこれで全部です。
  • 4文字のNGパターン
    • X を任意の文字として AXGC はNGパターンです。最初の2文字を入れ替えると AGC ができてしまうからです。同様の理由で AGXC もNGです。4文字のNGパターンはこれで全部です。

列挙してみると意外と少ないことが分かります。また5文字以上のNGパターンはありません。「隣り合う2文字の入れ替えを高々1回行って、連続する3文字の並びを見る」という操作に関係する文字は、必ず連続する4文字以内に収まっているからです。

ということで、連続する4文字の並びを確認すればNGパターンかどうかが判定できることが分かりました。これを言い換えると

文字列の末尾に新しく1つ文字を足した時にNGパターンが新しく発生しないかどうかは、直近の3文字だけを見れば判定できる

ということになります。この考え方を元にDPを構成することが出来ます。

具体的には、

  •  dp\lbrack i \rbrack\lbrack a \rbrack\lbrack b \rbrack\lbrack c \rbrack =  i 文字までの文字を決めていて、最近の3文字が左から  a, b, c となっていて、NGパターンを含んでいない文字列の場合の数

という状態を持ってDPすることができます。 a, b, c はそれぞれ文字 TAGC のどれかだと思ってください(後で実装について補足します)。

 dp\lbrack i \rbrack\lbrack a \rbrack\lbrack b \rbrack\lbrack c \rbrack からの遷移を考えます。この文字列に文字  d を足した時に新しく発生するNGパターンは、先ほど列挙した通り

  • 3文字のNGパターン
    • 文字列  bcd が、AGC GAC ACG のどれか
  • 4文字のNGパターン
    • 文字列  abcd が、X を任意の文字として AXGC AGXC のどちらか

です。これらNGパターンのどれにも当てはまらなければ、 dp\lbrack i+1 \rbrack\lbrack b \rbrack\lbrack c \rbrack\lbrack d \rbrack に遷移することが出来ます。

このDPを全部計算して、最後に  dp\lbrack N \rbrack\lbrack a \rbrack\lbrack b \rbrack\lbrack c \rbrack を全ての  a, b, c について合計したものが答えとなります。

ACコード&実装の補足

Submission #4700029 - AtCoder Beginner Contest 122

実装について少し補足します。まず先ほどの説明では文字をDPテーブルの添字として扱っていましたが、実装においては 0123 といった整数に対応させましょう。私のコードでは添字の 0123 が順に TAGC に対応しています。

次に初期状態について。DPの初期条件を考える時、初期状態(空文字列)には「直近の3文字」がないので少し困ります。今回の場合は「NGパターンに関して意味を持たないような文字」、つまり T が存在すると見なしてしまって良いです。先ほど T は添字 0 に対応させていたので、初期条件を dp[0][0][0][0] = 1 としています。

最後に関数 add(a, b) について。私のコードでは「変数 a に変数 b の値を足してMODを取る」という処理を add(a, b) にやらせています。a = (a+b) % MOD と同等の機能です。

yukicoder No.803 Very Limited Xor Subset

No.803 Very Limited Xor Subset - yukicoder

解法

AtCoderに「Limited Xor Subset」という問題があります。この問題の想定解法は今回のyukicoderの問題とは全く違うものですが、この問題に対するこちらの別解がとても参考になります。私もコンテスト本番はこの記事を見て解法を編み出しました。

Code Thanks Festival 2017 F Limited Xor Subset 解説 | 東京工業大学デジタル創作同好会traP

ビット列を並べたものを行列だと考える

まず、区間に関する条件がないものとして考えます。

与えられた数列をビット列だと思って行列を構成します。

f:id:betrue12:20190318002330p:plain

この行列の各行がそれぞれの要素に、各列がビットに対応します。ここから行をいくつか選んで要素のXOR和が  X のビット列と一致するような場合の数を求めるのが目的です。

今回の問題のように「要素のXOR和がある条件を満たすような、要素の選ぶ/選ばないの場合の数」を考える時、要素について「ある要素を他の要素にXORする」という操作を行っても答えは変わりません(こちらのE問題を参照)。これは行基本変形の1つであり、この操作を繰り返すことで行列を簡単にすることができます。上記の行列は以下の形まで簡単にできます。

f:id:betrue12:20190318002341p:plain

この行列の特徴は、

  1. 左から見てある列までは「全部0」か「1箇所だけ1」という状態になっていて、1になっている行は上から順に1つずつ進んでいる。
  2. それ以降の列は、それ以前の列で1が登場しているような行にしか1が存在しない。

というものです。このように変形すると以下のような性質が成り立ちます。

行のXOR和がある値  X に等しくなるような、行の選ぶ/選ばないの場合の数は、全要素が0である行の選び方を除くと高々1通りである。

具体的には  X をビット列として考え、先ほどの1.に含まれる列に関して「 X のビットが1なら、そのビットが立っている行を選ぶことにする」という風に行を選んでいきます。そのように行を選んでいって、最終的に選んだ行のビット列が全て  X と一致する場合はその1通りが条件を満たします。もし  X と一致しないビットがある場合、どのように行の選び方を調整しても  X と同じビット列を得ることはできません。

つまり求めたい場合の数は、全要素が0であるような行の個数を  z として  2^{z} または0になります。

区間に関する条件を考える

実際の問題では区間について「その区間から選ぶ要素の数は偶数個/奇数個である」という条件がありました。これの処理方法を考えます。

ここで、区間についての条件も行列に組み込んでしまうことを考えます。以下の図のように条件の個数  M 個だけ列を増やし、それぞれの列ではその区間に含まれる要素だけ1を立てます。

f:id:betrue12:20190318004053p:plain

元々のビット列については、 X のビット列と一致させることが必要でした。ではこの増やした列はどうなっているべきでしょうか?それぞれの列について、区間に含まれる要素を偶数個選んだ場合はXOR和は0、奇数個選んだ場合はXOR和は1になります。そのため与えられた条件の偶数個/奇数個に応じて、それぞれの列のXOR和を0/1にすることが条件を満たすことと同値になります。

こう考えてしまえば、前半で説明したものと解き方は同じです。条件の数だけ列を拡張し、「 X のビット列と条件の偶数個/奇数個に対応するビット列を結合したもの」を新しい  X だと思って解けば同じ方法で解くことが出来ます。

実装は掃き出し法です。ビット列の長さを  B = 30 として  N B+M 列の行列に掃き出し法を行うので、 B を定数だと思うとこの解法の計算量は  O(NM^{2}) となります。

ACコード

#325219 No.803 Very Limited Xor Subset - yukicoder

AGC031 C - Differ by 1 Bit

C - Differ by 1 Bit

解法

コンテスト本番で私が考察・実装した方針を書いていきます。公式解説とは実装の方針が異なっていて、公式解説のほうが恐らく楽な実装だとは思いますが、ACを得るまでの1つの過程として参考になればと思います。

YES/NO判定

まずはここから。数列が1つ進むごとにビットが立っている個数が  +1 または  -1 されること、数列の長さが偶数であることから、最初の要素と最後の要素でビットが立っている個数の偶奇は必ず異なっているはずです。なのでもし  A, B でビットが立っている個数の偶奇が一致していれば、問答無用で NO を出力すればよいです。

では偶奇が異なっている場合には必ず問題の条件を満たす数列が存在するでしょうか。なんとなく存在しそうな気がします(本番ではここで  N=3 のときの  8! 全列挙コードを書きました)。それはこれから具体的に構成していくことで示していきます。

考えやすい形への帰着

以降、「数列の隣り合う要素は2進表記でちょうど1桁だけ異なる」ことを単に「条件を満たす」と表記します。

まず、スタートもゴールも変数だとややこしいのでスタートを  0 にします。条件を満たす数列  A, ..., B は全ての要素に  xor A を掛けてもやっぱり条件を満たします。そのため  X = A xor B として、条件を満たす数列  0, ..., X を構築すれば、その全ての要素に  xor A を掛けて復元したものが答えになります。これでスタートを  0 に固定できます。

さらに  X のビットが散らばっていると考えにくいので、ビットの位置を並び替えて上位ビットに  1 を固めます。たとえば2進数で  X = 00100101 に対して、ビット列を並び替えて  X = 11100000 とします。これも後で位置を戻して復元します。

これらの操作によってこの問題は、スタートは  0、ゴールは  11...100...0 (1の個数は奇数で、 X の1の個数と同じ)であり条件を満たす数列を構成する問題に帰着することが出来ます。

構築

構築のアイデアは以下の通りです。

f:id:betrue12:20190317161659p:plain

図のように「 0 で始まるもの全部」「 10 で始まるもの全部」…という風に列挙しながら、一番上の桁を1つずつ  1 にしていきます。上からビットを固めていくので、最後まで影響を受けない一番右側のビットを調整に使います。

このように構築すると、ゴールの  1 の個数が奇数であれば必ず  2^{N} 通りの全ての値を尽くしてゴールにたどり着くことができます。

この構築をする上で必要なのは、図中青破線で示しているところで使う「  2^{i} 通りの数を尽くし、隣り合う要素はちょうど1ビット異なっていて、 0 で始まり  1 で終わるような数列」もしくはその逆順です。

これは再帰的に作ることが出来て、長さ  2^{i-1} のときの数列が得られているとすると

  1. 長さ  2^{i-1} のときの数列を2倍したもの
  2. 長さ  2^{i-1} のときの数列を2倍して1足したものの逆順

を結合することで長さ  2^{i} のときの数列を得ることが出来ます。例えば  \lbrace 0, 2, 3, 1\rbrace から上記の方法で長さ8の数列を作ると  \lbrace 0, 4, 6, 2, 3, 7, 5, 1\rbrace となります。

仕上げ

以上の方法で、スタートは  0 、ゴールは  11...100...0 であり条件を満たす数列を構成することができました。

最後にビットの位置を戻して、全要素に  xor A を掛ければ元の問題に対する答えが求められます。

ACコード

Submission #4601254 - AtCoder Grand Contest 031

AGC031 B - Reversi

B - Reversi

解法

まず、1つ性質を確認しておきます。それは「石の色を塗り替える操作について、両端と同じ色を間にも含むような区間に対する操作は考えなくても良い」ということです。具体的には以下の図の上側に示すような操作です。このような操作は下側のように小分けにした操作と同じになるので、小分けにした操作だけを考えて良いです。この性質は後で使います。

f:id:betrue12:20190317011038p:plain

答えの求め方ですが、左からDPをします。以下のようにDPテーブルを定義します。

 dp\lbrack i \rbrack = 左端から  i 番目までの石だけで考えた時の、色の塗られ方の場合の数

 dp\lbrack i \rbrack を求めるための遷移を考えます。 dp\lbrack i \rbrack としてあり得るものとして、まず「  i-1 番目までの塗られ方それぞれについて、単純に最後に  i 番目の石を足したもの」があります。この場合の遷移元は  dp\lbrack i-1 \rbrack です。

それ以外にあり得るのは「 i 番目を右端とするような操作をして  i-1 番目の石の色を変えたもの」で、この場合は先ほど数えたものとは異なる塗られ方が得られます。

最初に確認した性質を振り返ると、このときの操作の左端としては  i 番目より左側にある同じ色の石で一番近いものだけを考えればよいです。この一番近い石を  j 番目とします。もしここで  j = i-1 の時(つまりすぐ左隣が同じ色である時)は、操作をしても  i-1 番目の石の色が変わらないのでこちらの遷移は考えなくて良いです。

 j \lt i-1 の時、塗られ方としてあり得るのは「 j 番目までの色の塗られ方それぞれについて、後ろに塗りつぶされた石を並べたもの」なので  dp\lbrack j \rbrack が遷移元になります。

以上より、遷移は以下の3パターンに場合分けして計算できます。

f:id:betrue12:20190317004429p:plain

これをDPとして計算して、 dp\lbrack N\rbrack が答えです。

ACコード

Submission #4597497 - AtCoder Grand Contest 031

早稲田大学プログラミングコンテスト2019 I - Ramen

I - Ramen

解説を見て通したけど、実装にけっこう手こずったので記録。

解法

距離の2乗をコストに持つDP、といえばCHTです(?)。CHT(Convex-Hull Trick)が使えるように、価格  p_{i} の計算式を

  •  p_{i}^{\prime} = d_{i}^{2} + \min_{j} (-2d_{j} \times d_{i} + p_{j} + d_{j}^2)
  •  p_{i} = \min(p_{i}^{\prime}, x_{i})

と変形します。 p_{i}^{\prime} d_{i} についての一次式群から最小値を求める形式になっていて、CHTが使えそうです。

ただしこの問題の場合、CHTで解くには2つの課題があります。

  1. 店が開店する順番に価格を決定していく必要があるため  d_{i} の値を事前にソートできず、値を取得する点  d_{i} にも追加する直線の傾き  -2d_{j} にも単調性がない。
  2. 店が閉まるという事象を扱わなければいけない。CHTの「直線を消す」という操作に相当するが、これは無理。

1.の課題に対しては「Li Chao Tree」と呼ばれるものを利用することで解決できます。これはセグメント木を用いて直線群とその直線が最小値をとり得る区間を管理するもので、クエリの単調性を必要としません。

傾きの単調性が要らない Convex Hull Trick - kazuma8128’s blog

Li Chao Treeのメモ - 日々drdrする人のメモ

Li Chao Treeの追加/取得クエリの計算量は、長さを  D として  O(\log D) です。 D は取得クエリの値、すなわち  d_{i} の範囲に対応するので  10^{6} まで確保しておけばよいです。

そして2.ですが、こちらは日数の区間をセグメント木で管理することで解決できます。必要な操作は「ある日数区間に対してだけ直線を追加する」ことと「ある1日における直線群に対するある点の最小値を求める」ことなので、これらを実現します。

セグメント木の各ノードが日数の区間に対応し、それぞれがLi Chao Treeであるようなデータ構造を考えます。区間  \lbrack l, r) を担当するノードは、「区間  \lbrack l, r) 全体において営業している店(の直線)だけを追加したLi Chao Tree」として動作します。

このようにすると、

  • ある日数区間への直線追加:その区間に完全に含まれるノードに対して、直線の追加クエリを発行する。
  • ある1日における直線群に対するある点の最小値:その1日を含む全てのノードに対して最小値取得クエリを発行し、さらにその最小値を取る。

という方法で必要な操作を実現することができます。

f:id:betrue12:20190312212025p:plain

いずれの操作も、1回の扱うノード数は日数管理のセグメント木の長さを  L として  O(\log L) 個です。  L は日数なので  10^{5} まで確保しておけばよいです。

以上より全体計算量  O(N \log L \log D) で解くことが出来ます。座標圧縮で  N だけに依存するようにも出来ますが、これで十分でしょう。

注意点として、図のようにLi Chao Treeをセグメント木のノード数だけ作ることになるので、配列ベースで実装すると合計で  O(DL) 個の要素を作ってしまいます。ポインタベースで実装しましょう。

ACコード

Submission #4553775 - 早稲田大学プログラミングコンテスト2019

今回の問題で初めてLi Chao Treeを書きました。

早稲田大学プログラミングコンテスト2019 F - RPG

F - RPG

解法

「全ての頂点に対し、頂点  1 からのパスと、頂点  N へ向かうパスが存在する」「閉路がない」という制約から、無駄な辺/頂点はないということが分かります。具体的には全ての  1\to N パスを考えた時、全ての辺/頂点についてそれを通る 1\to N パスが存在し、さらに任意の頂点間の全てのパスについてもそれを通る  1\to N パスが存在します。

そのため、問題は以下のように言い換えられます。

  • 「戦闘頂点から戦闘頂点への任意のパスについて、そのパスに1つ以上の休憩所が存在する」という条件を満たすための最小コストを求めよ。

この問題は最小カット問題として解くことが出来ます。全ての戦闘頂点の「出口」を始点側に置き、「入口」を終点側に置きます。その間に他の頂点や辺を置き、休憩所を置くという操作を辺を切るという操作に上手く対応付けることができれば、最小カットコストがこの問題の答えに対応付けられます。

今回の場合は頂点がコストを持っているため、元のグラフにおける頂点を2つの頂点に分けてその間にコストを持つ辺を置くという方法が有効です。

具体的に入力例1を最小カット問題に帰着させたグラフは以下のようになります。

f:id:betrue12:20190310230952p:plain

このグラフの S \to T 最小カットを求めることで、答えを求めることが出来ます。

ACコード

Submission #4539728 - 早稲田大学プログラミングコンテスト2019

早稲田大学プログラミングコンテスト2019 E - Artist

早稲田大学プログラミングコンテスト2019 - AtCoder

解法

まず気付くべき点は、行の区切り位置と列の区切り位置を独立に考えられることです。行・列ともに、それぞれの区切り位置を境として黒いマスの個数が反転します。

そのためまずは行(列も同様)ごとの黒いマスの個数を数えて数列を作ります。そしてその数列を2つに区切る位置であって、2つに区切られた数列が両方とも回文になるようなものを数えればよいです。

f:id:betrue12:20190310215431p:plain

ただしたくさんの区切り位置についてこの回文判定を毎回計算していると時間が足りません。このように数列や文字列の色々な連続部分列について回文かどうかを効率的に判定したいときに、「Manacherのアルゴリズム」というものが使えます。

これは数列の全ての要素について、「その要素を中心とする連続した部分を見た時に、最大どれだけの長さが回文になるか?」を計算するものです。一般には回文判定(中心要素から端要素までの長さ)を求めるようにしていることが多いようです。計算量は数列の長さを  N として  O(N) であり、1回計算すればその結果を使って全ての連続部分列についての判定ができるので今回の用途にぴったりです。

注意点としてManacherは「その要素を中心とした」回文を考えるため、必然的に奇数長になります。そのため要素の間にダミーの値を挟んだ長さ  2N-1 の数列を用意し、それに対してアルゴリズムを適用することで偶数長の回文も求められるようにします。

ということで、ダミーを挟んだ状態の数列にManacherを適用し、元の数列の  i 番目の要素までで区切った時にそれぞれが回文になるための条件を考えましょう。これを求めるのは実験してみるのが良くて、0-indexedで書くと

  • 左側:中心は  i で、必要な回文半径は  i+1
  • 右側:中心は  N+i で、必要な回文半径は  N-i-1

です。ここで  N と表記しているものは行または列の個数(問題文中の  M, N )です。以下は具体例です。

f:id:betrue12:20190310221522p:plain

この方法で行・列ごとに条件を満たす区切り位置の個数を求めて、それを掛け算したものが答えです。

ACコード

Submission #4537644 - 早稲田大学プログラミングコンテスト2019

 N, M をそのまま使うと間違えそうだったので、コードでは  R, C にしています。