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

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