第一回日本最強プログラマー学生選手権-予選- C - Cell Inversion
解法
各マスの操作のされ方は、
のどちらかです。そして各マスがそのどちらになるかは、実は端から順番に決めていくことができます。
まず左端の1マス目を見てみます。これは必ず区間の始点になるので、左端のマスは必ず1回だけ反転します。なのでもし左端のマスの初期色が白だったら、どうやっても黒になってしまうので即アウト(0通り)です。
次に2マス目の扱い方は、「1番目のマスとペアにして終点となる」「右にあるマスとペアにして始点となる」の2択です。そして前者なら1回、後者なら2回、2番目のマスが反転します。なので2番目のマスの初期色が黒だったら前者、白だったら後者を選ぶ必要があり、終点/始点のどちらにするかが一意に決まります。
この考え方は一般化できます。つまり自分より左のマスの扱いが全て決まっていれば「左から何本、閉じていない操作区間が伸びてきているか」が分かり、その偶奇と自分の初期色から、自分が終点/始点のどちらになるべきなのかが一意に決まります。
より具体的に考えましょう。 マス目までの終点/始点を決めた時点で、 マス目に伸びてきている閉じていない操作区間が 個あるとします。このとき、もし マス目の初期色が白だったら、 マス目の反転回数が偶数にならないといけないので
- が偶数である場合、 マス目はこれまでの始点の「どれか」とペアにして終点となる。ここで場合の数が 倍され、次に伸びる区間は 個。
- が奇数である場合、 マス目は新しい区間の始点となる。次に伸びる区間は 個。
となります。 マス目の初期色が黒だったら真逆です。
ここでもし なのに マス目の初期色が白だったら、その時点で答えが0通りになります。また最後まで見終わった時点で閉じていない操作区間が残っている場合も0通りになります。(1敗)
この「 マス目を終点にするときに、始点のどれかを選んでペアにする」ときの選び方の数を全て掛け算したものが、ペアの作り方の数になります。今回の問題では 個のペアを並べる順番も考慮する必要があるので、 を掛けると答えになります。
ACコード
Submission #7112052 - Japanese Student Championship 2019 Qualification
「みんなのプロコン」本選 A - YahooYahooYahoo
お題箱より。
解法
「編集距離DP」を知ろう
まずは「編集距離DP」なるものを説明します。2つの文字列 の編集距離とは、文字列 に以下の操作を好きな順序で行って文字列 に一致させるための、操作回数の最小値です。
- 置換: の任意の1文字を選んで、それを任意の1文字に置き換える。
- 削除: の任意の1文字を選んで、それを取り除く。
- 挿入: の任意の位置に、任意の1文字を挿入する。
この3操作は今回の問題と同じですね。これは以下のようなDPで解くことができます。
- 文字列 の前から 文字目までを文字列 の前から 文字目までに一致させるための操作回数の最小値
このDPにおいて、文字列 の文字をそのまま採用することと、上記の3操作を行うことは以下のような遷移で表現できます。
- そのまま: が に一致する時に限り、
- 置換:
- 削除:
- 挿入:
遷移は全て「より小さければ更新」です。この計算量は です。
「yahoo」のループを考えよう
さて今回の問題です。目標とする文字列は yahoo
の繰り返しで、問題文の上では の長さがどこまでも大きくなる可能性があります。さらに、 という制約から2乗オーダーのDPは間に合いそうにありません。
しかし逆に言うと、 yahoo
は何周繰り返していようと条件判定には関係ないので、周回数の情報は忘れてしまうことができます。つまり状態定義はこうです。
- 文字列 の前から 文字目までを、「
yahoo
を0周以上繰り返した後、末尾にyahoo
の途中まで 文字が中途半端に付いているような文字列」にするための操作回数の最小値
このDPの遷移は先ほどの編集距離DPとほぼ同じです。相違点は は の値しか取らず、 の次は に戻ります。これは末尾の yaho
の後に o
を付けることに対応します。
ここで少し注意すべきは「挿入」の遷移で、 と遷移するため同じ での遷移となります。この遷移はどこかで止めないと無限に回りますが、1周以上の文字列を連続で挿入することは無駄なので、それぞれの からの挿入の遷移として1~4文字の挿入だけを考えれば十分です。
このときの具体的実装として、例えば以下のような遷移が素直です。
- 遷移元の それぞれについて挿入文字数 を全部試し、 と遷移する
この他に、公式解説のように「遷移を2周回す」という手があります。これは
- ...
という遷移を順番に回していくもので、
と2周回すことで先ほどの から 文字を挿入する操作が全パターン含まれるようになります。
どちらにせよ、yahoo
の文字数5を定数とするならばこのDPは で動作し、 として答えを求めることが出来ます。
ACコード
- (位置と挿入文字数を全部試す)Submission #7095420 - 「みんなのプロコン」本選 オープンコンテスト
- (2周回す)Submission #7095422 - 「みんなのプロコン」本選 オープンコンテスト
遷移先などの候補として「ループして自分より前のインデックスに遷移することはあるが、1周は超えない」という状況になったときには、文字列や数列を2倍して遷移を考えてみるとスマートに処理できることが多いです。例えばこの問題などもそうですね。
AtCoder Beginner Contest 135 D - Digits Parade
お題箱より。
「与えられた条件に従って各桁の数字を決められる」「出来上がる整数のうち、余りが特定の条件を満たすものを数える」という、是非とも押さえておきたい問題パターンの入門としてぴったりです。いつも以上に丁寧めに書きたいと思います。
解法
「前から○文字」を順に見ていく
まずは作れる数を全列挙してみましょう。文字列 として 51?3
を考えてみます。
このくらいなら作れる数は見ただけで10通り列挙できそうですが…今回はあえて、「前から○文字だけを見た時に作れる数」を最初から順番に見ていくようにします。
- 前から1文字:1文字目が
5
なので、作れる数は 。 - 前から2文字:2文字目が
1
なので、先ほどの の要素の末尾に1
をくっつけて、作れる数は 。 - 前から3文字:3文字目が
?
なので、これは0
から9
まで10通りのパターンがある。先ほどの の末尾に0
から9
を付けたものをそれぞれ考えて、作れる数は 。 - 前から4文字:4文字目が
3
なので、先ほどの それぞれの末尾に3
をくっつけて、作れる数は 。
ちょっと省略表記していますが、10通りの数を列挙しました。この10個のうち13で割って5で余る数の個数が答えです。
あえて順番に見ていったのは、この
- 「前から○文字」の時点で作れる数を、少ない文字数から順番に列挙していく。
- 「前から 文字」で作れる数は、「前から 文字」で作れる数それぞれの末尾に、 の 文字目の数を付け足すことで作ることができる。
- このとき 文字目が
?
だったら、作れる数の個数が10倍になる。
- このとき 文字目が
という考え方がとても大事だからです。
このように作れる数を列挙していって、最後に全部の数を13で割ってみれば、いつかは答えを求めることができます。しかし例えば文字列が ????????....
のようなものだった場合、1文字見るたびに個数が10倍になってものすごい個数になってしまいます。
そこで威力を発揮するのが「状態をまとめる」ということ。「以降ずっと同じ扱いをしていいような数はまとめてしまい、そのまとめた個数だけを覚えておく」という考え方です。
同じ扱いをしていい数を「まとめる」
この問題では、いくら大きな数を作っても最後には13で割った余りしか使いません。どれだけ多くの数を列挙しても、13で割った余りによってたった13通りに分類されてしまうのです。であれば、列挙している途中でどんどん分類して、まとめてしまうことはできないでしょうか?
先ほどの「ある数の末尾に数字を1個付け足す」という操作を具体的に考えてみましょう。元の整数が で末尾に付け足す1桁の整数が だとすると、結果は になります。これを順に繰り返すので、数字を付け足していく操作は足し算と掛け算だけで構成されていることになります。
そしてこのように足し算と掛け算だけで構成された計算の結果を13で割った余りは、計算の途中で出てくる数を13で割った余りに置き換えて同様に計算したものと同じになります。
※これは割る数が13に限ったものではなく、任意の正整数について言えます。また引き算でも、そして「逆元」というものを使えば割り算でも同じことが言えます。
例えば、列挙の途中で510という数があったとします。この末尾に 3
を付け足すと結果は5103になり、これを13で割った余りは7です。このように計算する代わりに、まず510を13で割って余り3を求めて、ここに 3
を付け足しても、33を13で割った余りは同じく7です。
この性質を使えば、列挙の途中でも数をまとめていくことができます。全ての数のパターンを具体的に持つ代わりに、「13で割って0余る数が○個」「13で割って1余る数が○個」という数え方をしていくのです。
DPをしよう
このように「順番に見ながら、これまでの計算結果を利用して必要な値を計算していく」「同じとみなしても良い状態をまとめていく」という処理を実現するのが動的計画法(DP)です。
先ほどのまとめ方をそのまま状態にします。つまり持つべき状態は、
- = 前から 文字の時点で作れる数のうち、13で割った余りが であるものの個数
です。このDPの遷移を考えましょう。
で数えられているのは、前から 文字の時点で作れる数で余りが の数です。この末尾に数 を付け足した数の余りは、 を13で割った余りになります。これを として、 に遷移すればよいです。
この としては、もし の 文字目が数字だったらその数。?
だったら の10通りを全部遷移させてしまいます。
これを最後まで計算して、 の長さを として が答えになります。
※ もし ?
が非常に多い場合、この がすごい数になってしまうかもしれません。しかし問題文には「答えは非常に大きくなる可能性があるため、 で割った余りを答えてください。」と書いてあります。そして遷移は全て足し算で計算できるので、先ほどの説明と全く同様の理由で、 は随時 で割った余りに置き換えて良いです。これをしないとオーバーフローを起こすか、多倍長整数が扱える言語でも計算時間が悪化します。
まとめ
「与えられた条件に従って各桁の数字を決められる」「出来上がる整数のうち、余りが特定の条件を満たすものを数える」というパターンの問題を、
- 「前から○文字だけを見た時に作れる数」を、少ない文字数から順番に列挙していく。
- 「計算の途中で余りを取っても良い」という性質を利用して、余りが同じになるような数はまとめてしまい、個数で管理する。
という考え方で解き、DPによって実装する方法を解説しました。
この考え方はそれ自体が頻出であるだけでなく、DPの根幹である「小さい問題から順に解いていく」「良い性質を使って、同じ扱いができるものはまとめてしまう」という思考のとても良い具体例になっています。
また発展的な内容として、さらに考慮すべき条件が加わる「桁DP」という問題パターンにも繋がります。
ACコード
AtCoder Beginner Contest 138 F - Coincidence
解法
考察も実装もそこそこ重い問題です。順に考えていきましょう。
記法について
剰余演算を記号 、XOR演算を記号 で表すことにします。
またこの記事では数え上げの対象である2数のペアを ではなく の順番で記載しています。
ビットだけの条件に置き換える
XORが絡む、制約が大きめ、与えられた下限/上限の間で条件を満たす値の数え上げ…ということで、帰着先として有力なのは2進数の桁DPです。しかしそのためには余りの条件をビットの条件に置き換えないといけません。
余りについての必要条件を導く時によく使うのは という性質です。この性質と を見比べると、 と の2進数での桁数は同じである必要があることが分かります。もし のほうが桁数が大きい場合、 に の最上位桁が残るので必ず となってしまうからです。
そしてこの「2進数での桁数が同じ」という条件から、 を で割った商は必ず1であることが分かります。もし が の2倍以上だとすると、必ず2進数で より大きい桁数になってしまうからです。このことから と置き換えることができます。 条件式は と変形できて、剰余演算を消すことができました。
さらにXORと足し算/引き算は近い性質を持っていて、 なる非負整数 に対して、2進数で繰り上がりがない足し算 や繰り下がりのない引き算 はXORと一致します。以前足し算とXORの比較をこの記事に書きましたが、同様の表を引き算についても書けば同じことが言えます。
そしてもし繰り下がりがあると引き算のほうがその分小さい値になってしまうので、逆に引き算とXORが一致するならば繰り下がりが一切ないということも言えます。
これでようやくビットの条件に言い換えられました。結局 となる必要条件は
- にビット単位での繰り下がりがない。つまり の各桁のビットの組み合わせは、 のいずれかである。
- 2進数での桁数が同じである。つまり前項目の3パターンの中で、上位桁から見て が登場する前に が登場することはない。
ということになります。また逆に上記の条件を2つとも満たすならば、実際に商が1になり引き算とXORが一致するので が成立します。これで十分条件であることも確かめられます。
※このように条件の言い換えテクニックを駆使すれば数式ベースで導くことができますが、思いつかない場合は小さい数で実験して、条件を満たす組み合わせの2進数表記を書き下してみるのが良いと思います。
桁DPを組む
ということで2進数での桁DPを組みます。 の範囲内で先ほどの条件を満たす組 を数えます。
2変数なので を別々に処理するのが難しく、両端を真面目に処理する必要があります。上限だけを考慮する場合は「上限 より小さいことが確定したかどうか」をフラグとして持つのが桁DPの常套手段ですが、今回は下限についても同様のフラグを持ちます。
さらに「上位桁から見て、ビットの組み合わせ が登場する前に が登場することはない」という条件も考慮すると、DPの状態は以下のような定義になります。
- = 桁目以上のビットの決め方であって、これまでに条件違反が確定するような遷移がなくて、各種フラグについて以下のような状態となっているような場合の数。
- が上限 よりも小さいことが確定している()/いない()
- が下限 よりも大きいことが確定している()/いない()
- これまでの桁でビットの組み合わせ が登場している()/いない()
桁DPの実装は人によって細かい差異がありますが、この記事では最下位ビットを 桁目として、上位ビットから順に決めていく方法を取ります。つまり初期状態を として、答えを の総和として求めます。
では遷移を組みましょう。気合いです。
まず についての条件は楽です。「 から遷移するときには のパターンを使わない」「 のパターンを使ったら にセットする」の2点を守ればよいです。
次に両端についての条件 です。ビットの組み合わせとして のどれを採用するかを決めれば、 の遷移は と のビットから、 の遷移は と のビットからそれぞれ求めることができます。
上限についての条件は桁DPでよく使いますね。図で描くとこうです。
下限についてはこう。似たような条件ですが色々と逆になっています。
×印で記したところは、これを採用してしまうと条件違反 や が確定してしまうところです。上限/下限のどちらか片方でも×印に遷移してしまう場合は遷移しないことにします。
これをDPの実装に落とし込むことができれば答えを求めることができます。気合いです。
ACコード
Submission #7000214 - AtCoder Beginner Contest 138
おまけ:実装テク
先ほどの画像の通りの遷移を条件分岐でゴリゴリ書けばいいのですが、if文だらけになるとつらいですね。
どちらも、遷移先の値は
- / の 桁目のビット
- 遷移前のフラグ / の値
- 桁目の / のビットとして何を採用するか
の3つから決まるので、私の実装ではこの遷移先を求めるだけの関数を作っています。この関数の中はちょっと散らかりますが、そのぶんループを回している本体が少しスッキリします。
このとき、先ほどの×印に相当する「遷移できない」ことの扱いが少し面倒なので、そのときは遷移先フラグの値として2を返すようにしています。DPテーブルのサイズとして / の場所は確保しつつ、次の遷移元にも答えの計算にも利用しないことで実質的に「遷移しない」ようにしています。
この辺りは好みだと思うので、バグらせにくそうだと思ったら真似してみてください。
CODE THANKS FESTIVAL 2017 H - Union Sets (並列二分探索解法)
お題箱より。
「公式解説で省略されている並列二分探索について知りたい」というリクエストだったのですが、私も実装したことがなかったので調べて書いてみました。私にとっても勉強になりました。
参考資料
参考にしました。
- Parallel Binary Search [tutorial] - Codeforces
- 並列二分探索(パラレルバイナリサーチ) - 迷いませんか?
- 並列二分探索(解説なしバージョン) - 宇宙ツイッタラーXの憂鬱
解法
対象とする問題
並列二分探索は以下のような形式の問題を解くことができるテクニックです。
- 個の操作からなる操作列があり、何らかの対象(数列や集合など)に対して順番に操作される。
- 以下のような形式の質問が 個あり、これら全てに答える必要がある。
- 「対象がある条件 を初めて満たすのは、操作列の中の何番目が操作された後か?」
- 単調性がある。ある時点での操作の後に条件を満たすならば、それ以降はずっと条件が満たされている。
今回の問題「Union Sets」では各操作が集合の併合であり、質問の条件が「ある2要素が同じ集合に属していること」なので、単調性が満たされています。
このような問題を、各質問についての二分探索を並列に行うという方法で解いていきます。
処理の流れ
まずは図を見てください。質問数 としています。
ok
ng
の初期値の決め方や、条件判定の結果に応じた ok
または ng
の移動などは通常の二分探索と同じです。違いは判定1回ごとに操作列のシミュレートを頭から行って、各質問ごとの mid
の位置に来たときに判定を行う、という点です。実装においては逆に mid
の値ごとに質問を分類しておくと良いです。
操作列を何度もシミュレートするという点が計算量的に危険に見えますが、二分探索の1ループなので 回しか回りません。今回の問題ではUnion-Find木を用いれば1回のシミュレーションは 、それと各質問の判定が1ループ1回ずつなので全体計算量として になります。 はアッカーマン関数の逆関数です。
実装&ACコード
並列二分探索の実装だけ書くとこんな感じになります。
// 各質問について通常の二分探索のように初期値を設定(0-indexed) vector<int> ok(Q, M), ng(Q, -1); while(true){ // midの値ごとに質問を分類。全質問ok-ng==1であれば終了 bool finish = true; vector<vector<int>> mid_idx(M); for(int i=0; i<Q; i++) if(ok[i]-ng[i]>1){ finish = false; int mid = (ok[i]+ng[i])/2; mid_idx[mid].push_back(i); } if(finish) break; // 操作列をシミュレートしながら、各midのタイミングで各質問について判定 UnionFind uf(N); for(int i=0; i<M; i++){ uf.unite(A[i], B[i]); for(int idx : mid_idx[i]) (uf.same(X[idx], Y[idx]) ? ok[idx] : ng[idx]) = i; } }
提出コードはこちらです。
Submission #6896843 - CODE THANKS FESTIVAL 2017(Parallel)
余談
並列二分探索のようなテクニックが必要になる背景には、「操作列を適用していった途中の状態を即座に得ることは難しい」という事情があります。もし途中のある時点での条件判定がすぐにできるなら、並列にせずとも各質問ごとに二分探索ができますよね。
今回の問題に限って言えば、部分永続Union-Find木というデータ構造を用いることで「過去のある時点である2要素が同じ集合に属していたか?」を調べることができます。仕組みについては以下の記事が参考になります。
部分永続Union-Find Treeについて - noshi91のメモ
これを用いた提出コードは以下です。各質問ごとに二分探索しています。
AtCoder Beginner Contest 136 D - Gathering Children
私の解法をTwitterに流したらわりと好評だったので記事にまとめておきます。
解法
ある程度動きをシミュレーションしてみると、十分に時間が経った後は全ての子供が RL
の2マスで振動するということが分かります。最終状態を求めるためには動きが止まってくれると考えやすいのですが、振動する動きをそのまま扱うと少し面倒です。これを扱いやすくするために、移動2ターンをセットで考えてみることにしましょう。
2ターンをセットで考えると子供の動きは以下の3パターンに分類されます。
- 自分が
R
で右隣もR
:2ターンで右に2マス動く。 - 自分が
L
で左隣もL
:2ターンで左に2マス動く。 - それ以外:振動するので、2ターン単位で見ると動かないとみなせる。
ここで、例えば2マス右に動いた子供が次の2ターンも2マス右に動くことはあり得ます。しかし2マス右に動いた子供が次の2ターンで左に2マス動くことはありません。2マス右に動いた後に左隣にあるのは必ず R
なので、2マス左に動く条件を満たさないからです。全く同様の理由で「左2→左2」はあり得ますが「左2→右2」はあり得ません。
よって、右に動く子供と左に動く子供は独立に考えることができます。具体的には、
- 最初に全てのマスに1人ずつ子供を置いておく。
- 左端から順番にマスを見ていき、「見ているマスと右隣がともに
R
」であればそのマスにいる子供を全て2マス右に移動させる。 - 右端から順番にマスを見ていき、「見ているマスと左隣がともに
L
」であればそのマスにいる子供を全て2マス左に移動させる。
とすることで答えを求めることができます。移動の総回数が偶数なので、2マス単位の移動を十分な回数繰り返した状態が答えになります。
ACコード
AtCoder Beginner Contest 136 F - Enclosed Points
解説
数え上げの軸を変える
- 個の部分集合それぞれについて、その集合に対応する長方形に 個の点のうちいくつ含まれるかを考え、それを全て合計したものを求めよ。
という問題です。部分集合の数が多すぎますね。まともに列挙するのは到底無理です。
これをこうひっくり返します。
- 個の点それぞれについて、長方形にそれが含まれるような部分集合が 個のうちいくつあるかを考え、それを全て合計したものを求めよ。
このように「XについてYを数えたものを合計する」を「YについてXを数えたものを合計する」と言い換えるのはとても重要なテクニックの1つです。特にXに当たるものが何かの選び方や並べ方だと、Xの要素数が や など膨大になりがちです。Xの要素数が膨大でYの要素数が比較的小さい場合、ひっくり返すと見通しが良くなることが多いです。
点が長方形に含まれる条件を考える
ある1点 を見た時に、長方形に点 が含まれるような部分集合の個数を数えることを考えます。
まず 自身が部分集合に含まれるときは残りの点の選び方に関わらずOKです。残りの点を部分集合に含めるかどうかを自由に選べるので、場合の数は 通りです。
以降は を部分集合に含まない場合を考えます。このとき、長方形に点 が含まれる必要十分条件は、
- 点 から見て左上にある点と、右下にある点がともに1個以上選ばれている。
- または、点 から見て右上にある点と、左下にある点がともに1個以上選ばれている。
この少なくとも一方が満たされることです。つまり座標平面を点 から見て左上・左下・右上・右下の4領域に分けて、それぞれの領域の点が1個以上選ばれているかどうかの組み合わせによって、長方形に点 が含まれるかどうかが決まります。
図のようにそれぞれの領域に と名前を付け、「その領域に1個以上点が含まれている」という事象を同じ記号で表すことにします。またある事象 に当てはまる場合の数を と表記することにします。そうすると上記の条件を満たす場合の数は
となりますが、これは包除原理 を用いて
と等しくなります。
これで「かつ」条件だけで求められる式になりました。それぞれの領域について点の選び方は実質的に独立に決めて良いので、各領域ごとにその領域に含まれる点の「全ての選び方の数」と「1個以上選ぶような選び方の数」を求めることができればこの場合の数を求めることができます。
※「実質的に独立に決めて良い」と書いたのは、問題文では「空でない」部分集合に限定しているので厳密には独立ではないという意味ですが、空集合は答えに算入しないと思うことにすればこれは考慮しなくて良いです。
※今回の問題では制約上、点 の真上・真下・真横に他の点が存在しないので、4領域が重複なくきれいに分かれるようになっています。やさしい。
それぞれの領域にある点を数える
ある領域に点が 個含まれているとき、全ての選び方は 通りあります。そのうち1通りだけが「1個も選ばない」というものなので、1個以上選ぶような選び方は 通りです。つまり、領域に含まれている点の個数が分かればよいです。
座標平面上の長方形領域に含まれる点の個数なので、座標圧縮して二次元累積和などが使えると良いのですが… かかってしまうので時間もメモリも足りません。何とかして一次元に潰したいです。
これは、点を調べていく順番を工夫することで解決できます。 座標の小さい順に点を見ていくと、点 を見ているときの領域それぞれは
- 既に見終わった点のうち、 であるようなもの
- 既に見終わった点のうち、 であるようなもの
- まだ見ていない点のうち、 であるようなもの
- まだ見ていない点のうち、 であるようなもの
として求めることができます。つまり具体的な 座標の値を考えなくても良くなり、 座標だけの条件で計算できます。
あとは「既に見終わった点」「まだ見ていない点」のそれぞれについて、 がある範囲内にあるような点の個数を求めれば良いです。これはそれぞれについて 座標をインデックスとするようなBITを用意し、最初にBIT(未)に全ての点を入れておき、点を見ていくごとにBIT(未)から除外してBIT(既)に足す、という処理をしていけば実現できます。座標圧縮を忘れずに。
これで各領域に含まれる点の個数を1回あたり で求めることができたので、先ほどの計算式を用いて場合の数を求めることができます。全体計算量は になります。
ACコード
Submission #6701344 - AtCoder Beginner Contest 136
上記コードの細かい補足としては、BITで範囲を指定する時に点 の 座標も含めてしまっています(このBITは閉区間で作っています)。コードのように、点Pを見る前にBIT(未)から除いて見た後にBIT(既)に足すようにするとこれでもOKです。もちろん点 自身の 座標を含めないように範囲指定してもOKで、そちらのほうが安全です。