AtCoder Beginner Contest 190のきろく - Flkanjin’s 競プロ録

ABC189の参戦録を書いたところですがABC190の参戦録も書いていきたいと思います。

A - Very Very Primitive Game (100点)
B - Magic 3 (200点)
C - Bowls and Dishes (300点)
D - Staircase Sequences (400点)
E - Magical Ornament (500点)
F - Shift and Inversions (600点)
結果、感想

A - Very Very Primitive Game (100点)

$A \gt B$ なら高橋くんが、 $A \lt B$ なら青木くんが勝ち、同数なら後手の勝ち、簡単簡単、とサンプル通さずに提出したらWAが返ってきてしまいました...。焦ってしまい何が間違ってるのか分からなくなってしまったので愚直にシミュレーションして答えを求めるようなコードに変更しました。
後で問題のコードを見直してみると

if(A > B){
    std::cout << "Takahashi" << std::endl;
    return 0;
}else if(B < A){
    std::cout << "Aoki" << std::endl;
    return 0;
}
std::cout << (C ? "Takahashi" : "Aoki") << std::endl;

とB > AとすべきところをB < Aとしてしまっていたのが原因でした。解説にあるようにA + C > Bという条件式でやればよかったなぁと反省しています。

B - Magic 3 (200点)

$S \gt X_i$ かつ $D \lt Y_i$ となるような $i$ が存在するかという問題で、順に見ていけばいいです。A問題でWA出してしまっていたので発狂しながらコード書いてました。

C - Bowls and Dishes (300点)

$K$ 人の人間について皿 $C_i$ と皿 $D_i$ のどちらの皿にボールを置くかを $2^K$ 通りをbit全探索で全て探索して最大値を求める。
この問題を通した時点で18分ぐらいが経過していたので今回やばいなと思ってました。

D - Staircase Sequences (400点)

初項 $a$ 、長さ $n$ 、公差 $1$ の等差数列の総和は $\displaystyle\frac{1}{2}n(2a+n-1)$ となるので $2N=n(2a+n-1)$ を満たす $(a,\,n)$ の組の数を求めます。 $n$ も $2a+n-1$ も整数なので、 $n$ は $2N$ の約数となります。 $n$ を1つ決め打ちした時、 $a = \displaystyle\frac{\dfrac{2N}{n} - n +1}{2}$ となりますが数列の要素は全て整数であるため $a$ が整数である必要があります。これを確かめるのには整数型で $a$ を求めた後、上の公式に当てはめて $2N$ になるかをみればいいです。
約数列挙は $O(\sqrt{N})$ なので十分間に合いました。

E - Magical Ornament (500点)

$K$ の値が $17$ 以下と小さいのでbit系かなと思いました。そこから最短Hamilton路問題(戻ってこなくてもいい巡回セールスマン問題)じゃないかなと思って考察していきました。
魔法石を頂点、隣り合わせにできる組を辺とした無向グラフを考えます。このグラフにおいてDijkstraやBFSを用いることで全ての $(i,\,j)$ の組について $C_i$ と $C_j$ の間の距離が求まります。ここでの計算量は $O(KN \log M)$ (Dijkstraの場合)、もしくは $O(K(N+M))$ (BFSの場合)となります。
次に $(C_1,\,\dots,\,C_K)$ を頂点、各頂点間の辺の重みを前のグラフでの対応する頂点間の距離となるような重み付き無向グラフを考えると、求める答えはこのグラフ上の最短Hamilton路の長さ+1となります。このグラフでは三角不等式が成立するのでbitDPで求まります。 $S$ を $\{C_1,\,\dots,\,C_K\}$ の部分集合、 $i \in S$ として $$ {\mathrm{dp}}_{S,i} = (\text{$S$ の各頂点のみを考慮した頂点 $i$ を終点とする最短 Hamilton 路の長さ}) $$ とすると、 $$ {\mathrm{dp}}_{\{i\},i} =0 $$ $$ {\mathrm{dp}}_{S,i} =\displaystyle\min_{j \in S} \{ {\mathrm{dp}}_{S \setminus \{i\},j} + (C_i,\,C_j\text{ 間の距離})\} $$
という漸化式で求まります。このbitDPは $O(2^KK^2)$ で求まります。ここで $S$ は $s = \displaystyle\sum_{i \in S} 2^{(i-1)}$ という整数 $s$ で表現することができます。再帰関数で実装することもできますが、 $s \leq t$ のとき $S \subseteq T$ であるので、単純にfor文で下から見ればいいです。

F - Shift and Inversions (600点)

転倒数そのものはセグ木やBITで $O(N \log N)$ で求まるけど、それを $N$ 回行うと $O(N^2 \log N)$ となって間に合わない...うーむ、どうしたものか、各遷移の差分が $O(1)$ で求まらないかなと考えてみました。
遷移の様子を見てみると、先頭の要素を最後に持っていくときに、その要素よりも小さな要素の数だけ転倒数は減り、大きな要素の数だけ転倒数が増えることが分かります。ここで私は最初の転倒数を求める時にそれより左にある大きな要素の数を求めるのでそれを利用して必要なものを求めました。しかし、この問題では $A$ は $0,\,1,\,\dots,\,N-1$ の順列となっているので $a_i$ を先頭から末尾に移動させるときの差分が $(N-1-a_i) - a_i = N-1-2a_i$ と分かるのでそんなことしなくてもよかったなぁという感じでした。

結果、感想

f:id:Flkanjin:20210201205314p:plain
A問題でWAを出して時間を溶かしてしまったときは、嗚呼、今回はレート冷えるだろうなと思っていましたが、何とか全完してレートを冷やさずに温めることができました。でも、こんなに焦ってもいいことはないので、こういった事態をできるだけ避けていきたいところですね。