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

今回は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})$ で答えが求められます。