AtCoder Regular Contest 086
Updated:
Source codes
Solutions
C - Not so Diverse
カウントして小さい方から消していく。
ポイント
V.erase(V.begin()) のおかげで 1 ケース TLE になった。
D - Non-decreasing
仮に全ての数が非負だったら、 $a_{i+1} += a_i$ を繰り返せば良い。 同様に、仮に全ての数が非正だったら、 $a_{i-1} += a_i$ を繰り返せば良い。
絶対値が最大のものを取ってきて、全てに足せば、全ての数が非負または全ての数が非正になる。
ポイント
この 2 つに分解するのがポイント。このせいで時間が。
E - Smuggling Marbles
この問題は、データ構造を使い回す問題である。 vector<deque<vector<ll>>> DP を定義する、動的配列、両側つきキュー、動的配列である。
$DP[i][j][k] = $ 頂点 $i$ を根とする部分木だけ考えたとき、深さ $j$ の頂点のビー玉の置き方の組であって、 $j$ 回の操作によりそれらが全て頂点 $i$ に来た時に頂点 $i$ に置いてあるビー玉が $k$ 個であるような場合の数。ただし $k = 2$ の場合は、「$2$ 個以上」を表すものとし、適切な時期に $k = 0$ へ合算され $0$ に戻されるという、途中計算にのみ使用する temporary なものとする。つまり、本質的には $k = 0, 1$ のみ定義される。
この時、 $DP[0]$ を求めることができれば、 $\sum_j DP[0][j][1] \times 2^{N+1 - dep[j]}$ が答えである。ここで $dep[j]$ は深さ $j$ の頂点の個数。 $DP[0]$ の他はいらないことに注意してほしい。
頂点 $x$ の子が $a, b$ であり、 $DP[a], DP[b]$ を求めたとする。この時、子の $DP$ を 破壊的に処理 し、親の $DP[x]$ を iterator で求める。考えやすいように、
\[
\begin{align}
DP[a] &= \begin{pmatrix} DP[a][0], DP[a][1] \end{pmatrix} \\
DP[b] &= \begin{pmatrix} DP[b][0], DP[b][1], DP[b][2], DP[b][3] \end{pmatrix}
\end{align}
\]
となっているとする。この時、長い方である $it = DP[b]$ を iterator でとり、短い方 $DP[a]$ を併合する。子がいっぱいあるときも、常に長い方を $it$ で指し示し、短い方を併合する動作を繰り返す。
こうして全ての子を併合した $it$ の、必要なだけの長さの $j$ に対し(ここでは $0 \leq j < 2$ であって $0 \leq j < 4$ ではない)、 $it[j][2]$ を $it[j][0]$ に合算し $0$ にする。その後 $(1, 1, 0)$ を前から挿入するとこれが $DP[x]$ になっている。
実践的には vector<deque<vector<ll>>>::iterator itr[200010] を持っておく方が懸命だと思う。
短い方を長い方へ併合しているので、全体の計算量はならしで $O(N \log N)$ となるのは有名である。この時点で間に合うことは保証されたようなものであるが、実は、全体の計算量は最悪でも $O(N)$ である。最後にこのことを示しておく。全体からみて、挿入する動作と、併合する動作(マス目の数で数える)が、それぞれ何回行われたかチェックしよう。まず挿入する動作であるが、これは頂点の数と等しく $N+1$ 回である。次に、併合する動作の数を数えるために、仮に併合する動作でもメモリ上消えないと仮定して「併合された側のマス」に印をつけていくことにしよう。すると、同じマスに印は二度とつかないことがわかる。つまり併合の動作数(マス目の数で数える)は、全てのマスの数を超えないことがわかり、 $N+1$ で抑えられている。ゆえに、挿入する動作と、併合する動作、いずれも計算量は $O(N)$ である。答えを計算する他の動作もこれを超えないので、全体の計算量は $O(N)$ である。
最後の落とし穴：コンパイラ
この問題、全く同じプログラムでも、 C++14 (GCC 5.4.1) は通り、 C++14 (Clang 3.8.0) は MLE になる。同じ被害に遭っている人が少なくとも 2 人いるようである。
Clang で落とされていない場合は、 3 種類の値を保有する struct を自分で定義し 1 個の vector を使い回す解法であった。この場合どうやっているのか詳しく解析していないが、見通しは悪いものの無理ではないと思う。最後に出てくる $DP[0]$ の長さがあらかじめ決まっているし、再帰でやっても絶対的な位置を与えることは無理ではない。
VSCode に乗り換えた後にこの記事を執筆しているが、 VSCode の構文解析は Clang によるので、そのまま Clang で手元でテストし Clang で提出したいところではある。しかし Clang は上記のような問題点があり、以前も「Clang は TLE, GCC は AC」のようなこともあった。だから
- 構文解析は Clang で行う
- 手元で実行するところから提出までは GCC で行う
ということにした。
ポイント
部分点解法はわかっていたが実装間に合わず。満点解法は、数学的な感じではなくて、データ構造を使うものだった。とは言っても、高尚な話ではなくて deque を使い回すだけである。数学的な簡単さを求めていた私は永遠にたどり着くことはできない。
解説放送で rng さんが C++11 では vector<int> x, y を swap(x, y) するのは $O(1)$ だと言っていた。これを使うと簡単に実装ができるという。私は愚直に iterator をいじることにした。 pointer を理解していればこのほうが簡単かと思う。
F - Shift and Decrement
解説聞いてもよくわからなかった。
ポイント
Others
rng さんによると、慣れている人なら E の部分点までは取れないといけないという。確かに D でつまらなければ E の部分点は取れたと思う。
最近、専門家による治療を続けているが、嫌なことが起こると 1 週間くらいは減退してしまう。この時の体調は最低だった。