AtCoder Beginner Contest 396
お久しぶりです。
最近ブログというか競プロそのものにかける時間がほとんど取れず、二週間ABCをお休みしていました。
2,3日前にABC396をバチャでやっと走れたので、今回はその「感想」として、どんなことを考えながら解いたのかを簡単にまとめたいと思います。（解説要素はほぼないので、感想です）
結果、ABCDの4完（33分0ペナ）でした。
unratedですが、AC predictorによると1162perfらしいです。
今回はA~Eまでの感想を述べていきます。
A - Triple Four
問題文の「より厳密には〜」以降をそのままプログラムに書けば良いですね。
良心的な問題です。
B - Card Pile
山札の一番上しか参照しなくて良いということで、スタックで十分そうです。
また、クエリ2では必ず山札にカードがあることが保証されているので、特に例外的な処理も書く必要がなさそうですね。
C - Buy Balls
黒のボールが白のボールと同じか、それより多くなければなりません。
一見、$B_i$と$W_i$がどちらも正のものだけ取り出して、黒のボールが白のボール以上であるように白のボールのうち値が小さいものから減らして調整すればよいのではないかと思うかもしれませんが、値がマイナスの黒のボールを選んだ時に最適となるような組み合わせもあるのでそう簡単ではありません。
実は、次のようなアルゴリズムで最適な値を得ることができます。
- $B,W$を降順にソートする
- $B_w+W_w≧0$かつ$W_w≧0$を満たす限りインデックス$w$を進める
- その後、$b=w$とした後、$B_b≧0$を満たす限りインデックス$b$を進める
- $B_b+W_w$を得る。これが求める最適値である。
D - Minimum XOR Path
これは計算量解析が難しいのですが、ただのdfsで間に合いました。
JavaScriptでは$10^{15}$以上のxor計算が遅すぎるので、こっそりとPythonを使ってACしました笑
E - Min of Restricted Sum
1時間の長考の末、全くわかりませんでした笑
なんとなく、整数列を頂点、$A_i$を頂点$i$の重み、$Z_i$を$A_{X_i}$と$A_{Y_i}$を結ぶ辺の重みとしてグラフとして考えた時に、連結頂点のうち一つは$A_x=0$となるようなゼロ点$x$を含む、閉路が一つでもある場合は閉路内の頂点のxor和が0でなければ破綻する、などの必要条件が思い浮かびましたが、結局$A_x=0$として最適な値を得る頂点$x$の高速な求め方がわかりませんでした。
解説を見ていないので方針から間違っているかもしれません笑
まとめ
10日ほど競プロから離れていた割には高いperfが出ていましたが、水色に全く歯が立たないのは悔しいです。
また、ABC397も解いて感想をupする予定です。
少し精進ペースは落ちますが、今後も引き続き頑張っていきます