2018-12-24

CADDi 2018　参加記録＆解説（C～E）

2問速解きでレート微増。悪くはないけど良くもない。

f:id:betrue12:20181223010458p:plain

C - Product and GCD

解法

各素因数ごとに考えてみます。

ある素数 $p$ について、各 $a_{i}$ ごとに「 $a_{i}$ には素因数としていくつ $p$ が含まれているか？」を考えます。その個数の最小値を $m_{p}$ とすると、 $\gcd(a_{1}, ..., a_{N})$ には $p$ が $m_{p}$ 個含まれます。

$a_{i}$ の積 $P$ が与えられているので、素数 $P$ に素数 $p$ がいくつ含まれているかは素因数分解で計算できます。この個数を $n_{p}$ 個として $N$ 個の要素に分配するとき、なるべく最小個数が大きくなるようにするには均等に分配するとよいです。結果として、最適に分配したときには $m_{p} = \lfloor\frac{n_{p}}{N}\rfloor$ となります。

そのため $P$ を素因数分解して、各素因数 $p$ ごとに $\gcd(a_{1}, ..., a_{N})$ に含まれる個数 $m_{p}$ を求め、全て掛け算すると答えが求められます。

ACコード

（C++）Submission #3838299 - CADDi 2018
（Ruby）Submission #3851808 - CADDi 2018

D - Harlequin

解法

結論は公式解説にある通りなので、ちょっと別のことを書きます。

ゲームの問題の解き方は「Grundy数を計算する」「遷移を考えてDP」「実験してエスパー」など色々タイプがありますが、

まず初手で「必勝状態」に持っていって、それ以降は相手の行動の真似をしたり打ち消したりするような操作を取り続けることで必ず勝てる

という視点で考えると解ける問題がけっこうあります。

ちょっと抽象的なので、今回の問題よりも簡単な具体例を出してみます。

（例）石取りゲーム

全部で $n$ 個の石がある。各プレイヤーは交互に、 1, 2, 3個のいずれかの個数で石を取る。最後に石を取った人が勝ち。

というゲームを考えます。

このゲームには必勝法があり、

まず、自分のターンの終了時に石が4の倍数である状態にする。これが「必勝状態」である。
相手が石を個取った場合、自分は石を個取る。
- 取れる石の個数が1, 2, 3個なので、これは必ず可能。
- このように立ち回ると、必ず自分のターンの終了時には石が4の倍数になっている。
これを繰り返すと、自分のターンの終了時に石が0個になるので、勝ち！

というのが必勝法です。このときの勝敗は

$n$ が4の倍数でないときは、先手が初手で4の倍数にできるので勝ち
$n$ が4の倍数でないときは、先手が初手で4の倍数にできないので、後手に必勝法を取られて負け

となります。「相手が何をしても、必勝状態に戻せる」というふうに、必勝状態と戦略を選ぶのが一番のポイントです。

今回の問題の場合

この考え方にあてはめて今回の問題を考えてみると、

リンゴの数が全部偶数である状態が「必勝状態」。
必勝状態から相手がリンゴを食べた直後は奇数のリンゴが必ずあるので、奇数のリンゴを全部1個ずつ食べることで必勝状態に戻せる。

という発想をすることができます。

もちろん最初に小さい数で実験をしてみることはとても効果的です。実験で思いついた仮説を証明するときに、この「必勝状態を保つ」という考え方のパターンを知っておくとちゃんと証明できることがあります。

蟻本に詳しく解説がありますが、Grundy数も理論としてはこの考え方の発展です。ただGrundy数を扱うような問題は、その性質は単に知識として使ってしまうことが多いですね。

ACコード

（C++）Submission #3840089 - CADDi 2018
（Ruby）Submission #3852513 - CADDi 2018

E - Negative Doubling

解法

負と正の区切り位置に注目する

$A_{1} \le A_{2} \le \cdots \le A_{N}$ となっている数列は、左側に負の数が、右側に正の数が集まっていて、それぞれ外側に行くほど絶対値が大きくなっています。この区切り位置を全探索することにします。

まず区切り位置より右側だけを考えます。この範囲の数は正である必要があるので、「-2倍」という操作をする回数は必ず偶数です。そのため、「4倍する」という操作に置き換えてしまい、後で回数を×2することにします。

区切り位置が $A_{i-1}, A_{i}$ の間にある場合、右側で成り立って欲しい条件は $A_{i} \le A_{i+1}\le \cdots \le A_{N}$ です。これを満たす操作回数を求めたいですが…区切り位置は全部試すので、全ての $i$ についてこれを求める必要があります。

DPを考える

$A_{i} \le A_{i+1}\le \cdots \le A_{N}$ が成り立つための最小操作回数を $dp\lbrack i \rbrack$ として後ろからDP、つまり $dp\lbrack i+1 \rbrack$ から $dp\lbrack i \rbrack$ を更新するDPができそうな気がします…が、これだけでは情報として不十分です。

f:id:betrue12:20181224024851p:plain

この図に2つ例示したように、 $A_{i+1}$ を増やしたときに、さらに右側の要素を「道連れ」で増やさなければいけないかもしれません。この情報が得られないと、何回追加で操作をしなければいけないかが求められません。

ではどうすればいいかというと、DPの情報を増やします。「 $A_{i}$ に $j$ 回操作をした上で、 $A_{i} \le A_{i+1}\le \cdots \le A_{N}$ が成り立つための最小回数」を $dp\lbrack i \rbrack\lbrack j \rbrack$ とします。このように情報を持ち、 $dp\lbrack i \rbrack\lbrack j \rbrack$ を求めるときには $A_{i+1}$ 以降の追加操作は行わないと決めてしまえば、先ほどのような理由で情報が不足することはありません。

具体的に $dp\lbrack i \rbrack\lbrack j \rbrack$ を求めるときには、 $A_{i} \times 4^{j} \le A_{i+1} \times 4^{k}$ を満たすような全ての $k$ について $dp\lbrack i+1 \rbrack\lbrack k \rbrack$ からの遷移を計算し、その中で一番良いものを採用すればよいです。

これで操作回数の計算は正しくできますが… $j$ の値は実際にはとても多くなってしまう可能性があり、これだと間に合いません。もうひと工夫考える必要があります。

操作回数の多いところをサボる

先ほどの「道連れ」で操作回数が増えるかどうか分からないという問題は、その時点で $A_{i+1}$ と $A_{i+2}$ がどれだけ離れているか分からない、ということが原因です。 $A_{i+2}$ が $A_{i+1} \times 4$ 以上であれば、 $A_{i+1}$ を4倍しても道連れは必要ありません。

ただし、既に $A_{i+1}$ がとても大きい場合はどうでしょうか。 $A_{i+1}$ が全要素の初期値より大きくなってしまっている場合、感覚的に言うと $A_{i+1}$ 以降の要素は「だいたい同じ高さに均されてしまっている」と思うことができます。その状態で $A_{i+1}$ にさらに1回の操作を加えると、それ以降の全要素も1回ずつ必ず道連れされることになります。

そう考えると、操作回数 $j$ がある一定以上を超えてしまった場合

$dp\lbrack i+1 \rbrack\lbrack j+1 \rbrack = dp\lbrack i+1 \rbrack\lbrack j \rbrack + (i+1番目以降の要素数)$

という性質が成り立ちます。これを用いると、実際のDPテーブルは $j$ が小さいところだけ計算しておいて、大きいところはこの式で求めることができます。

具体的には $\frac{A_{i+1}}{A_{i+2}} \le 10^{9} \lt 4^{15}$ なので、15回より上は先ほどの性質が成り立ちます。ここまで絞れば計算量がかなり落ち、現実的に間に合うくらいになってきます。

逆向きも計算して答えを求める

元々やりたいことは「負と正の区切り位置を全探索して、負と正それぞれの操作回数を考える」ことでした。

正のほうはこれまで見てきたようにDPで計算できます。そして負のほうは、負の範囲の要素全てにまず-2を掛けてから、絶対値が左側ほど大きくなるように左からDPをしていくことができます。この実装は、reverseなどで数列を反転させて正のときと同じコードを通すのが断然オススメです。

両方の計算が終わったら、区切り位置を全部見て操作回数を求め、その一番良いものを出力すればよいです。

ACコード

（C++）Submission #3852419 - CADDi 2018

2018-12-17

Codeforces Avito Cool Challenge 2018 参加記録＆解説（A～E）

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

プレテスト5完だったのですが、Dがしょうもない実装ミスで落ちました…

f:id:betrue12:20181217033706p:plain

A～Eまで5問振り返ります。

A. Definite Game

Problem - A - Codeforces

問題概要

正整数 $n$ の初期値 $v$ が与えられる。これに以下の操作を0回以上繰り返して、 $n$ をできるだけ小さな数にしたい。その数を求めよ。

$x \lt n$ かつ $x$ が $n$ の約数でないような正整数 $x$ を選び、 $n$ から $x$ を引く。

制約

$1 \le v \le 10^{9}$

解法

$v = 1, 2$ のときは条件を満たす $x$ が存在しないので一度も操作を行えません。

$v \ge 3$ のとき、 $x = v-1$ は条件を満たすのでこれを選ぶと $n = 1$ にすることができて、これが最小です。

つまり $v = 2$ のとき答えは2、そうでないとき答えは1になります。

ACコード

Codeforces

B. Farewell Party

Problem - B - Codeforces

問題概要

$n$ 人の人が、 $1, ..., n$ で番号付けされた $n$ 種類の帽子のうちどれかを被っている。ここで各人 $i$ について、その人と違う種類の帽子を被っている人は $a_{i}$ 人である。

このような条件を満たす帽子の割り当て方を1つ求めるか、割り当て方が存在しないことを判定せよ。

制約

$1 \le n \le 10^{5}$
$0 \le a_{i} \le n-1$

解法

同じ帽子を被っている人は $a_{i}$ の値が同じになっていて、かつその帽子を被っている人はちょうど $N - a_{i}$ 人います。そのため各人を $a_{i}$ の値ごとに分類しておき、人 $i$ を順番に見ていって

人 $i$ の帽子が未割り当てのとき、 $a_{i}$ の値が同じ人を人 $i$ 含めて $N-a_{i}$ 人適当に選び、その人達に同じ帽子を割り当てる

という操作を繰り返すことで帽子を割り当てていくことができます。割り当てるための人数が足りなくなってしまった場合は、割り当てが不可能と判定して終了します。

ACコード

Codeforces

C. Colorful Bricks

Problem - C - Codeforces

問題概要

一列に並んだ $n$ 個のレンガを $m$ 色のペンキで塗り分ける。このとき、隣り合うレンガ間で色が異なるような場所がちょうど $k$ 個あるような塗り方の総数を求め、 $998244353$ で割った余りを出力せよ。

制約

$1 \le n, m \le 2000$
$0 \le k \le n-1$

解法

「 $i$ 番目のレンガまでの塗り方で、それまででレンガ間の色が異なる箇所が $j$ 個であるような塗り方の総数」を $dp\lbrack i \rbrack\lbrack j \rbrack$ とします。 $dp\lbrack n \rbrack\lbrack k \rbrack$ が答えです。

最初のレンガの塗り方は $m$ 通りなので $dp\lbrack 1 \rbrack\lbrack 0 \rbrack = m$ 、そこからの遷移は「前と色が同じ」塗り方が1通りで「前と色が異なる」塗り方が $m-1$ 通りなので

$dp\lbrack i+1 \rbrack\lbrack j \rbrack$ += $dp\lbrack i \rbrack\lbrack j \rbrack$
$dp\lbrack i+1 \rbrack\lbrack j+1 \rbrack$ += $(m-1) \times dp\lbrack i \rbrack\lbrack j \rbrack$

となります。 $O(NK)$ が間に合うのでこれで解けます。

ACコード

Codeforces

D. Maximum Distance

Problem - D - Codeforces

問題概要

$n$ 頂点 $m$ 辺の重み付き無向グラフが与えられる。辺 $i$ の重みは $w_{i}$ である。

このグラフにおける経路の「コスト」を、その経路の最も重い辺の重みと定義する。そして頂点同士の「距離」を、頂点間を結ぶ経路のコストの最小値とする。

頂点のうち $k$ 個の頂点が「特別な頂点」として指定される。それぞれの特別な頂点について、最も「遠い」特別な頂点との距離を求めよ。

制約

$2 \le k \le n \le 10^{5}$
$n-1 \le m \le 10^{5}$
$1 \le w _{i} \le 10^{9}$
グラフは連結であるが、単純とは限らない

解法

頂点同士の距離が $d$ 以下であることは、重み $d$ 以下の辺だけを使って頂点間が連結となることと同値です。

まずグラフから全ての辺を取り去り、重みの小さい辺から順にグラフに足していくことを考えます。この操作において頂点同士が連結になったとき、最後に追加した辺の重みがその頂点間の距離となります。

つまり各特別な頂点について最も遠い特別な頂点は、一番最後に連結になったものです。結局は、全ての特別な頂点が連結になったときに全頂点にとってそれぞれ最も遠い頂点と連結になり、そのとき最後に追加した辺の重みが全ての頂点についての答えになります。

あとは、辺を追加して端点同士を連結にしていく操作をUnion-findで実装します。「全ての特別な頂点が連結になった」という判定が少し難しいですが、Union-Findの連結成分に「その連結成分に含まれる特別な頂点の個数」を管理する機能を持たせ、その値が $k$ になればOKという判定をするのが楽だと思います。

ACコード

Submission #47165529 - Codeforces

E. Missing Numbers

Problem - E - Codeforces

問題概要

正の偶数 $n$ が与えられる。数列 $x_{1}, ..., x_{n}$ のうち偶数番目の要素が与えられる。

このとき奇数番目の要素の選び方で、以下を満たすものを1つ求めよ。またはそのような要素の選び方が存在しないことを判定せよ。

$1 \le x_{i} \le 10^{13}$
各 $t$ について、 $x_{1} + \cdots + x_{t}$ は平方数となる。

制約

$2 \le n \le 10^{5}$ であり $n$ は偶数
与えられる偶数番目の要素は、 $1 \le x_{i} \le 2\times 10^{5}$

解法

平方数 $x_{1} + \cdots + x_{t}$ の正の平方根を $a_{t}$ と表すことにします。この値は整数です。また $x_{i}$ が全て正であることから、 $a_{1}, ..., a_{n}$ は狭義単調増加になっています。

この最大値 $a_{n}$ がどこまで大きくなり得るか考えてみます。 $x_{n} = a_{n}^{2} - a_{n-1}^{2}$ であり、 $a_{n-1} \le a_{n} - 1$ を用いて式変形すると

$a_{n} \le \frac{x_{n}+1}{2}$

という不等式を得ることができます。制約から $x_{n} \le 2\times 10^{5}$ なので、 $a_{n}$ が整数であることも考慮すると $a_{n} \le 10^{5}$ となり、そんなに大きな値にならないことが分かります。

次に、奇数番目の要素 $x_{2k+1}$ をどのように決めればよいか考えます。1つ前までの要素和が $a_{2k}^{2}$ であるとき、 $x_{2k+1}$ を適切に選ぶことによって、 $a_{2k} \lt a_{2k+1}$ である任意の $a_{2k+1}$ を実現することが出来ます。具体的には $x_{2k+1} = a_{2k+1}^{2} - a_{2k}^{2}$ とすればよいです。

もちろんその次の要素 $x_{2k+2}$ は与えられているので、 $a_{2k+1}^{2} + x_{2k+2}$ が平方数となるようなものを選ばなければいけません。その条件内でなるべく小さいものを選んだほうがその後の選択肢が多くなります。

そのため、各奇数番目の要素 $x_{2k+1}$ を決めるにあたって、

$a_{2k+1}$ の候補として、1つ前の値 $a_{2k}$ より大きい値を小さい方から順に $a_{2k}+1, a_{2k}+2, ...$ と試す。
もし $a_{2k+1}^{2} + x_{2k+2}$ が平方数となるような $a_{2k+1}$ が見つかれば、その値を採用して $x_{2k+1} = a_{2k+1}^{2} - a_{2k}^{2}$ とする。
その値を採用したときの $a_{2k+1}^{2} + x_{2k+2}$ の平方根が $a_{2k+2}$ となるので、これを用いて次の $a_{2k+3}$ を同じ手順で求める。

というように、前から順番に値を決めていくことが出来ます。

この過程において調べる $a_{2k+1}$ の値は、試行を1回行うごとに少なくとも1増えます。先ほど見たように $a_{n} \le 10^{5}$ なので、多くとも合計で $10^{5}$ 回の試行を行えば、最後まで値を求め終わるか、または解が存在しないことが分かります。計算量の面でも十分間に合います。

ACコード

Submission #47165496 - Codeforces

ある整数が平方数かどうかを誤差を気にせずに求めるのは少し面倒ですが、今回の問題では取り得る値が限られていて計算量にも余裕があるので、この実装では「平方数→その平方根」の対応を集めたmapを作ってしまっています。

2018-12-16

AGC029 参加記録＆解説（A～D）

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

AtCoder Grand Contest 029 - AtCoder

今回は4完！完答数で言うと自己ベストです。配点が低めでペナルティ込みの時間がかなり遅いので、パフォーマンスはそんなに高くないですが…

f:id:betrue12:20181216004313p:plain

A～Dを振り返ります。

A - Irreversible operation

解法

この操作は「白石を1つ左にずらす」という操作に相当します。これ以上ずらせない、すなわち「白白白...白黒黒黒...黒」のような状態になるまで操作を繰り返すことができます。

この状態にするまでの操作回数を考えましょう。左端を0とする座標をとって「白石の座標値の合計」を考えると、白石を左に1つずらす操作を1回するたびにこの値は1減ります。そのため、

操作前の白石の座標合計：与えられた入力をもとに計算
操作後の白石の座標合計：白石を $k$ 個とすると $0 + 1 + \cdots + (k-1)$

をそれぞれ計算して、これらを引き算すると答えが出ます。

もしくは、この値は「転倒数」とみなすことができるので、転倒数を求める要領で左から計算する方法もあります。この場合は初期状態の各白石について「それより左側にある黒石の個数」を数えて全部足し算すればよいです。どちらでも $O(|S|)$ で計算できます。

ACコード

（Ruby、合計の差）Submission #3805088 - AtCoder Grand Contest 029
（Ruby、転倒数）Submission #3793082 - AtCoder Grand Contest 029

B - Powers of two

解法

結論を言ってしまうと「大きい方からペアの候補を探していってマッチングを作るのが最適」となります。これを証明します。

まず、与えられた数のうち一番大きい値を取ってきてその値を $x$ とします。 $x$ とペアになる候補として $y$ を取ったとして、和を $s = x+y$ とします。

このとき $1 \le y \le x$ であることから $x+1 \le s \le 2x$ です。そして作りたい2冪の値 $1, 2, 4, 8, ...$ のうち、この範囲に入っているものは1つしかないことが証明できます。隣り合う2冪の値の比は2ですが、 $x+1$ と $2x$ の比は2未満だからです。

そのため $x$ とマッチングできる数は1種類だけに定まります。このときマッチング相手がいるのに「マッチングをしない」という選択をしてしまうと、 $x$ は以降どの数ともマッチングができずに残るので

$x$ とマッチングできる候補 $y$ が $x$ 以外の値とマッチングできないとき、マッチングをしないのは単純に損である。
$y$ が $x$ 以外にマッチング相手を持っている場合、足し引き0になって損をしない可能性はあるが、得をすることはない。

と、マッチングをしないことに得がありません。マッチングが作れる場合は作ってしまうのが最適になります。

$x$ の次に大きい値を見るときには、同じようにこれを「一番大きい数」として考え、同じように処理して大丈夫です。たとえ $x$ が残っていたとしても、その $x$ はどの数ともマッチングできないので無視してよいからです。

これを全ての値について繰り返すと答えが求められます。「ペアになる候補の値が存在するか？」という判定が必要になるので、mapなどで各値の個数を管理するとよいですね。mapを使うと全体計算量は $O(N\log N)$ になります。

ACコード

（C++）Submission #3794721 - AtCoder Grand Contest 029

C - Lexicographic constraints

解法

まずは二分探索することを考えます。文字の種類数 $K$ を固定し、「 $K$ 種類の文字で与えられた条件を満たすことができるか？」のYes/No問題を考えます。 $N$ 種類あれば絶対に条件を満たせるので、初期条件は $ng=0, ok=N$ とすることができて、反復回数は $O(\log N)$ 回です。以降、Yes/No問題を考えていきます。

最適な文字列の作り方を考える

$i$ 番目の文字列を $S_{i}$ と表記します。その長さは $A_{i}$ です。

この次の文字列 $S_{i+1}$ は次のように作るのが最適です。

のとき、の後にを繋げたもの。
- 例： $S_{i} = abc$ 、 $A_{i+1} = 5$ とすると、 $S_{i+1} = abcaa$
のとき、の文字目までを「1つ繰り上げた」もの。
- 例： $S_{i} = abc$ 、 $A_{i+1} = 2$ とすると、 $S_{i+1} = ac$

「1つ繰り上げる」という操作は整数の桁の繰り上がりに似ていて、 $K = 3$ で文字数が2の場合は

$ab \to ac \to ba \to bb \to bc \to ca \to...$

のような要領で繰り上がっていきます。

そのため発想として、「 $K$ 種類の文字からなる文字列を $K$ 進数の整数のようにみなして繰り上がり等をシミュレートし、一番上の桁が溢れなければOK」というようにYes/No問題を解くことを考えます。

ただそのまま整数で実装すると $K$ 進数で $10^{9}$ 桁の値を考えないといけないので、多倍長整数でもとても無理です。これを工夫して実装する必要があります。

※下の方の桁ほど答えに影響しづらいので、私は本番では「ある長さ以上のところの変化は無視する」という方法で通してしまいました…64bit変数2つでなんちゃって多倍長を作り、 $K^{d}$ がだいたいギリギリ128bit整数になるくらいまで桁数 $d$ を取るとジャッジは通りますが、恐らくhack可能です。提出コードはこれです。

文字列の効率的な持ち方

どうするのかというと、文字列で言うと $a$ でない、つまり $K$ 進数でいうと $0$ でないところだけの情報を持ちます。例えば

$S_{i} = aaabcaab$

という文字列は、 $a$ でないところだけを $(桁, 文字を数値化した値)$ と表現したものを集めて

$S_{i}^{\prime} = \lbrace(4, 1), (5, 2), (8, 1)\rbrace$

という風に持ちます。桁については一番最初の文字を1桁目、文字については $a$ を0文字目としています。

このように管理した文字列に対して、先ほどの操作をそれぞれどのように行えばよいかを考えます。

の後ろに、長さがになるまでをある個数追加する
- $a$ は情報として持たなくて良いので、何もしなくてよい。
を長さがになるまで削る。
- $S_{i}^{\prime}$ の末尾を、インデックスが $A_{i+1}$ 以下になるまで削る。
を1つ繰り上げる。
- 整数の繰り上がりと同様に、末尾から順に「値が $K$ になったらゼロにして1つ上の桁に1加算する」という処理を行う。

という風に各操作を行うことができます。

あとはこれを効率的に実現できるように $S_{i}^{\prime}$ の持ち方を考えます。単純にmapでもよいですし、末尾にしか操作をしないことに着目するとstackを用いてもよいです。

計算量について

ちょっと計算量の解析が面倒ですが、やってみます。以降、 $K \gt 1$ とします。

まずは繰り上がり処理において、値を追加する回数の合計がどれくらいになるか？を考えます。繰り上がりが多く起こる場合というのは、例えば $S_{i}^{\prime} = \lbrace(1, K-1), (2, K-1), (3, K-1), (4, K-1)\rbrace$ となっていて、その末尾に1加算するようなときです。

このような現象が頻繁に起こってしまっては計算量が多くなってしまいますが…今回の場合、 $S_{i}^{\prime} = \lbrace(1, K-1), (2, K-1), (3, K-1), (4, K-1)\rbrace$ のような状態を「効率的に作る」ことができません。4桁目に1を足すという操作を地道に $K^{4}-1$ 回繰り返すことでしかこのような形は作れません。

一般的に言うと、 $K^{d}$ 回の操作で $000000...0$ から始まって $1000000...0$ （ $d+1$ 桁）への繰り上がりが実現できます。この時各桁に値を追加する回数の合計は、

上から1桁目：1
上から2桁目： $K$
...
上から $d+1$ 桁目： $K^{d}$

となり、その和は $\frac{K^{d+1}-1}{K-1}$ です。これはおよそ操作回数 $K^{d}$ の $\frac{K}{K-1}$ 倍になっていて、つまり操作回数の2倍で抑えることができます。操作回数は合計で $N$ 回なので、値を追加する回数の総数も $O(N)$ で抑えることができます。

次に末尾の要素を削る処理です。要素を削るためには、それより前に要素が追加されている必要があります。先ほど見たように値の追加回数は $O(N)$ で抑えられているので、削る回数の合計も $O(N)$ で抑えられます。

以上の考察によって、 $S_{i}^{\prime}$ に対して変更を加える回数の合計は $O(N)$ となります。もしstackを使っていれば1回の変更は $O(1)$ 、そして二分探索の反復回数が $O(\log N)$ なので、全体計算量 $O(N \log N)$ が達成できます。もしmapを使えばもう1つ $\log N$ が付きますが十分間に合うと思います。

※ $K = 1$ のときは1回でも繰り上がりが起こってしまうとその時点でアウトなので、上の解析によらず最悪でも $O(N)$ で判定できます。また答えが1になるのは $A_{i}$ が狭義単調増加である場合だけなので、二分探索を回す前に狭義単調増加であるかだけを調べてしまってもよいですね。

ACコード

（C++）Submission #3806921 - AtCoder Grand Contest 029

D - Grid game

解法

「2回連続で駒が動かされなかったら終了する」ので、高橋くんは動かし続けるしかありません。逆に青木くんはなるべく早く駒を動かせない状態に持っていきたいです。高橋くんが駒を動かせない状態というのは、駒の下のマスに障害物または外壁がある状態です。青木くんはなるべく早く障害物に「上から」駒をぶつけてしまいたいです。

まず、青木くんが常に駒を動かせるような場合を考えてみます。

f:id:betrue12:20181216021942p:plain

青木くんが常に駒を動かせる場合、上の図のように考えることで、下のマスに行くほど青木くんが駒を操作できる横の範囲が広がります。水色の範囲内で最も上にある障害物を探すことで答えが求められます。

ただ青木くんが常に駒を動かせるとは限りません。以下の図のような場合を考えてみましょう。

f:id:betrue12:20181216023138p:plain

この図のように、青木くんが右に動こうとしたときに障害物にぶつかってしまうことがあります。この時は駒を操作できる範囲を広げることはできません。

このように、列（行でもいいです）を1つずつ見ていきながら、青木くんがどの範囲の障害物にぶつけられるかを考えていくことで答えを求めることができます。

ACコード

（C++）Submission #3800715 - AtCoder Grand Contest 029

実装ですが、障害物を行または列ごとにまとめて管理し、ソートして順番に見ていくとよいでしょう。コード中の loss が、障害物のせいで青木くんが範囲を広げられなかった回数を示しています。

2018-12-08

ABC115 参加記録＆解説

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

19分台全完で25位。20分切れたのは良いですね。

f:id:betrue12:20181208225414p:plain

A - Christmas Eve Eve Eve

解法

入力が4通りしかないので全部ifで分岐してもよいのですが、まず Christmas を出力して、 $25-D$ 回だけ [半角スペース]Eve を出力するとスマートです。

ACコード

B - Christmas Eve Eve

解法

一番高い商品を半額にするのが最適です。そのため、

ソートして、最も高い商品を半額にして、合計する
最も高い商品の値段を調べて、元々の全商品の合計からその半額を引く

などの方法で解くことができます。

ACコード

C - Christmas Eve

解法

$N$ 本の中から $K$ 本を選ぶ時、できるだけ高さの近い木を選びたいです。そのため木を高さ順に並べて、連続する $K$ 本

$1, 2, ..., K$ 本目
$2, 3, ..., K+1$ 本目
...
$(N-K+1), (N-K+2), ..., N$ 本目

を全て試せば、そのうちのどれかが答えになっているはずです。これをすべて試して一番良いものを求めればOKです。

ACコード

D - Christmas

解法

ハンバーガーが再帰的に作られています。なので、計算も再帰的にしていくことを考えましょう。

一般に、レベル $k$ バーガーの下から $x$ 層目までを考えてみます。レベル $k$ バーガーを分解してみましょう。

f:id:betrue12:20181209205728p:plain

レベル $k$ バーガーの構成要素の中でどこに境界があるかによって、場合分けをすることができます。この場合分けの条件を知るためにはレベル $k-1$ バーガーの長さが必要です。

どこに境界があったとしても、レベル $k$ バーガーの下から $x$ 層は

単体のバン、パティ
レベル $k-1$ バーガーの全体
レベル $k-1$ バーガーの途中まで

のうちのいくつかから構成されています。この中にパティがいくつ含まれているかを考えます。

単体のパティはもちろんパティ1個。レベル $k-1$ バーガーの全体に含まれるパティの数は、あらかじめ計算しておくことができます。残るはレベル $k-1$ バーガーの途中までの部分ですが…これを次のようにさらに分解していきましょう。

f:id:betrue12:20181209205742p:plain

このように途中までのバーガーをどんどん「拡大」していって、バーガーのレベルを1つずつ下げていくことで、最悪の場合でもレベル0バーガーまで下げれば具体的な値を求めることができます。

境界がどこにある場合でも、レベル $k-1$ バーガーの途中までが含まれているのは高々1個です。そのため再帰関数も各レベルについて高々1回しか呼ばれないため、呼び出し回数の合計は $O(N)$ で済みます。

あとはこれを場合分け＆再帰関数で実装します。各計算に必要なのは、

レベル $k-1$ バーガー全部のパティ数
レベル $k-1$ バーガー全部の長さ

で、これはバーガーの作り方に従ってレベル0バーガーから漸化式を立て、前計算しておくことができます。

解法をまとめると、

レベル $0, ..., N$ バーガーのパティ数と長さを漸化式で前計算しておく。
再帰関数を実装する。再帰関数ではどこに境界があるかによって場合分けをし、前計算の結果を使って上の図のようにそれぞれ計算する。
レベル $N$ バーガーの下から $X$ 層目を再帰関数で計算する。

のようになります。

ACコード

C++のほうがコメント多め。上記コードの再帰関数は直接的な場合分けではなく、下から見ていって使ったぶんだけ $x$ を減らすようにしています。

2018-12-08

01-BFSのちょっと丁寧な解説

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

先日Twitterで少し話題になったので書いてみます。データ構造とアルゴリズム Advent Calendar 2018 の8日目の記事でもあります。

「01-BFS」というものをちょっと丁寧に解説します。これは以下のような問題を解くことができるアルゴリズムです。

辺の長さが0または1である有向グラフにおいて、ある1つの始点から全頂点への最短路の長さを効率的な計算時間で求めよ。

f:id:betrue12:20181207211652p:plain

※図のグラフは非循環（DAG）ですが、必ずしもDAGである必要はないです。

この記事では01-BFSの解説の前に「ダイクストラ法」「幅優先探索」をそれぞれ復習し、その流れで01-BFSを解説します。必須ではありませんが、これら2つのコードを書いたことがない人は是非そちらからやってみてください。

ダイクストラ法

多くの人は深さ/幅優先探索→ダイクストラ法の順に学ぶと思いますが、今回は逆の記載順にしています。

ダイクストラ法は、以下の問題を解くことができるアルゴリズムです。

辺の長さが非負である有向グラフにおいて、ある1つの始点から全頂点への最短路の長さを効率的な計算時間で求めよ。

ダイクストラ法においては、全頂点について「それまでに見つかった、始点からの最短距離」を保持します。これを暫定最短距離と表記します。初期値は始点だけ0、それ以外の頂点は無限大（実装上は十分大きい値）です。

アルゴリズムは、まず始点を探索候補に加え、以下を繰り返すことで動作します。

探索候補の中で、暫定最短距離が最も小さい頂点 $v$ を取り出す。
頂点 $v$ から伸びる辺を用いて暫定最短距離を更新できる頂点がある場合、更新してその頂点を探索候補に加える。

この「暫定最短距離が最も小さい頂点を取り出す」という処理を実現するため、多くの場合は優先度付きキュー（＋適切な枝刈り）が用いられます。

ダイクストラ法は何故効率的に、ムダなく動作するのでしょうか？その理由は、端的に言うと二度手間が起こらないからです。

辺の長さが全て非負であるグラフにおいては、経路を進むことで始点からの合計距離が減るということがありません。そのため各ステップにおいて取り出す「暫定最短距離が最も小さい頂点」は、真の最短距離になっていることが保証されています。

f:id:betrue12:20181207212459p:plain

「暫定最短距離が小さいところをどんどん探索していったけど、後で近道が見つかっちゃったから全部探索し直しになる」ということは発生しません。

逆に言うと、長さが負の辺が存在する場合はこういうことが起こり得るので効率的に動作しません。最悪、長さが負の閉路で永遠にループして探索が終わらない可能性もあります。

f:id:betrue12:20181207213201p:plain

各ステップにおいて暫定最短距離が最も小さい頂点を取り出すことで、効率的な探索をすることができる。これがダイクストラ法のキモであり、この記事でも最も重要なポイントです。

幅優先探索による最短路問題

次は幅優先探索です。単なる全探索以外の目的で幅優先探索を用いる問題は、グリッドで表現された迷路などの移動回数を最小化するものが多いです。移動回数の最小化は、移動を長さ1の辺としたときの最短路問題と見なすことが出来ます。

f:id:betrue12:20181207213809p:plain

もちろんこれを優先度付きキューで解くこともできますが、これは「先入れ先出し（FIFO）」の機能を持つキューで実装するほうが効率的です。先ほどと同様に全頂点の暫定最短距離を保持し、まず始点をキューに加え、以下を繰り返します。

キューの先頭から頂点 $v$ を取り出す。
頂点 $v$ から伸びる辺を用いて暫定最短距離を更新できる頂点がある場合、更新してその頂点をキューの末尾に加える。

このアルゴリズムが動作している最中のキューの状態を考えてみます。先頭の頂点を取り出して、その暫定最短距離より距離が1大きい頂点が末尾に追加される…という操作が繰り返されるので、キューの中にある頂点の暫定最短距離は以下のようになっているはずです。

$1, 1, 1, 2, 2$ とか
$3, 3, 4$ とか
$100, 100, 100, 100$ とか

つまり「全てが同じ値である」または「ある値が前側に、それより1大きい値が後ろ側にそれぞれ固まっている」ような状態です。常にこのような状態になるので、先頭から取り出した頂点は常に暫定最短距離が最も小さい頂点になっているわけですね。

つまりキューを使うといっても、暫定最短距離が最も小さい頂点が先頭にある状態を常に保ってさえいればよくて、探索順序がFIFOである必要は全然無いのです。ここが後の説明に繋がります。

ここまでのまとめ

やりたいことはダイクストラ法も幅優先探索も同じで、「辺長が非負で始点が1点固定の最短路問題」を効率的に解くために、暫定最短距離が最も小さい頂点を選んで、そこから伸びる辺で他の頂点の暫定最短距離を更新することを繰り返したいのです。

それを具体的に実現する手続きにおいて、一般的な条件だと優先度付きキューが使えるし、辺長が全て1の場合はキューが使える、ということですね。

ここを再確認した後で、いよいよ01-BFSの説明です。

01-BFS

ここまでの内容が理解できていれば、01-BFSは自然に理解することができます。

先ほどは辺長が全て1の最短路問題を考えました。01-BFSはこれを少しだけ難しくした、辺の長さが0または1の最短路問題を解く方法です。

f:id:betrue12:20181207211652p:plain

キーポイントは辺長が全て1の場合と同じく、探索候補の順番を暫定最短距離で見て $3, 3, 4$ のような「全てが同じ値である」または「ある値が前側に、それより1大きい値が後ろ側にそれぞれ固まっている」という状態に保つことです。始点からの暫定最短距離が3である先頭の頂点を取り出して遷移先をチェックしたとき、その経路での始点から遷移先までの距離は辺長0ならば3、辺長1ならば4になります。このとき

距離3ならば探索候補の先頭に追加することで、候補の並びは $3, 3, 4$ になる。
距離4ならば探索候補の末尾に追加することで、候補の並びは $3, 4, 4$ になる。

とすることで、「全てが同じ値である」または「ある値が前側に、それより1大きい値が後ろ側にそれぞれ固まっている」という状態を常に保つことが出来ます。

先ほど「FIFOである必要はない」と書いたのはこういうことで、このように先頭にデータを割り込ませても良いのか少し不安になりますが、これで正しく機能します。

あとはこの操作を効率的に実現するデータ構造があればアルゴリズムを実装することができて、多くの場合両端キューが用いられます。両端キューは先頭と末尾の両方に対して要素の追加と取り出しを $O(1)$ で処理できるデータ構造です。

01-BFSではまず始点を両端キューに加え、以下を繰り返します。

両端キューの先頭から頂点 $v$ を取り出す。
頂点から伸びる辺を用いて暫定最短距離を更新できる頂点がある場合、更新してその頂点を
- 0の辺を用いた場合は両端キューの先頭に加える。
- 1の辺を用いた場合は両端キューの末尾に加える。

こう書いてしまうと理屈はとてもシンプルです。ダイクストラ法と幅優先探索をしっかり理解することが、01-BFSを理解する一番の近道です。

計算量のはなし

頂点数を $V$ 、辺数を $E$ とします。よく使われる実装ではこのようになります。

ダイクストラ法（優先度付きキュー利用）： $O(V + E\log V)$
幅優先探索（キュー使用）： $O(V + E)$
01-BFS（両端キュー使用）： $O(V + E)$

これまで見てきたようにどれもやっていることは大体同じなので、探索候補を格納するデータ構造の操作にどれだけ時間が掛かるかという点で差が出ています。

※ダイクストラ法の計算量は（優先度付きキュー利用を前提としても）細かい実装や資料によって書かれ方が色々違っていることがあります。グラフが単純かつ始点から全頂点に到達可能であると仮定すると $V-1 \le E \le V(V-1)$ が成り立つので、だいたいの実装は式変形すると上記の評価になると思います。

01-BFSを使う問題

01-BFSが比較的素直に使える問題を紹介します。私もあまりたくさんは知りません。

※（2018年12月時点で）AtCoder過去問を新しい方から埋めていった場合、多くの人が最初に「01-BFS」という単語を目にする問題はコレだと思いますが…これは01-BFSに帰着させるまでの考察が問題のほぼ全てなので、リストには含めていません。

問題文を読んでいただければわかるように、

ノーコストの手段で移動する
何らかのコストや回数制限のある手段で移動する

の2通りの移動方法が与えられているような問題は、01-BFSに帰着できることがあります。

ただ…これらの問題は全て、高速な言語であればダイクストラ法でも十分間に合います。もしかしたらスクリプト言語を使っている人のほうが、01-BFSを必要とする機会が多いかもしれません。

実装例

隣接リストでグラフを管理しているときの01-BFSの実装例です。入力などを受け取るところは省略しています。

C++

#include <bits/stdc++.h>
using namespace std;

int main(){
    // 頂点数N、始点の頂点番号s
    int N, s;
    // 隣接リスト。
    // edges[i]の要素に(j, c)が含まれる時、iからjにコストcの辺が存在
    vector<vector<pair<int, int>>> edges(N);

    vector<int> dist(N, 1e9);
    dist[s] = 0;
    deque<int> que;
    que.push_back(s);

    while(que.size()){
        int i = que.front(); que.pop_front();
        for(auto [j, c] : edges[i]){
            int d = dist[i] + c;
            if(d < dist[j]){
                dist[j] = d;
                if(c){
                    que.push_back(j);
                }else{
                    que.push_front(j);
                }
            }
        }
    }
}

Python

from collections import deque

# 頂点数N、始点の頂点番号s
N, s = map(int, input().split())
# 隣接リスト。
# edges[i]の要素に(j, c)が含まれる時、iからjにコストcの辺が存在
edges = [[] for i in range(N)]

dist = [10**9]*N
dist[s] = 0
que = deque()
que.append(s)

while len(que) > 0:
    i = que.popleft()
    for j, c in edges[i]:
        d = dist[i] + c
        if d < dist[j]:
            dist[j] = d
            if c == 1:
                que.append(j)
            else:
                que.appendleft(j)

グリッドグラフの場合

グリッド上を探索する場合は、隣接リストなどを作らずに座標で移動先を指定したほうが書きやすくて実行速度も速いことが多いです。そのように実装した「器物損壊！高橋君」の実装例を以下のリンク先に提出しています。多めにコメントを付けています。

余談：BFSって？

一般に幅優先探索をBFSと略すことが多いですが、この記事では幅優先探索の意味でBFSという略語を使わないようにしました。

01-BFSは「辺コスト1の最短路問題を幅優先探索で解く方法の拡張」ではありますが、これが幅優先（Breadth-First）なのかと言われるとかなり違う気がしています。あくまで優先されているのは暫定最短距離の短さだからです。

Wikipediaには「最良優先探索（Best-First Search）」なる言葉が載っていて、こちらであれば完璧に当てはまります。偶然にもどちらも略語はBFSになってしまいますね。

もちろん多くの文脈では幅優先探索をBFSと略しても誤解はないと思います（私も使います）が、このように最短路問題における特殊化・一般化について述べる際には指しているものが曖昧になりやすいので、意識して区別するようにしています。

2018-12-05

Codeforces Round #525 参加記録＆解説（A～E）

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

Dashboard - Codeforces Round #525 (Div. 2) - Codeforces

今回は3完…うーん。Div2でこれは良くないですね。

f:id:betrue12:20181205205506p:plain

本番後にEまで通したので5問書いていきます。

A. Ehab and another construction problem

Problem - A - Codeforces

問題概要

正整数 $x$ が与えられる。以下の条件をすべて満たす整数 $a, b$ を1組求めよ。（存在しない場合は -1 を出力せよ。）

$1 \le a, b \le x$
$b$ は $a$ の約数である
$ab \gt x$
$\frac{a}{b} \lt x$

制約

$1 \le x \le 100$

解法

$a, b$ の組が最大で10000個しかないので、全探索が確実です。

$O(1)$ 解法もありますが、本番ではノータイムで全探索を書き始めました…Codeforcesではコーナーケース考慮漏れによるシステス落ちが常に頭をよぎるので、個人的には余裕で間に合う計算量であれば全探索したくなります。

ACコード

Submission #46589226 - Codeforces

B. Ehab and subtraction

Problem - B - Codeforces

問題概要

長さ $n$ の配列 $a_{1}, ..., a_{n}$ が与えられる。これに以下の操作を $k$ 回行い、それぞれ値を出力せよ。

非零の要素が存在する場合、最も小さい非零の値を出力する。その後、その値を配列内のすべての非零要素から引く。
全ての要素が0である場合、0を出力する。

制約

$1 \le n, k \le 10^{5}$
$1 \le a_{i} \le 10^{9}$

解法

0になってしまった要素はその後の操作に全く関係しないので、配列から除外してしまって構いません。また与えられる要素が全て正で、常に最小の値を引き算するので、操作中に配列の要素に負数が現れることはありません。

以下リンク先のコードではシミュレーションをしています。配列を降順にソートし、末尾の値が0なら削除し、そうでなければその値を出力して全体から引きます。ただし毎回全ての要素に引き算をしていては間に合わないので、「今まで累積いくつ引き算したか」を持っておいて処理しています。

よりスマートな解法として、最初に重複要素を全て除いてしまうという方法もあります。

ACコード

Submission #46592094 - Codeforces

C. Ehab and a 2-operation task

Problem - C - Codeforces

問題概要

長さ $n$ の配列 $a_{1}, ..., a_{n}$ が与えられる。この配列に以下の操作を好きな順序で $n+1$ 回以下行い、配列を狭義単調増加にしたい。そのような操作列を1つ求めよ。

整数 $i, x$ を選ぶ（ $1 \le i \le n, 0 \le x \le 10^{6}$ ）。配列の要素 $a_{1}, a_{2}, ..., a_{i}$ それぞれに $x$ を加算する。
整数 $i, x$ を選ぶ（ $1 \le i \le n, 1 \le x \le 10^{6}$ ）。配列の要素 $a_{1}, a_{2}, ..., a_{i}$ それぞれを、 $x$ で割った余りに置き換える。

制約

$1 \le n \le 2000$
$0 \le a_{i} \le 10^{5}$

解法

「余りを取る」という操作を上手く使うことを考えます。

$a_{1}, a_{2}, ..., a_{N}$ に上手く値を足し、それぞれを $n$ で割った余りが $0, 1, ..., (n-1)$ になるようにする。
最後に全要素を $n$ で割った余りに置き換える。

ことで条件を満たすことができます。 $n$ 回の足し算操作を行えるので、末尾から順番に余りの値を合わせていけばよさそうです。

足し算操作は $n$ が小さいので愚直にやっても十分間に合います。B問題で書いたのと同じようにまとめて加算することもできます。

各操作では（1-indexedで書くと） $(a_{i} + x) \% N = i-1$ となるような $x$ を求めることになりますが、これはそのまま移項して $x = (i-1 - a_{i}) \% N$ とすればよいです。ただし言語によってはこの値が負になってしまったりするので、さらに $x = (x + N) \% N$ とするなどしてください（つらい）。

ACコード

Submission #46597669 - Codeforces

D. Ehab and another another xor problem

Problem - D - Codeforces

問題概要

インタラクティブ問題である。以下のクエリを62回以下行うことで、隠された整数 $a, b$ を求めよ。

である整数をクエリとして出力する。その答えとして以下の値を得ることができる。ここではXOR演算を表す。
- $a \oplus c \gt b \oplus d$ のとき、 $1$
- $a \oplus c = b \oplus d$ のとき、 $0$
- $a \oplus c \lt b \oplus d$ のとき、 $-1$

制約

$0 \le a, b \lt 2^{30}$

解法

最下位ビットを0ビット目として、下から数えて $k$ ビット目のビットを単に「 $k$ ビット目」と呼ぶことにします。

値の大小には、上位ビットほど優先的に影響を与えます。そのため上位ビットから順に決めていくことを考えます。まず最上位のビット（29ビット目）を決めるため、クエリとして29ビット目だけを立てたものを考えてみましょう。

考えられるクエリは $(0, 2^{29}), (2^{29}, 0), (0, 0), (2^{29}, 2^{29})$ あたりです。各ビットごとに使えるクエリはほぼ2回なので、良い情報が得られそうなものを2つ選びたいですが…ここでは $(0, 2^{29}), (2^{29}, 0)$ を考えてみましょう。

$a, b$ の29ビット目のパターンそれぞれについて、クエリの結果がどうなるかを書き下します。

↓ $a, b$ の29ビット目	$(0, 2^{29})$	$(2^{29}, 0)$
$0, 0$	-1 が返る	1が返る
$0, 1$	28ビット目以下の大小に従う	同左
$1, 0$	28ビット目以下の大小に従う	同左
$1, 1$	1が返る	-1が返る

このように、両クエリで値が異なる場合は $a, b$ の29ビット目が確定します。ただし値が同じ場合、29ビット目が $a, b$ で異なるという情報は得られますが、どちらが $1$ なのかは分かりません。これを判定するには、別途 $(0, 0)$ のクエリを発行し、 $a, b$ の大小関係を調べればよいです。

上位のビットが判定できれば、以降のクエリにはそのビットを常に付与しておくことで、 $a \oplus c, b \oplus d$ ともに上位ビットは打ち消し合って0になります。そのため最上位ビットと同様の判定方法でビットを判定していくことができます。

まとめると、「 $k$ ビット目を判定するためには、 $k$ ビット目以下の大小関係を知った上で、クエリ $(0, 2^{k}), (2^{k}, 0)$ を発行すればよい」ことになります。これだけ見ると、ビット1つにつきクエリが3つ必要そうに思えますが…

最初の情報を得るために $(0, 0)$ は発行する必要があります。それ以降は追加のクエリを発行しなくても、上位ビットから判定していって以下のように考えることで大小の情報を得ることができます。

$a, b$ の $k$ ビット目が等しい場合、 $k$ ビット目以下の大小と $k-1$ ビット目以下の大小は一致するので、そのまま情報を使うことができる。
$a, b$ の $k$ ビット目が異なる場合、上記の表に記載した通りクエリの結果は「 $k-1$ ビット目以下の大小に従う」ため、この結果を情報として使うことができる。

このように考えることでクエリ回数は最初の1回＋30ビット×2回の計61回となり、問題の条件に収まります。

ACコード

Submission #46645417 - Codeforces

E. Ehab and a component choosing problem

Problem - E - Codeforces

問題概要

$n$ 頂点の木があり、各頂点に重み $a_{i}$ が設定されている。この木から連結成分を互いに交わらないように1個以上選ぶ。

選び方のスコアは、連結成分の数を $k$ 、選んだ連結成分に含まれる頂点全ての重み和を $A$ として $\frac{A}{k}$ と定義される。

スコアを最大にし、かつその中で $k$ を最大にしたい。そのような選び方をしたときの $A, k$ を求めよ。

制約

$1 \le n \le 3\times 10^{5}$
$|a_{i}| \le 10^{9}$

解法

スコアは「各連結成分の重み和の平均」と解釈することができます。その最大値は、1つだけの連結成分で作れる重み和の最大値（これを $A_{1}$ とします）と一致します。 $A_{1}$ より大きな重み和を持つ連結成分が作れない以上、その平均も $A_{1}$ を超えることができないからです。

そのためまずは $A_{1}$ を求めます。重み和最大の連結成分を求めるのは、適当に根を決めた根付き木において以下のような木DPをすることで可能です。

$dp\lbrack i \rbrack$ を「頂点 $i$ を含み、根付き木において $i$ 以下の要素で作られる連結成分の最大重み和」とします。 $dp\lbrack i \rbrack$ を求める時に $i$ の子 $j$ それぞれと接続をするかどうかは、 $dp\lbrack j \rbrack \gt 0$ であれば接続し、そうでなければ接続しない、とすることで最適となります。

f:id:betrue12:20181205231143p:plain

※この説明には例外がありますが、それは後で補足します。

これで $A_{1}$ を求めることができました。今度は $k$ を最大にするため、「重み和 $A_{1}$ の連結成分を最大でいくつ作れるか？」を求めることが必要になります。これも同様に木DPで求めることができます。先程のDPとの違いは、「重み和 $A_{1}$ の連結成分ができたら、そこで連結成分を閉じて上と繋がない」ようにするだけです。

これで多くの場合は解を求めることができますが…DPにおいて「重み和が正でない子は切り捨てる」としているため、全頂点の重みが0以下であるときには1つも頂点を選べません。この場合は「いかにマイナスを小さくするか」という視点で考えると、「値が最大の頂点を探し、それと同じ値の頂点を全て独立な連結成分として選ぶ」ことが最適だと分かるので、木DPをせずにこれを出力してしまえばよいです。

ACコード

Submission #46645581 - Codeforces

この実装のようにDPテーブルを保持せず、再帰関数の戻り値だけで処理することも可能です。

2018-12-05

解説記事のはなし

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

この記事は「Competitive Programming (1) Advent Calendar 2018」の5日目の記事です。

解説記事を書いています

私がコンテストの参加記録として記事を書き始めたのは今年の5月末くらいです。競技プログラミングを始めたのが4月頭なので、だいたい2ヶ月後です。最初の記事はこれ。

AtCoder ARC098 参加記録 - ARMERIA

それ以来、参加したコンテストは全部ではありませんがなるべく記事を書くようにしています。AtCoderでは参加したABC/ARC/AGCは毎回書いています。企業コンやCodeforcesはたまにサボっています…

記事を書くようになって以降「この記事のおかげで理解できた」という声ももらうようになり、嬉しい限りです。皆さんのACが私の記事執筆エネルギーになっています。

解説記事を書く目的

解説記事を書いている目的は2つです。

自分の復習のため。
他の人、特に公式解説を読んでよく分からなかった人の理解の助けとなるため。

単発で書いている精進記事は前者、コンテスト後に書いている記事（特にABCオンリー回）は後者の目的が強いです。

どんな記事を目指しているか

私の記事は全体的に「長い」です。長い文章を書くというのが好きというのもありますが、一番の理由は「公式解説を読んでよく分からなかった人の理解の助けとなる」ためです。

writerさんにもよりますが、AtCoderの公式解説は簡潔です。解ける人の目線で書かれているので（writerさんが書いているので当然ではありますが）、「あと一歩で解ける」という人には必要十分で非常に良い解説となっていますが、知識や理解レベルにギャップがあると「解説の解説がほしい」という状態になります。私も競技プログラミングを始めたばかりの時は解説を読んでそう思うことがありました。

そのため非常に簡潔にまとまっている公式解説と相補的に機能するもの、つまり前提知識や考え方についての補足があり、理解レベルのギャップを埋められるようなものを書きたいと思っています。

競プロ以外にも言えることですが、「万人にとって必要十分になるような説明は存在しない」と考えています。読む人によっては私の記事は冗長すぎると感じるかもしれません。公式解説PDFがあり、とても分かりやすい解説放送があり、そして私以外にも何人かの人がコンテスト後に解説記事を書いています。解説を探す人は、是非自分に合った解説を見つけるため渡り歩いてほしいと思います。

記事を書く時に意識していること

まず公式解説を読みます。解説放送がある場合はそちらも観ます。そしてTwitterでコンテスト参加者の人のツイートを見て「どういうところで考えが詰まってそうか」をチェックし、そこをどうやったらフォローできるかを考えて記事を書きます。

先述の通り「公式解説と相補的に」がモットーなので、こんな感じのことを意識しています。逆に公式解説がめっちゃ丁寧で分かりやすいと、私が書くことがなくなるので困ります（？）

もう1つ意識していることは「図を使う」ことです。競プロの考察においても解説においても、図はとても有効です。いかに視覚的なイメージを持てるかで理解度が大きく変わってきます。私自身が図形的なイメージで理解していることは、なるべく解説でも図付きで記述するようにしています。図を描くツールは「draw.io」のデスクトップ版を使っています。

speakerdeck.com

最近はこんな感じでスライドを使うことも始めました。スライド作成にはGoogleスライドを使っています。

ただしABCオンリー回など、コンテスト終了直後に解説記事を公開できそうなときにはスピード重視で書くこともあります。そのタイミングが一番「解説が要望されている」時間かなと思うので。

解説記事を書いてみませんか？

私は解説記事を書くことも好きですが、読むことも好きです。私自身、分からない問題の解説を求めてブログなどを探すことが多々あります。自分が解説を書いた問題も、他の人の解説を読むことで参考にしています。

解説記事を書くのはけっこう時間がかかるので、全ての人にオススメできるものではないです。面白そうだなと思ったらやってみてください。いつかその記事のおかげでACする人が現れるでしょう。私も色々な人の記事を読むのが楽しみです。

オススメ解説記事ブログ

個人的に好きでよく読んでいる解説ブログを~~勝手に~~紹介します。

Mister雑記
- 個人的に推しNo.1。ものすごく解説が丁寧で分かりやすい。図もキレイ。コンテスト終了後の記事も過去問の記事も充実しています。
kmjp's blog
- 解法説明はとても簡潔。とにかくたくさんの問題の記事を書かれていて高難度の問題も多いので、私が自分で解けなかった問題の解説にいつも助かっています。
けんちょんの競プロ精進記録
- 「どんな風に考察を進めていけばよいか」がとても丁寧に書かれている記事。思考の流れがすごく参考になるので、たとえ自力で解けた問題であっても読む価値大です。
Kutimotiの競プロメモ
- こちらも、問題を解く人目線での思考の流れがよく分かる記事。こちらのページに掲載されている問題もあります。

おわり

これからも記事をたくさん書いていくので、よろしければ読んでやってください。よろしくお願いします。