AtCoder Grand Contest 029
Updated:
Source codes
Solutions
A - Irreversible operation
swap しているだけなので、左から見ていき、白石を観測したら、飛び越える黒石の数(それまで観測した黒石の個数)を足していくだけである。時間計算量は $N = \lvert S \rvert$ としたとき $O(N)$ である。
B - Powers of two
ポイント
C - Lexicographic constraints
初期的考察
$\{ A _i \}$ たちを reverse する。この問題は $S _0 > S _1 > S _2 > \dots > S _{N - 1}$ としていった方が考えやすい。また、以下では文字列は自然数で表し、順序は $0 > 1 > 2 > \dots$ と逆順に入っていると考える。
まずこの問題の $A _i \leq 10^9$ という制約を忘れて、愚直にどうするべきか考えてみる。すると、以下のことに気がつく。
- $A _i > A _{i + 1}$ の場合は、文字数を単純に減らすのがいかなる場合でも最善である。
- $A _i < A _{i + 1}$ の場合は、まず最初の $A _i$ 文字について出来るだけ「小さく」進めておき、 $A _i$ 文字目以降では $0$ を入れるのが最善である。よってこの場合は $A _i = A _{i + 1}$ の亜種と考えられる。
- $A _i = A _{i + 1}$ の場合、何が最善であるかは、 一概には言えない 。例えば $A = {2, 2, 2, 2, \dots }$ と続いている場合は、 $(0, 0), (0, 1), (1, 0), (1, 1), \dots$ と続けるものと $(0, 0), (0, 1), (0, 2), (0, 3), \dots$ と続ける方法がある。前者の方が文字の種類という意味では得をしているが、後者の方が辞書順では小さくて済んでいる。一般に 辞書順を考える場合は貪欲法と相性が良い ので、このどちらであるかを前から見ていって決められないのは非常に悩ましい。
そこで問題に立ち戻って考えると、文字種類の最小値を考えることになる。明らかに、文字数は $N$ 種類あれば可能だし、 $0$ 種類では絶対にできない。つまりこれは二分探索で可能判定をすればよろしい。つまり、与えられた $X \in \mathbb{N}$ に対し、 「$X$ 文字種類で実現可能か？」をそこそこのスピードで判定できれば良いことになる。
これならば先に述べた問題は解決する。例えば $X = 3$ で実現可能かという問題に対しては $(0, 0), (0, 1), (0, 2), (1, 0)$ が一番得をするのは確実であるから、前から順に確定できることになる。
制約の「解消」
以上のことを愚直に判定するプログラムは簡単に書ける。先ほど書いた数列を、配列で持っておいて、更新すれば良いからだ。擬似的に $X$ 進数を実装し、カウンタが回らなくなったら false 、全部処理できたら true を返せば良い。
さて問題は $A _i \leq 10^9$ という制約である。上記の方法を愚直に実装しようとすると $10^9$ 個の配列が必要となり、当然間に合わない。
ところで、文字種類 $2$ 種類でどのくらいの数が実現可能か考えてみる。すると $A = \{ 20, 20, 20, 20, 20, 20, \dots \}$ なら、答えはもう $2$ である。というのも $2^{20} \approx 10^6$ であるので、 $N \leq 2 \cdot 20^5$ と比べて大幅に余裕がある。つまり せいぜい上から $20$ 桁が正確に管理できていれば可能判定に影響はない わけである。ゆえに $A _i$ たちが $10^9$ 個必要な場面というのは、まずありえない。
そこで $10^4$ 以上は全て $\infty$ とみなす ことにする。つまり $10^4$ 個だけ配列を確保して、先に述べた $X$ 進数で計算していく。ただし $\infty$ を観測したら操作しないで次に進む 。 $10^4$ 以上の桁は、上の $20$ 桁の計算結果には絶対に影響を与えないからである。
以上で答えがでる。 $K = 10^4$ とすると、計算量は $O(NK \log N)$ である。これで $1 \cdot 10^0$ sec 程度で、間に合った。多分 $K = 10^3$ 程度でも問題ない。
ポイント
上記のような制約の解消の仕方は、定跡なのかもしれないが、私は知らなかった。
制約の解消に近いことは結構早い段階で思いついていたのだが、「$\infty$ を観測したら 操作しないで次に進む」のところを誤ってしまった。例えば $A _i \gets \min(A _i, 10^4)$ と単純に丸め込んでしまうと、 $A = \{ 100000, 100000, 99999, 99999, 99998, 99998, \dots \}$ のようなケースで WA を出してしまう。ここで 6WA してしまった。しかし 130 分で AC を出せたので、不幸中の幸い。よかった。