2019-02-20

Codeforces Round #540 F2. Tree Cutting (Hard Version)

コンテスト単位の記事がなかなか書けずにこどふぉの記事をサボってしまっているので、比較的楽に書ける1問単位の記事も書いていこうと思います。ちょっと方向性模索中。

解法

同じ色の頂点を繋ぐ

もし直接辺で繋がっていない頂点同士が同じ色だった場合、その間のパスに含まれる頂点は全て同じ連結成分に含まれる必要があります。なので前もってパス上の頂点をその色で塗りつぶしておくことで、今後の処理が楽になります。

これを効率的に行うためにLCAを利用します。同じ色の頂点全てのLCAを求めて、各頂点からLCAまでの経路上の頂点を全て塗れば良いです。（同じところを何度も塗りなおすような実装だと時間がかかるので注意）

このとき、もし塗ろうとした頂点に既に別の色が塗られていた場合は問題の条件を満たすことは絶対に不可能なので、0 を出力して終了します。ある色の頂点たちが別の色の頂点で分断されているような場合や、パス同士が交差してしまうような場合が該当します。

以降は、こうやって色を塗り足して同じ色の頂点をそれぞれ連結にした状態を考えていきます。

辺の切り方をDPで数える

適当に根を決めて木DPをします。このとき状態は以下のように取ることが出来ます。

$dp\lbrack i \rbrack\lbrack 0 \rbrack =$ 頂点 $i$ 以下の部分木における辺の切り方であって、頂点 $i$ が含まれる連結成分に有色の頂点が含まれていないような場合の数。
$dp\lbrack i \rbrack\lbrack 1 \rbrack =$ 頂点 $i$ 以下の部分木における辺の切り方であって、頂点 $i$ が含まれる連結成分に有色の頂点が含まれているような場合の数。

「辺をいくつ切ったか？」「具体的に何色の頂点が含まれているか？」というパラメータが必要そうに見えますが、それらを含めてしまうと計算が間に合いません。上手くDPをすることでこれらのパラメータを持たなくても正しい数え上げをすることができます。

先ほど同じ色の頂点は連結になるように間を塗ったので、有色の頂点の間に無色の頂点が挟まっている場合、それら有色の頂点同士は必ず異なる色になっています。そのためどの色が伸びてきているのかに関わらず、その間のどこかでは必ず辺を切らないといけません。これにより「具体的に何色の頂点が含まれているか？」という情報を不要にすることができます。

そして必要以上に辺を切らない、具体的には「 $dp\lbrack i \rbrack\lbrack 0 \rbrack$ から遷移するときには辺を切ることを考えない」ことにより、最終的には必ずちょうど $K-1$ 本の辺が切られている状態になっているはずです。これにより「辺をいくつ切ったか？」という情報を不要にすることができます。

この考え方をもとに遷移を構成していきましょう。

頂点 $i$ が有色であるとき

有色の頂点については必ず $dp\lbrack i \rbrack\lbrack 0 \rbrack = 0$ になるので、 $dp\lbrack i \rbrack\lbrack 1\rbrack$ の計算だけを考えます。それぞれの子からの遷移は、子との色関係によって

子 $j$ が $i$ と同じ色を持っている場合、 $dp\lbrack j \rbrack\lbrack 0\rbrack = 0$ であり、 $dp\lbrack j \rbrack\lbrack 1\rbrack$ から「辺を繋ぐ」という遷移があり得る。
子 $j$ が $i$ と違う色を持っている場合、 $dp\lbrack j \rbrack\lbrack 0\rbrack = 0$ であり、 $dp\lbrack j \rbrack\lbrack 1\rbrack$ から「辺を切る」という遷移があり得る。
子 $j$ が無色である場合、 $dp\lbrack j \rbrack\lbrack 0\rbrack$ から「辺を繋ぐ」という遷移と、 $dp\lbrack j \rbrack\lbrack 1\rbrack$ から「辺を切る」という遷移があり得る。

の3パターンに分かれます。これらは結局どれも $dp\lbrack j \rbrack\lbrack 0\rbrack + dp\lbrack j \rbrack\lbrack 1\rbrack$ 通りになるので、これを全ての子について掛け算したものが $dp\lbrack i \rbrack\lbrack 1\rbrack$ です。

頂点 $i$ が無色であるとき

まずは $dp\lbrack i \rbrack\lbrack 0 \rbrack$ を考えます。これは有色の頂点が含まれている連結成分を一切繋がないようにするので、

子 $j$ が有色である場合、 $dp\lbrack j \rbrack\lbrack 0\rbrack = 0$ であり、 $dp\lbrack j \rbrack\lbrack 1\rbrack$ から「辺を切る」という遷移があり得る。
子 $j$ が無色である場合、 $dp\lbrack j \rbrack\lbrack 0\rbrack$ から「辺を繋ぐ」という遷移と、 $dp\lbrack j \rbrack\lbrack 1\rbrack$ から「辺を切る」という遷移があり得る。

と、先ほどとほぼ同じになります。 $dp\lbrack j \rbrack\lbrack 0\rbrack + dp\lbrack j \rbrack\lbrack 1\rbrack$ を全ての子について掛け算したものが $dp\lbrack i \rbrack\lbrack 0\rbrack$ です。

一方 $dp\lbrack i \rbrack\lbrack 1 \rbrack$ のほうでは、どれかちょうど1つの子からは有色の頂点を含む連結成分を繋ぎ、残りの子については色を持ち込まないという遷移を考えます。この1つの子を全通り試すので、そのような子を $k$ として

$dp\lbrack i \rbrack\lbrack 1 \rbrack = \sum_{k}(dp\lbrack k \rbrack\lbrack 1\rbrack \times \prod_{j \ne k}(dp\lbrack j \rbrack\lbrack 0 \rbrack + dp\lbrack j \rbrack\lbrack 1 \rbrack))$

が遷移の計算式になります。外側の $\sum$ が全ての子 $k$ について回り、その中の $\prod$ は $k$ 以外の子 $j$ について回るので、これは単純に計算すると子の数の2乗オーダーの計算時間がかかります。ですが積の部分を $k$ を挟んで左右からの累積積を用いて計算することで1乗オーダーに落ちます。

※ほとんどの場合は総積から1つだけ割り算（逆元の掛け算）をすることでも計算可能ですが、0除算になってしまう可能性があるので避けたほうが無難です。

このDPを根まで計算し、根を $r$ として $dp\lbrack r \rbrack\lbrack 1 \rbrack$ が答えです。

ACコード

Submission #50200443 - Codeforces

おまけ（類題情報）

わりと似たような木DPをする類題です。これも好き。

Codeforces Round #522 C. Vasya and Maximum Matching - ARMERIA

「総積から1つだけ外した値が欲しいけど、0除算の可能性があるから逆元が使えない」という問題は、最近だとEDPCにありましたね。kyopro_friendsさんの記事のリンクを貼らせていただきます。

EDPC解説 U～Z - kyopro_friends’ diary

2019-02-18

全国統一プログラミング王決定戦本戦解説（C～E）

プログラミング競技プログラミング AtCoder

今回はオンサイト参加でした！

成績は200人中46位。なかなか健闘したんじゃないでしょうか。

f:id:betrue12:20190218220603p:plain

参加記はまた気が向いたら別記事で書きます。この記事ではいつものように問題解説を。

現在Eまで書いていますが、Fは後日追記したいと思っています。G以降はまだ通せていません…。

C - Come Together

解法

まず、縦の座標と横の座標を独立に考えられることに気付くと良いです。縦の座標を揃えるための操作回数と横の座標を揃えるための操作回数の合計が答えとなります。

では、縦の座標についてはどの座標に全ての駒を集めるのが最適でしょうか。結論を書くと、これは全部の駒の座標の中央値になります。これについては同じ知識を使う問題の解説を以前書いたので、そちらを参考にしてください。

ARC100 参加記録 - ARMERIA

というわけで中央値を求めたいですが、駒の数が全部で $HW-K$ 個あるので全てを列挙することはできません。そこで、次のようにして駒の縦座標の「分布」を求めることにします。

まず $K$ 個の駒を取り除く前の分布を作る。1行目から $H$ 行目まで全てに $W$ 個の駒があるので、分布は $\lbrack W, W, ..., W\rbrack$ となる。
そこから、 $K$ 個取り除いた駒それぞれについてそれぞれの $R_{i}$ に対応する個数を1減らす。

この累積和を下から取っていき、ちょうど $HW-K$ 個の半分以上になったところが全ての座標の中央値になります。中央値が求まれば、先程の分布をそのまま使って駒の移動回数を求めることが出来ます。縦と横それぞれについて同じ計算をして足したものが答えです。

ACコード

（C++）Submission #4314368 - 全国統一プログラミング王決定戦本戦

D - Deforestation

解法

それぞれの竹から得られるスコアは、その竹を最後に伐採した時刻と一致します。これを求める方法はいくつかありますが、一例を示します。

竹を番号1から順番に見ていきます。このとき、「今見ている竹を伐採する時刻の集合」を順序付き集合（C++なら std::set ）で持っておきます。この集合は、竹を順番に見ていきながら「区間 $\lbrack L_{i}, R_{i}\rbrack$ に入ったら $T_{i}$ をinsertし、区間から出たらeraseする」ことによって管理できます。順序付き集合で持っていればそれぞれの竹について一番大きい要素がわかるので、答えの値に足していけばよいです。

ACコード

Submission #4314235 - 全国統一プログラミング王決定戦本戦

本番は区間更新できるセグメント木を使いましたが、set でめちゃくちゃ簡単に書けますね…

E - Erasure

解法

魔法がたくさんあるので、いくつかにグループ分けして考えたいです。今回は区間の左端の値でグループ分けしてみます。

左から見ていって、左端が $1, 2, ..., i$ の魔法について使う/使わないを決め終わったとします。残りの魔法は $i+1$ 以降のブロックにしか作用しないため、問題の条件を満たすためにはこの時点で $1, ..., i$ のブロックが全て消えていなければいけません。そして $i$ より右側のブロックについては、連続してあるところまでが消えているような状態になっているはずです。

このことから以下のようなDPを考えます。

$dp\lbrack i \rbrack\lbrack j \rbrack =$ 左端が $1, 2, ..., i$ の魔法について使う/使わないを決め終わったとき、 $1, ..., j$ のブロックが全て消えているような場合の数。ただし、 $i \le j$ とする。

これを計算しましょう。 $i-1$ の状態から遷移してきて $dp\lbrack i \rbrack\lbrack j \rbrack$ の状態になるのは、以下のいずれかのときです。

f:id:betrue12:20190218234730p:plain

左端が番目の魔法まででちょうど番目のブロックまで消えていて、左端が番目の魔法で番目より右側のブロックが消えないパターン。
- 遷移元の場合の数は $dp\lbrack i-1 \rbrack\lbrack j \rbrack$ 通り。
- 左端が $i$ 番目の魔法については、右端が $j$ 以下であるものの使う/使わないは自由。そのような魔法の個数を $m$ とすると $m = \max(0, j-i-K+1)$ であり、係数として $2^{m}$ が掛かる。
左端が番目の魔法までで番目未満のブロックまで消えていて、左端が番目の魔法でちょうど番目のブロックまで消えるパターン。
- 遷移元の場合の数は $dp\lbrack i-1 \rbrack\lbrack i-1 \rbrack + \cdots + dp\lbrack i-1 \rbrack\lbrack j-1 \rbrack$ 通り。
- 左端が $i$ 番目の魔法については、右端が $j$ であるものは必ず使う。そのため $j-i \ge K$ である必要がある。右端が $j$ 未満の魔法の使う/使わないは自由であり、そのような魔法の個数は $j-i-K$ なので係数として $2^{j-i-K}$ が掛かる。

これら2パターンからの遷移を足したものが $dp\lbrack i \rbrack\lbrack j \rbrack$ となります。このうち $dp\lbrack i-1 \rbrack\lbrack i-1 \rbrack + \cdots + dp\lbrack i-1 \rbrack\lbrack j-1 \rbrack$ については、DPの更新時に $j$ を回しながら累積和を取っていくと良いです。

区間の左端としてあり得るものは $N-K$ までなので、答えは左端を $N-K$ まで見て $N$ までのブロックが消えているような場合の数、すなわち $dp\lbrack N-K \rbrack\lbrack N \rbrack$ となります。

ACコード

（C++）Submission #4314458 - 全国統一プログラミング王決定戦本戦

2019-02-10

みんなのプロコン2019 参加記録＆解説

AtCoder プログラミング競技プログラミング

今回は5完！かなり健闘したとは思いますが、それでも赤パフォは取れず。厳しい世界。

f:id:betrue12:20190210002435p:plain

問題数が多いので、Cから解説します。

C - When I hit my pocket...

解法

まず、ビスケットを「普通に叩いて増やす」のと、「円を介して増やす」のはどちらが得か考えます。

普通に叩いて増やす場合、操作1回でビスケットが1枚増える。
円を介して増やす場合、操作2回でビスケットが $B - A$ 枚増える。

このことから、 $B-A \le 2$ である場合は普通に叩き続けたほうが得です。答えは $1 + K$ になります。

そうでない場合は円を介してビスケットを増やしていきたいですが、それにはまず $A$ 枚の元手が必要なので、操作手順は次のようになります。

手持ちのビスケットが $A$ 枚になるまで叩く。必要操作回数は $A - 1$ 回。
残りの操作回数を2で割って切り捨てた回数だけ、円を介してビスケットを増やす。操作回数2回につきビスケットが $B-A$ 枚増える。
最後に操作回数が1回余ったら叩く。

この手順に基づいて計算すれば答えが出ます。ですがもし操作回数が $A-1$ 回に足りない場合は、叩き続けるだけで終わってしまうのでやっぱり答えは $1+K$ です。

ACコード

（C++）Submission #4219154 - Yahoo Programming Contest 2019

D - Ears

解法

耳に入っている石の個数の並びにどのような特徴があるか考えます。

すぬけくんが動く範囲は連続した区間になるので、整数座標点 $0, 1, ..., L$ のうちすぬけ君が動いた範囲を $\lbrack l, r \rbrack$ とします。そしてすぬけくんの移動の始点と終点をそれぞれ $s, t$ とします。この範囲の移動を図示してみます。

f:id:betrue12:20190210010419p:plain

上の図で示すように、それぞれの道の通過回数は、左から

「0」→「2以上の偶数」→「奇数」→「2以上の偶数」→「0」

という並びになります。ただし各ゾーンの長さが0であることはあり得ます。耳の石の個数として作れる数列は必ずこの形をしていて、逆にこの形の数列なら $l, r, s, t$ およびどこで往復を入れるかを調整することで必ず作ることが出来ます。

※ 上の図と違って $s$ が $t$ より右側にある場合も通過回数は同様の形になり、「真ん中が3以上の奇数」に変わるだけなので考えなくて良いです。

ということで、石の個数の並びの特徴が分かりました。あとは操作回数、すなわち目標とする数列 $A_{1}, ..., A_{N}$ との差をなるべく小さくすることを考えます。

数列を左から見ていくDPを考えます。このとき先ほどの各ゾーンに、順番にゾーン0からゾーン4までの番号を付けておきます。そしてDPテーブルを

$dp\lbrack i \rbrack\lbrack j \rbrack =$ $i$ 番目までの耳まで見て、 $i$ 番目の耳がゾーン $j$ に属しているときの、それまでの操作回数の最小値

とします。

$dp\lbrack i\rbrack \lbrack j\rbrack$ を求めるための遷移を考えます。 $i-1$ 番目から $i$ 番目に遷移するときに、ゾーンを進めることは出来ますが戻すことは出来ないので、遷移元として選ぶことができるのは $dp\lbrack i-1\rbrack \lbrack 0\rbrack, ..., dp\lbrack i-1\rbrack \lbrack j\rbrack$ からです。このうち一番小さいものを遷移元として選びましょう。

次に、 $i$ 個目の耳がゾーン $j$ に属しているときに石の個数を $A_{i}$ と一致させるための操作回数を求めます。これは各ゾーンによって違って、

ゾーン0, 4：通過回数は0回。なので操作回数はそのまま $A_{i}$ 回。
ゾーン1, 3：通過回数は2以上の偶数回。なので操作回数は $A_{i}$ が0なら2回、2以上の偶数なら0回、奇数なら1回。
ゾーン2：通過回数は奇数回。なので操作回数は $A_{i}$ が偶数なら1回、奇数なら0回

と求めることが出来ます。遷移元の最小値と操作回数の合計で $dp\lbrack i\rbrack \lbrack j\rbrack$ を更新します。

このDPを最後まで計算して、 $dp\lbrack N\rbrack \lbrack j\rbrack$ のうち一番小さいものが答えです。

ポイントは以下の2点ですね。

操作回数の並びにどのような特徴があるかを考察する。
数列全体をいくつかのゾーンに分けることができて、その個数が十分小さいときには、「 $i$ 番目まで見て、ゾーン $j$ に属しているときの○○」のようなDPができないか試す。

ACコード

（C++）Submission #4219578 - Yahoo Programming Contest 2019

E - Odd Subrectangles

解法

解説がバリバリの線形代数＋有限体の話になっているので、なるべく難しい概念を使わずに説明してみますが…どうしても線形代数の知識は要りますね。

行列の基本変形

まず考えるべきは、行（列も同様）について以下の操作を自由に行っても答えは変わらないということです。

ある行とある行を入れ替える。
ある行の値を、別の行の値に足す。

ただし使うのは値の偶奇だけなので、「足す」という操作は「XOR演算をする」と思うことにします。こうすると演算後も各要素の値は0または1になります。

1.については分かりやすいと思います。2.についてですが…例えば（行1, 行2, 行3) からなる行列 $A$ を、（行1+2, 行2, 行3）からなる行列 $A^{\prime}$ に置き換えたとします。このとき例えば $A$ においての行1, 2, 3を（使う、使う、使う）という選び方に対しては、 $A^{\prime}$ においては（使う、使わない、使う）と選ぶことで同じものを実現できます。各行について使う/使わないが対称になっているので、 $A$ における行の選び方と $A^{\prime}$ における行の選び方は1対1対応します。

これらの操作は、「3. ある行/列を0でない定数倍する」という操作と合わせて「行列の基本変形」と呼ばれています。今回は要素が0, 1しかなく、0でない定数は1だけなので3.の操作は実質的には意味がありません。

行列の基本変形ができる場合、この操作を繰り返していくことで行列をどんどん簡単にしていくことができます。具体的には以下の形まで簡単にできます。

f:id:betrue12:20190210141719p:plain

この形式にしたときの1の個数 $r$ をこの行列のランクと呼びます。要素がほとんど0になったのでかなり考えやすくなりました。

答えを数え上げる

行列をさきほどの形式に変形して、1の個数 $r$ が分かったとします。この状態から答えを数え上げていきましょう。「使う行と列が交差する要素の合計」を $S$ と書くことにします。

まず、0しか含まない下のほうの行と右のほうの列はどう選んでも $S$ に影響しません。そのような行は $N-r$ 個、列は $M-r$ 個あるので、ここで $2^{N+M-2r}$ の係数が得られます。

残りの $r \times r$ の行列部分を考えます。まず最初に行の選び方を決めたとします。このとき、「行を1つ以上使うように選んでいれば、 $S$ が奇数になるような列の選び方は、列の選び方すべてのちょうど半分である」ということが言えます。この理由を説明します。

使う行のうち何か1つの行を $i$ 行目とします。このとき $(i, i)$ に要素1があるので、 $i$ 列目を使えば $S$ に1が加算されます。そのため先に $i$ 列目以外の使い方を全部決めてしまえば、それまでの $S$ が偶数のときは「 $i$ 列目を使う＝ $S$ が奇数」、「 $i$ 列目を使わない＝ $S$ が偶数」となります。 $i$ 列目以外における $S$ が奇数の場合は逆です。このように考えると、 $i$ 列目の使う/使わないで最終的な $S$ の偶奇が決まるので、それぞれの場合の数は半分ずつになります。

ただしこれは行を1つ以上使うように選んだ場合の話で、行を1つも使わない場合は $r$ 個の列をどのように選んでももちろん $S$ は0になります。このことから $S$ が奇数になる選び方は

行を1つ以上使うような、 $r$ 個の行の選び方： $2^{r} - 1$
$r$ 個の列の選び方のうち半分： $\frac{2^{r}}{2} = 2^{r-1}$

を掛け算したものです。さらに $r \times r$ の範囲外の行と列に関する係数 $2^{N+M-2r}$ を掛けて、答えは

$2^{N+M-2r} \times (2^{r} - 1) \times 2^{r-1} = 2^{N+M-1} - 2^{N+M-r-1}$

となります。

実装

ここまでが考察で、あとは実装なのですが…行列の基本変形によってランクを計算するアルゴリズムが必要です。これは「掃き出し法」という名前で知られています。

コードは以下のリンクを参考にしていただければと思います…計算量は $O(NM^{2})$ です。行と列を逆にしてもよいので、より正確には $O(NM\min(N, M))$ でしょうか。要素同士の足し算の代わりにXORを使うことに注意してください。

ACコード

（C++）Submission #4218848 - Yahoo Programming Contest 2019

F - Pass

解法

最終的に高橋くんに渡るボールの順序としてどのようなものがあるか考えます。まず必要条件として、「 $i$ 人目のすぬけ君が持つボールは、高橋くんには $i$ 番目以降に渡される」ということが言えます。 $i$ 番目より前に渡そうと思っても届きません。

この「 $i$ 人目のすぬけ君が持つボールは、高橋くんには $i$ 番目以降に渡される」という条件を満たすように、各ボールに「高橋くんに渡されたい順序」を被りなく書き込むことにします。この順序に合うようにボールを回して高橋くんに届けていくことは、実は必ず可能です。全員のすぬけ君が常に「持っているボールのうち、順序の早いほうを次に渡す」ように行動すれば、ボールに書いたとおりの順序で高橋くんに渡すことが出来ます。

以上の考察から、この問題の操作は以下のように言い換えられることが分かります。

「使えるボール」が入った袋は最初は空である。
以下のターンを回繰り返す。
1. $i$ ターン目の前に、 $i$ 人目のすぬけ君が持つボール2個を袋に入れる。（ $i \le N$ のとき）
2. その後、高橋くんは袋から1個のボールを自由に取り出す。

このように考えると、以下のようなDPができるようになります。

$dp\lbrack i \rbrack\lbrack r \rbrack =$ $i$ ターン目までの操作が完了して、それまでに使った赤ボールが $r$ 個であるような場合の数

このように状態を定義すると、それまでに使った赤ボールは $i-r$ 個になります。 $i$ ターン目までに袋に入った赤ボール・青ボールそれぞれの個数は入力から計算できるので、その個数を使ったボール数が赤青ともに超えない範囲で $r$ を動かすことができて、それ以外の $r$ については0通りです。

遷移については赤ボールを使う/青ボールを使うの2通りなので、 $dp\lbrack i+1 \rbrack\lbrack r \rbrack = dp\lbrack i \rbrack\lbrack r \rbrack + dp\lbrack i \rbrack\lbrack r-1 \rbrack$ となります。このDPを最後まで計算すると、 $O(N^{2})$ で答えが求められます。

ACコード

（C++）Submission #4222715 - Yahoo Programming Contest 2019

2019-02-07

Xor Sum　Editorial解法の「解説の解説」

AtCoder プログラミング競技プログラミング

D - Xor Sum

重み付き配点のABCで出された問題としては最強候補の1つと言われている「Xor Sum」。ビット単位のXOR演算と整数の足し算の密接な関係を利用した問題で、様々な解法が考えられています。こちらの記事ではいくつかの解法がまとめられています。

Xor Sum(ARC066 D)についてのいろんな解法 - Qiita

問題自体の難しさもさることながら、公式解説PDFも行間を補って読み解く必要がありなかなか大変です。この記事では「解説の解説」、つまり公式解説PDFの解法を色々と補足しながらもっと丁寧に解説することを試みます。

記法

整数の2進数表記におけるビットの位置について、一番下を0番目として下から $d$ 番目のビットを単に「 $d$ ビット目」と呼ぶことにします。 $d$ ビット目は $2^{d}$ の位に相当します。

非負整数 $a, b$ のXOR演算を記号 $a \oplus b$ で表記します。

XOR演算と足し算の関係

まずはここからです。XOR演算は、繰り上がりのない足し算と思うことが出来ます。これは非負整数 $a, b$ のXOR演算と足し算それぞれについて、 $a, b$ の $d$ ビット目の組み合わせが演算結果にどう影響するかを比較してみると分かります。

$a, b$ の $d$ ビット目	$a \oplus b$ への影響	$a + b$ への影響
$0, 0$	$d$ ビット目が0になる	$d$ ビット目が0になる
$0, 1$ または $1, 0$	$d$ ビット目が1になる	$d$ ビット目が1になる
$1, 1$	$d$ ビット目が0になる	$d$ ビット目が0になり、 $d+1$ ビット目に1繰り上がる

このように繰り上がりの有無を除いて2つの演算結果は同じになります。また繰り上がりの有無の違いから、 $a \oplus b \le a+b$ が必ず成り立ちます。

この性質を用いると問題が少し考えやすくなります。 $u = a \oplus b, v = a + b$ について $u \le v$ という関係が必ず成り立つので、 $v \le N$ ならば自動的に $u \le N$ となります。これで $0 \le u, v \le N$ という条件について注意するべきは $v$ のほうだけであり、 $u$ のほうは気にしなくてもよいことが分かりました。

$(u, v)$ の数え上げから $(a, b)$ の数え上げへ

$(a, b)$ に計算を施した結果である $(u, v)$ の数え上げというものはなかなか難しいです。これを直接考えようとすると、計算結果のほうに何か特別な構造を見つけたりする必要があります。（冒頭リンク先の「シェルピンスキーのギャスケット」解はまさにそういうアプローチです）

一方、仮に $(a, b)$ のほうを数え上げ対象にしてみたらどうでしょうか。もし「非負整数の組 $(a, b)$ のうち、 $u = a \oplus b, v = a + b$ について○○な条件を満たすような組の個数がいくつあるか求めよ」という問題であれば、 $(a, b)$ について全探索を考え高速化したり、DPを回すなどの方法が取れます。できればこちらを考えたいです。

ただ実際には $(a, b)$ と $(u, v)$ は1対1に対応しないため、 $(u, v)$ の数え上げ問題を直接 $(a, b)$ の数え上げ問題に言い換えることはできません。例えばあるペア $(a, b)$ と、それに対して「 $a, b$ 間で同じ桁のビットを交換する」という操作を何度か行ったものでは、XORも和も同じ値になります。

f:id:betrue12:20190206223308p:plain

ではこの「同じ桁のビットを交換」パターン以外で、異なる $(a, b)$ から同じ $(u, v)$ ができてしまうことはあるでしょうか？結論を書くと、これはありません。それを確認します。

異なる $p_{1} = (a_{1}, b_{1}), p_{2} = (a_{2}, b_{2})$ に対してまずXORが一致、つまり $a_{1} \oplus b_{1} = a_{2} \oplus b_{2}$ になっていると仮定しましょう。このとき $p_{1}, p_{2}$ で異なっている桁のうち「同じ桁のビット交換」でないものは、必ず「片方が $(0, 0)$ でもう片方が $(1, 1)$ 」の形になっています。

f:id:betrue12:20190206222912p:plain

このときに和のほうがどうなるか考えます。 $d$ ビット目について「片方が $(0, 0)$ でもう片方が $(1, 1)$ 」という状態になっている場合、その違いによって $a_{1} + b_{1}$ と $a_{2} + b_{2}$ の間には $\pm 2^{d+1}$ の差が生まれます。これらがキレイに相殺されて $a_{1} + b_{1} = a_{2} + b_{2}$ となってしまうと同じ $(u, v)$ ができてしまうのですが、それは起こり得ません。各桁で生じる差たち $2, 4, 8, 16, ...$ からどのように選んで符号を付けても、1つ以上選んでその合計が0になることはないからです。

これで「同じ桁のビットを交換」パターン以外で、異なる $(a, b)$ から同じ $(u, v)$ ができてしまうことはないと確認できました。これまでの考察から問題を次のように言い換えることが出来ます。

非負整数 $(a, b)$ の組について、 $a+b \le N$ である組の個数を求めよ。ただし「 $a, b$ 間で同じ桁のビットを交換する」という操作を何度か行って一致するものは1個として数えることにする。

これは元の問題の数え上げ対象と1対1の対応が取れているため、正しい問題の言い換えになっています。また数え上げ対象が $(a, b)$ になっているため考えやすくなっています。

※公式解説PDFはいつの間にかこの言い換えがされていて、それが可能な理由は完全に省略されていますね…

桁DPを考える

ではこの問題を解いていきましょう。同じ桁のビットを交換したものは同一視するため、各桁ごとのビットの選び方は $(0, 0), (0, 1), (1, 1)$ のいずれかになります。桁ごとにこの3パターンの選び方があり、 $a + b$ について上限が存在する…少し変則的ですが、これは桁DPが有効であるような形をしています。

※2進数での桁DPで解ける問題はちょうど先日のABC117でも出題されたので、そちらの解説も参考にしてみてください。

基本的な考え方に従えば、「 $d$ ビット目まで上から見て、その時点で $a+b \lt N$ であることが確定している/いない選び方の数」みたいな状態を考えたくなりますが…これを普通にやると失敗します。単に1つの整数の各桁の値を決めていく場合は上の桁で上限より小さいことが確定すれば下の桁は自由に選べますが、今回の場合 $(1, 1)$ を選んだ際に繰り上がりが発生してしまうからです。

単に「 $d$ ビット目まで上から見て、その桁までの値において $a+b$ が $N$ より小さい」だけでは情報として不十分です。となれば、いくつ小さいかを具体的に持つことで桁DPができないでしょうか？

「 $d$ ビット目まで上から見て、その桁までの値において $a+b$ が $N$ より $s \times 2^{d}$ だけ小さい」ような場合の数を $dp\lbrack d \rbrack\lbrack s \rbrack$ とします。この $s$ が多ければ多いほど、下の桁で繰り上がりがあっても $N$ を超えにくくなります。また $s \lt 0$ である場合は $a+b \gt N$ であることが確定してしまうので、そのような状態には遷移しないことにします。

$dp\lbrack d+1 \rbrack\lbrack s_{d+1} \rbrack$ 、すなわち $d+1$ ビット目まで見た時点で $a+b$ が $N$ より $s_{d+1} \times 2^{d+1}$ だけ小さい状態からの遷移を考えます。ここから見る桁を1つ下ろすと $2s_{d+1} \times 2^{d}$ だけ小さいことになるので、 $s$ の値は見る桁を1つ下ろすと2倍になって引き継がれます。

ここに $N$ の $d$ ビット目と、 $(a, b)$ の $d$ ビット目として選んだ値が足し引きされます。これらをそれぞれ $n_{d}, k_{d}$ とすると、 $d$ ビット目における $s_{d}$ は

$s_{d} = 2s_{d+1} + n_{d} - k_{d}$

と計算できます。 $n_{d}$ は入力 $N$ によって決まる値であり、 $a, b$ のビットの選び方が $(0, 0), (0, 1), (1, 1)$ であることから $k_{d} = 0, 1, 2$ の3通りについてそれぞれの $dp\lbrack d \rbrack\lbrack s_{d} \rbrack$ に遷移します。

これを $s \ge 0$ の範囲で全て回せば答えを求めることが出来ます。

計算量を削減する

ただしこのDPをそのまま回すと、一番下の桁まで到達した時には $s$ は最大で $N$ と同じ値まで膨れ上がります。1つ1つ遷移を計算していては間に合いません。

ここで式を見返してみます。 $n_{d}$ は0か1、 $k_{d}$ は0, 1, 2のどれかであり、 $s_{d+1}$ は2倍されています。となると $s_{d+1}$ が十分大きいところでは $s_{d} \ge s_{d+1}$ が成り立ちそうです。

具体的には $s_{d+1} \ge 2$ であれば必ず $s_{d} \ge 2$ になります。これは「上位のある桁で $s \ge 2$ となってしまえば、後の桁をどのように選んでも以降は $s \ge 2$ がずっと保証される」ということを意味します。となると2以上であることが分かれば、その具体的な値を区別する必要はありません。

このことから、 $s$ として持つべき状態は「0」「1」「2以上」の3通りだけで良いことが分かります。ここまで状態を削ることができれば、各桁においては $s$ の3状態と $k_{d}$ の3通りの組み合わせについて遷移をすればよいので、（桁数）×9回の遷移でDPを完了することが出来ます。これで計算が間に合い、問題を解くことができました。

ACコード

（C++）Submission #4186608 - AtCoder Regular Contest 066

感想

というわけで「解説の解説」を書いてみました。公式解説の記述は半ページほどですが、ちゃんと言い換えの妥当性や具体的な遷移まで含めて書くとこれほどの分量になりますね…

私自身、この問題はABCを埋めているときにあまり深く理解をしないまま解説ACをした記憶があります。当時よりは間違いなく実力が上がっているため、今回改めてこの解説を書いてみて解法をしっかり理解できた気がします。

この記事が皆さんのACに繋がれば幸いです。読んでいただきありがとうございました！

2019-02-03

ABC117 参加記録＆解説（C, D）

AtCoder プログラミング競技プログラミング

2WAを出して169位…今回は良くなかったですね。

f:id:betrue12:20190203232047p:plain

取り急ぎC, Dの解説を。あとで書き直すかもしれません。→書き直しました（02/04）

C - Streamline

解法

※訪れるべき地点 $X_{i}$ のことを「目的地」と書くことにします。

コマ数 $N$ が訪れるべき目的地の数 $M$ 以上である場合、全ての目的地に最初からコマを置けるので答えは0です。

そうでない場合、まず $N$ 個のコマはそれぞれ異なる目的地の上に置くべきです。そうすると最初にコマを置けない目的地が $M - N$ 個あるため、「既にどこかの目的地に置いてあるコマを、まだ訪れていない目的地まで移動する」という操作を $M - N$ 回繰り返す必要があります。

1回の操作ではコマが目的地と目的地の間を移動します。各操作における移動距離の合計を最小化したいので、できるだけ近い目的地の間でコマを運ぶようにしたいです。そう考えると、隣り合う目的地と目的地の間の距離を全部調べて、その中から必要な操作回数と同じ $M - N$ 個を短いほうから選ぶ、という発想ができます。

実際にこの $M - N$ 個の区間を選んで以下のようにコマの初期位置と動き方をすると、これらの区間合計が移動距離の合計となり、これが最適です。

f:id:betrue12:20190203232945p:plain

ACコード

Submission #4161130 - AtCoder Beginner Contest 117

D - XXOR

解法

※一番下を0番目として、下から $d$ 番目のビットを単に「 $d$ ビット目」と書くことにします。 $d$ ビット目は $2^{d}$ の位に相当します。

$f(X)$ に加算される値をビットごとに考える

ビット単位のXORなので、 $f(X)$ に加算される値をビットごとに分解して考えます。

与えられた $N$ 個の $A_{i}$ についてそれぞれの $d$ ビット目を全部見て、0であるものが $n_{d, 0}$ 個、1であるものが $n_{d, 1}$ 個あったとします。このとき

$X$ の $d$ ビット目を0にすると、 $A_{i}$ それぞれの $d$ ビット目はそのままなので、 $n_{d, 1} \times 2^{d}$ が $f(X)$ に加算される。
$X$ の $d$ ビット目を1にすると、 $A_{i}$ それぞれの $d$ ビット目が全て反転するので、 $n_{d, 0} \times 2^{d}$ が $f(X)$ に加算される。

となります。このうち大きいほうを採用していきたいですが、 $X \le K$ という条件により $X$ の各ビットは自由に決めることが出来ません。またビットごとに独立に決めていくことも無理そうです。

桁DPとは

このように「ある値 $X$ の各桁の値に注目して最適値探しや数え上げを行う。ただし $X$ には上限がある。」という形式の問題を解く有効な方法として「桁DP」というものがあります。

桁DP入門 - ペケンペイのブログ

これは「上から○桁目まで見て、その途中の状態が○○であるようなものの個数/最大値/最小値など」を状態に持って、桁を1つずつ進みながらDPをしていくものです。「桁」というのは10進数の桁であることが多いですが、今回のような2進数でももちろん使えます。

今回は桁DPというほど大袈裟なものではないですが、大切なのは

上位の桁（今回はビット）から決めていく
「 $X$ が上限 $K$ よりも小さいことが確定しているか？」をフラグとして持った状態を考える

ということです。特に2について詳しく説明していきます。

$X$ のビットを上から決めていく場合、 $X$ が $K$ を超えてしまうのは下の図のようなときです。今まで見たビット全てにおいて $X$ と $K$ が一致していて、 $K$ のビットが0である場合、 $X$ のビットとしてはどんなに損でも0を選ぶしかありません。

f:id:betrue12:20190204201311p:plain

一方、今まで見てきたビットのどこかで「 $K$ が1なのに、 $X$ が0である」という選び方をしたとします。そうすると上位ビットで $X$ のほうが小さくなっているため、その先 $X$ の各ビットをどのように決めても $X \lt K$ が保証されます。これが「 $X$ が $K$ よりも小さいことが確定している」状態です。

f:id:betrue12:20190204201544p:plain

これをまとめると、

ビット目まででがよりも小さいことが確定していない状態から遷移するとき…
- もしのビット目が1であれば…
  - $X$ の $d$ ビット目として1を採用すると、そのまま確定していない状態に遷移する。
  - $X$ の $d$ ビット目として0を採用すると、確定している状態に遷移する。
- もしのビット目が0であれば…
  - $X$ の $d$ ビット目としても0を採用するしかない。そのまま確定していない状態に遷移する。
ビット目まででがよりも小さいことが確定している状態から遷移するとき…
- $X$ の $d$ ビット目は自由に選んで良いので、 $f(X)$ への加算値が大きくなる方を取り、確定している状態に遷移する。

「遷移前で確定しているかどうか」「 $K$ のビットは何か」「 $X$ のビットとして何を選ぶか」の3条件があり、入れ子になっていてややこしいかもしれませんね。1つ1つのパターンそれぞれについて、どうしてそうなるのか考えてみるのが良いと思います。

これが桁DPの基本となる思考パターンで、10進数の場合でも選択肢は多くなりますが考え方は同じです。あとはこれをDPの実装に落とし込めば解くことができるので、続きはコードを参照していただければと思います。

ACコード

Submission #4173561 - AtCoder Beginner Contest 117

※桁DPに見えるような実装に差し替えました。

実装について少し補足です。

制約の $10^{12}$ が $2^{40}$ より小さいので、39ビット目から順に見るようにしています。
最大化問題なので、初期状態以外のDPテーブルは $-\infty$ で初期化したいです。この実装だと合計で最悪 $N \times 2^{39+1}$ くらいの値が足されてくるので、実装上の $\infty$ はそれより大きい値としておく必要があります。あまり上のビットから回し始めると $-10^{18}$ で初期化しても足りなかったり、そもそも計算途中の値で64ビット整数型でオーバーフローが起こってしまう可能性があるので、そこは注意です。

2019-01-28

NIKKEI Programming Contest 2019 参加記録＆解説（A～E）

AtCoder プログラミング競技プログラミング

Dまでがまずい感じでしたが、無事Eを通して予選突破！

f:id:betrue12:20190128201220p:plain

A～Eの5問を振り返ります。

A - Subscribers

解法

最大値については、新聞 $X, Y$ を取る人をなるべく被らせたいので $\min(A, B)$ が答えです。

最小値については、新聞 $X, Y$ を取る人をなるべく被らせたくないので、 $A+B$ が $N$ 以下であれば0。 $N$ を超えている場合はどうしても $A+B-N$ 人は被ってしまうので、これが答えです。

ACコード

（Ruby）Submission #4096948 - 全国統一プログラミング王決定戦予選/NIKKEI Programming Contest 2019

Touitsu

B - Touitsu

解法

同じ位置（インデックス）の文字3つを比較し、これらを全て一致させるための操作回数を考えます。全部同じであれば0回、2つだけが同じであれば1回、全て違っていれば2回の操作回数が必要です。これを全インデックスについて足し合わせると答えになります。

ACコード

（Ruby）Submission #4097798 - 全国統一プログラミング王決定戦予選/NIKKEI Programming Contest 2019

C - Different Strokes

解法

こういった問題を考える上では、まず「2つの要素があったとき、取るべきなのはどちらか」を考えるとよいです。より汎用的には「2つの要素を交換したらどうなるか？」と言うこともできます。

仮に料理が番号 $1, 2$ の2つしかなくて、今が高橋くんのターンだとします。高橋くんが1を取ると青木さんが2を取り、高橋くんの利得は $A_{1} - B_{2}$ です。高橋くんが2を取り青木さんが1を取ると、高橋くんの利得は $A_{2} - B_{1}$ です。

このことから、高橋くんが2よりも1を取ったほうが良い条件は $A_{1} - B_{2} \ge A_{2} - B_{1}$ と定式化され、これを移項して料理1の要素と料理2の要素に分離すると $A_{1} + B_{1} \ge A_{2} + B_{2}$ となります。この条件が満たされるとき、高橋くんは料理2よりも料理1を取るべきです。

一方青木さんのターンで同じことを考えると、やはり同様に $A_{1} + B_{1} \ge A_{2} + B_{2}$ のとき青木さんは料理2よりも料理1を取るべきだという結果になります。

この結果を一般化すると、高橋くん・青木さんどちらも「残っている料理の中で $A_{i} + B_{i}$ が最大のものを取る」という戦略が最適であることが分かります。料理の総数が一般の $N$ 個であっても、もし $A_{i} + B_{i}$ が最大のものを取らない場合は、相手にそれを取られてより損をしてしまうからです。

あとはソートしてシミュレーションすれば高橋くんの利得が求められます。この問題のように複数の料理にまたがるような利得がない場合は、2つの要素で比較した結果を要素数 $N$ のときに一般化する、という解法が有効であることが多いです。

ACコード

D - Restore the Tree

解法

まずは根を探したいです。元の根付き木の性質として、根の入次数は0であり、それ以外の頂点の入次数は1です。さらに書き加えた辺は先祖から子孫に伸びているため、根に辺が向いていることはありません。そのため頂点の中で入次数が0である頂点はちょうど1つ存在するはずで、それが根です。

根が見つかったら、元からあった木を復元します。このとき書き加えた辺が先祖から子孫に伸びていて、また制約から多重辺がないので、書き加えた辺は元の木を「ショートカット」するように生えているはずです。以下は入力例2に対応するグラフですが、赤で記載した追加辺は確かにショートカットになっています

f:id:betrue12:20190128210448p:plain

このことから根から各頂点への最長経路を辿っていけば、そのときに通った経路が求めたい木であり、遷移元を記録しておけば出力すべき「各頂点の親」を求めることが出来ます。

DAG（閉路のない有向グラフ）における最長経路問題は、トポロジカルソート順でDPをすることで解けます。こちらの資料が分かりやすいです。

動的計画法入門(An introduction to Dynamic Programming)

ACコード

（C++）Submission #4104614 - 全国統一プログラミング王決定戦予選/NIKKEI Programming Contest 2019

E - Weights on Vertices and Edges

解法

問題文の通りに考えると、以下のような操作をすればよいです。

最初はグラフが連結なので、全ての頂点の重み和を計算し、それを超える重みの辺を削除する。
これによって連結成分が分断されてしまった場合、各連結成分の頂点重み和は減ってしまうので再計算をする。それぞれの連結成分ごとに、頂点重み和を超える重みの辺はやはり削除する。
これを全ての辺が削除されなくなるまで繰り返す。

ただしこれを処理しようとすると、連結成分の分断を考える必要があり面倒です。

そこで処理を逆から考え、辺がない状態から始めて使う辺をなるべく多くすることを目指します。辺を追加していく方向で考えると、連結成分の分断ではなくて併合を扱うのでUnion-Findを利用することが出来ます。

辺を追加していく場合、どのような順序で辺を考えていけばよいでしょうか。辺が追加されることで連結成分が広がり条件が緩くなるので、それぞれの辺を独立に考えることはできません。また「1本辺を追加するごとに、他の辺を追加できるようになったかを1本1本判定する」等のアルゴリズムでは間に合いません。

ここで問題文の条件に注目すると、連結成分の頂点重みの和が、その連結成分で一番重い辺以上であればよいということが書いてあります。そのため、ある重み $w$ 以下の辺だけで構成される連結成分1つの頂点和が $w$ 以上であるときには、その辺たちは全て使って良いことが分かります。

このことから、以下のような手順で使う辺を決めていくことが出来ます。

Union-Findを用意し、辺の重みが小さい順に辺を「仮で」追加し、頂点を併合していく。この追加は、必ずしもこの辺が使えるということを意味しない。
もし重み $w$ の辺を追加したときに、Union-Findにおいてその辺が属する連結成分の頂点重み和が $w$ 以上だったとする。このとき辺の重みが小さい順に追加しているので、その連結成分に含まれる辺の重みは全て $w$ 以下であり、先ほどの考察よりその連結成分に今まで追加した辺を全て使うことができる。
この操作を、全ての辺を追加し終わるまで続ける。

この手順で使う辺を決めてしまえば、使えなかった辺の数が答えになります。

手順の2. で「その連結成分の頂点重み和を取り出す」「その連結成分に今まで追加した辺の本数を取り出す」という処理が必要になりますが、これはUnion-Findに今まで追加した頂点の重み和や辺の本数を記憶させておくことで実現することが出来ます。連結成分のサイズを持たせておく実装はよくあると思いますが、それと要領は同じです。