AGC043 参加メモ - tinumu's reminder

atcoder.jp
AGC043に参加しました。
ABの2完(110:49)で378th, Perf=2115 (1873->1900) でした。
AGCでちゃんと黃パフォを出せたのは少し安心したな

３日前なのでなんか忘れてそうだけど、解説メモっぽいのを書いていきます
Dまで解いて書きました

A - Range Flip Find Route

一つの経路を考えた時に、黒が含まれている部分があるとする。
経路中でそのような黒の領域は全て消さなければ $(H, W)$ へは行けない。
経路において連続している黒の領域は $1$ 回の操作で白にできる。この際、経路中の白の部分を黒にしないで実行できる。
黒の連続しているところを白にする操作は経路中では最小の操作になる(階差を考えると証明できる)。
最小の操作の仕方はわかったので、あとは、経路を選択するためにDPをしておわり(白->黒の時にコストを $1$ 追加するようにして解けば良い)

B - 123 Triangle

まず、 $1,2,3$ で与えられるのは扱いづらいため、 $-1$ して $0, 1, 2$ にする(この後の数列に変化はない)。
なぜそのような変換をするかというと、これから出てくる数列は全て $0, 1, 2$ になるので、最初から一貫した計算が出来るようにするためである。

まず、数列内に $2$ と $1$ が混在する場合、答えが $2$ になることはない。
この場合、 $1$ は必ず $0$ か $2$ に隣接する場所が現れるので、次の数列でも $1$ が現れる。
$2, 0$ のどちらかが $x_{N-1}$ まで残り続けたら、答えは $1$ になる。
もし、 $2, 0$ が途中でどちらも無くなった場合は、 $1$ だけになるので、そこから $2$ は生まれなくなる。
ということは答えは $0, 1$ しかありえない。

さらに、そのようなときは、 $2$ を $0$ に置き換えて考えられる。
置き換えても、つじつまが合っているので、答えが $1$ かどうかは変化していない。
答えが $1$ ではないのなら、上述の通り、 $2$ がありえないので、 $0$ しか無い事がわかるので答えが確定できる。

そのため、 $0, 1$ しかない場合に対する演算を考えれば良いことになる。

また、数列内に $0, 2$ しかない場合も、 $0, 1$ しかない場合に対する演算を考えれば、答えを $2$ 倍して得られたものが答えである。

次に $0, 1$ に対する答えを考えてみる。
この時、 2項の差は2項のxorになる。
$a_i$ が答えに何回寄与するかは $\binom{N-1}{i}$ になっている。xorなので、寄与が偶数になっていれば寄与しないのと同じになり、奇数だと $1$ 回だけ寄与するのと同じになる。
そのため、 $\binom{N-1}{i}$ が奇数か偶数かだけを考えれば良い。
奇数だったら答えに $a_i$ を xor すれば良い。
偶奇の判定は、二項係数が階乗を使って出来ている事を利用して階乗の $2$ の素因数が何個含まれているのかを見るか、 $Lucas$ の定理というのを使うと簡単にもとまるらしい。

以上、人に見せる気のない解説でした()

C - Giant Graph

重みの定義的に、明らかに大きい方から取る貪欲が成り立ちそうなことがわかる。

まず、単純なグラフ ( $1$ 次元のとき) の重みが最大になる独立集合を考える。
一番大きい頂点は必ず取るのでそれを独立集合に入れる。
そうしたら、次に大きい頂点を見て、先ほどの頂点と隣接しているかどうかを判定して隣接してない時に独立集合に入れる。と言ったような操作が出来る。こうすると $1$ 次元での問題は解ける。

今回の $3$ 次元のグラフを考えてみる。
頂点 $(i_1, j, k)$ にいるとして、 $i_1$ から $i_2$ に辺が張られている時に、
全ての $j, k$ に対して頂点 $(i_1, j, k)$ から頂点 $(i_2, j, k)$ へ行けるので、
$3$ 次元のグラフの現在位置はこう言い換えられる。

$3$ のグラフ $X, Y, Z$ があって、それぞれのグラフに $1$ つずつ駒を置く。
それらの駒の現在位置が $i \in X, j \in Y, k \in Z$ であり、これらはそれぞれのグラフに基づいて独立に動く。
と考えても良い(もしかしたらこれは問題文にすでに書いているかも？)
そうすると、グラフ $W$ のような大きいグラフではなくて、単なる $3$ つのグラフがあるだけと見ることが出来る。

ところで、先ほどの $1$ 次元のグラフの重みが最大の独立集合を求める問題について考察する。
辺を重みが小さい頂点から大きい頂点へのみに貼ると、このグラフはDAGになる。

すると、問題は次の問題と同じになる。
「アリスとボブがグラフ $G$ に一つ置かれた駒を動かすゲームをしている。それぞれ、駒を辺の張られた頂点へ動かす操作を $1$ 回ずつ交互に行う。アリスが先手である。このとき先に駒を動かせなくなったほうが負けである。アリスが必ず負けるような駒の頂点の重みの総和はいくらか？」
アリスが負ける頂点の集合は独立集合になっており、それは大きい頂点から決まっていくので、問題が同じになる。
この問題はgrundy数を用いて $grundy[x] = 0$ になっていれば頂点 $x$ はアリスが負ける頂点であると言えるので、解ける。

このグラフを $3$ つ用意して、駒を $3$ つ用意する問題を考える。
この時はそれぞれの grundy 数の総xor が $0$ になっていれば、アリスが負ける。
これは、グラフ $W$ における重みが最大になる独立集合と一致する(重要)。

そのため、グラフ $X, Y, Z$ のgrundy数を示す配列をそれぞれ $grundyX, grundyY, grundyZ$ とすると、ある頂点 $i, j, k$ があって、 $grundyX[i] \oplus grundyY[j] \oplus grundyZ[k] = 0$ であるような頂点 $i, j, k$ を探せば良くなる。
grundy数の性質により、grundy数はたかだか $\mathrm{O}(\sqrt{M})$ ( $M$ は辺の個数) 程度しか無いので、 grundy数を $2$ つ決め打ち(これを $g_1, g_2$ とする)、 $3$ つ目のgrundy数は $g_1 \oplus g_2$ とすると、 $\mathrm{O}(M)$ 程度で決め打てる。

最後に、grundy数を決め打っても頂点は複数あるので、そこで計算量を取らないように、 $\mathrm{O}(1)$ で計算しなければならない。
次の計算式を考える。
$\sum\limits_{i} \sum\limits_{j} \sum\limits_{k} 10^{18(i+j+k)}$
この計算式は次のように式変形できる。
$(与式)=\sum\limits_{i} \sum\limits_{j} \sum\limits_{k} 10^{18i} \times 10^{18j} \times 10^{18k}$
$=\sum\limits_{i} 10^{18i} \sum\limits_{j} 10^{18j} \sum\limits_{k} 10^{18k}$
$=(\sum\limits_{i} 10^{18i}) \times (\sum\limits_{j} 10^{18j}) \times (\sum\limits_{k} 10^{18k})$

このように式が分解できるので、それぞれのgrundy数に対して総和を前計算しておくと、 $\mathrm{O}(1)$ で計算できる。
全体の計算量は $\mathrm{O}(N+M)$ で、この問題を解けました。

解説の方法を誰か教えてください(涙)

D - Merge Triplets

この問題は一番大きい値に着目することで解くことが出来る。

一番大きい値である $3N$ が取り出された時は、他の数列たちは全て取られていることになり、最後に $3N$ の後にあった数列が連続して取り出される。この $3N$ と $3N$ の後ろにあった数列を一つの「ブロック」とする。
$3N$ が取り出される前は、先ほどの「ブロック」に含まれない最大の値があってそれを先頭とした「ブロック」が連続して取り出されていたことになる。
このような「ブロック」の単位で考えると、この問題は考えやすい。
ブロックごとに取り出すというように考えると、各ブロックの先頭は昇順であるというように考えられる。

$P$ は図のようにしか構成されないはずである。
ブロックの先頭が昇順になっているように構成できれば、他の数列がどうなっていようが、 $A_1A_2\cdots A_N$ を作れる。
ただし、ブロックは次の条件を満たしている必要がある。

ブロックの長さはたかだか $3$
$長さが1のブロックの数 \geq 長さが 2 のブロックの数$

前者は明らか。
後者は、長さが $2$ のブロックを作ったら余りが長さ $1$ になることから言える。

後は条件を満たすようにDPをしていけば良い。
$DP[i][j]$ : 現在構成している列の長さが $i$ であり、 $長さ1のブロックの数 - 長さ2のブロックの数$ が $j$ である。
こうすると、 $DP[3N][j], 0 \leq j \leq 3N$ が答えになる。

遷移は、 $P$ をブロック単位で後ろから作っていくと考えるのがわかりやすい。
残っている値の中の最大値を選ぶのは $1$ 通りであり、その後は任意に決められるので、
未使用の値の個数を $n$ としてブロックの長さを $k$ とすると、 $_{n-1}P_{k-1}$ 通りだけある。
そのため、長さ $3$ を選ぶ or 長さ $2$ を選ぶ or 長さ $1$ を選ぶという遷移を適切にやっていけば、遷移は $\mathrm{O}(1)$ で、空間計算量に依存して、 $\mathrm{O}(N^2)$ でこの問題を解くことが出来る。