はじめに
こんにちは！jastawayです。ABC396の参加記です！！
今回はKCPCブログ初のアンレ参加の記事となります。緊張感は少し減りますが、本気で参加したのでぜひ最後までご覧ください！
最近、これまで使っていたテンプレートを結構変えました。まだ慣れていないので(たまに前のテンプレで使ってたマクロを打ってしまう)早く慣れておきたいところ。
目次
ABC396
参加前の私のレートは2010でした。
そうです。今回アンレとなったのは前回のABC395で早解き6完の2397パフォで入黄したからです！
来年度のICPC国内予選までに黄色になるという目標だったので、非常に嬉しいです！
ですが、安心できません。ARCやAGCですぐに青に落ちる可能性が大いにあります。いつ落青してもいいように、ABCにはできるだけ参加していきます！
今回の配点は100-200-300-400-450-500-600で、Fまで早解きは必須。もしかしたらGも解けるかも、といったところです。
レートが賭かっていないぶんいつもより気楽にスタート！
以下、各問題の考察&感想です。
A問題
問題文: A - Triple Four
KCPCメンバー(rated 参加)のAC数: 9/9
diff: 13
添字をforで回して、$ A_{i} = A_{i + 1} = A_{i + 2} $を確かめればOK。0-indexedにおいて、$i<N-2$までということに注意。
0:48に提出、AC。
B問題
問題文: B - Card Pile
KCPCメンバー(rated 参加)のAC数: 9/9
diff: 37
これはまさにstackです。実装はstd::vectorを用いましたが、初めに$0$を$100$個入れたものを用意しておいて、push_back(x)、pop_back()で末尾に追加、削除できます。
末尾の要素のアクセスにはback()が便利です。
1:55に提出、AC。
C問題
問題文: C - Buy Balls
KCPCメンバー(rated 参加)のAC数: 9/9
diff: 291
ボールの順番はどうでもいいので、$B$、$W$ともに降順にソートして良さそうです。
黒は全部使って良くて、$N$を超えないように白を前から使えばいいと思い実装しますが、サンプルが合いません・・・。
価値は負の数も取りうるではないか！
じゃあ、$B$も$W$も非負のものだけ考えて同じように貪欲すればいいかと思いますが、またもサンプルが合いません・・・。
あ、どっちかが負になっても、それ以上に価値が得られればいいパターンあるやん。
ということで、黒の個数の取りうるパターンを全探索することに。
これは$B$の累積和$sB$と、$\max (0, W_{i})$の累積和$sW$を前計算しておけば$\max (sB_{i} + sW_{i})$で答えが求まります。
実装してやっとサンプルが全部通ったので提出！！！
・・・RE・・・
黄色コーダーさん その問題、C問題ですよ？(例の顔)
$sW$のサイズを$M+1$にしていたせいで、$ N > M $のときに範囲外参照してました😭
$N$まで見るのでサイズを$N+1$に変更して、累積和の計算でも範囲外参照しないように直して提出！！！
・・・RE・・・
黄色コーダーさん その問題、C問題ですよ？(2回目)
はい、累積和の計算で$N$までにしないといけないのに、直し忘れて$ M $まで回してました。これでは$ N < M $のときに範囲外参照です。
訂正して3度目の正直！
10:55に提出、無事AC。
D問題
問題文: D - Minimum XOR Path
KCPCメンバー(rated 参加)のAC数: 9/9
diff: 601
$N \leq 10$と非常に小さいので、頂点$1$から$N$までの単純パスを全探索できそうです。(高々$(N-2)!$通り)
next_permutationで順列全探索してもいいですが、DFSで簡単に書けそうです。
現在のXORと訪れた頂点のフラグを管理しておいて、DFSし、頂点$N$にたどり着いたら、答えとchange maxします。
再帰関数を抜けるときになどに、現在のXORとフラグを元に戻すことに注意が必要です。(パスを列挙するときは、フラグなどを全部もとに戻す。連結性などを調べるときは一度訪れたフラグは元に戻さない。)
15:08 に提出、AC。
E問題
問題文: E - Min of Restricted Sum
KCPCメンバー(rated 参加)のAC数: 4/9
diff: 1379
C問題で2ペナしてるので爆速で解きたいです。
重みが$ Z $の$ N $頂点$ M $辺の無向グラフとして、考えれそうです。
辺の重みに関して、条件を満たすかどうかは、ポテンシャル付き(重み付き)Union Findと似ています。しかし、今回はXORです。
これはポテンシャルとなるでしょうか？
しばらく考えて、なりそうだと思いました。
ポテンシャル付きUFのライブラリを探してきて、+や-のところを^に変えていきます。
順に辺でつなぐときに、すでに連結で、ポテンシャルの差が矛盾していたらダメ。
そうでなかったら、$A_i$を頂点$i$のポテンシャルにして提出！
・・・WA・・・
え〜、ダメなの・・・？19WAでコーナーケースなどではなく、普通に間違ってそうです・・・
ポテンシャル付きUFが使えるなら、main関数の部分は多分合ってるはずです。なのでライブラリのところをチェックします。
mergeするときに、選ぶリーダーによって重みを$-1$倍しているところを消し忘れていることを見つけました。訂正して提出！！
・・・WA・・・
なんで〜〜〜WAの数は変わりません。
こんなに違うのはなにか勘違いしているか、ポテンシャル付きUFが使えないかです。
問題文をよく読むと、$A$の総和が最小となると書いてあるではないか！？！？！？
読んでいませんでした😭😭😭
良い数列につて各連結成分に含まれるノード全部に同じ数$x$をXORしても良い数列のままであることは、同じ数同士のXORが$0$であることからすぐに分かります。
つまり、各連結成分ごとに要素の総和を最小化すればいいです。
さらに、XORはbitごとに独立なので、$0$と$1$で多数決を取って、$1$が多ければ$x$のその桁に$1$を立ててれば、そのbitの$1$の数を最小にできます。
これを実装して提出！！！
・・・WA・・・
またもや19WAです。
(ポテンシャル付きUFが使えるなら)解法は合ってるはずです。もう一度ライブラリを見直します。
経路圧縮時に、ポテンシャルの更新をXORに変えるのを忘れてました🥺
4度目の正直で提出！！！！
52:39 に提出、やっとAC。
F問題
KCPCメンバー(rated 参加)のAC数: 7/9
diff: 1479
ペナ数がやばいです。早く解いてもすぐに追い抜かれそうなので、Gまで解きたいですが、まずはFを解かないと。
転倒数はBIT(fenwic tree)などを使って、$ O(N \log N) $で計算できます。しかし、愚直にすると$ O(NM \log N) $で間に合いません。
$ A $の要素が$ [0, M) $の中央あたりに固まっているときを考えると、ほとんどの$ k $において転倒数は変わりません。
転倒数が変わるのは $ M - 1 $ から $ 0 $ になるときだけです。そのようなのは全部で高々$ N $個しかないので、転倒数の差分計算ができそうです。
$ M - 1 $ から$ 1 $の順で$ A_i $の値を考えます。
値が $ a $ のものが $ M - 1 $ から $ 0 $ に変わるのは、 $ k = M - a $ のときです。
$ k = M - (a + 1) $のときの転倒数がわかっているとします。
$ A _{ i_{ 0 } }, \dots , A _{ i_{ m - 1 } } = a $ として、$ i_{ j } $ の左側のもので値が $ a $ でないものの個数だけ転倒数が増え、 $ i_{ j } $ の右側のもので値が $ a $ でないものの個数だけ転倒数が減ります。
つまり転倒数は $ i_{j} - j - (N - i_{j} - m + j) $ となり、差分計算ができました。
75:16 に提出、AC。
G問題
問題文: G - Flip Row or Col
KCPCメンバー(rated 参加)のAC数: 0/9
diff: 2195
あまり他の人が解いていないですが、解ければほぼ勝ち確でしょう。逆に解けなければ負けです。
$W \leq 18$と小さいです。すぐ思いつくのとして、反転させる列を全探索して$O(HW 2^{W})$が見えますが、これは間に合いません。
うまいことbitset高速化することも考えますが、それでも微妙です。($H 2^{W} / 60$になればギリ通るかも)
なにか前計算などして、$ 2^W $に$ H $がかかることを避けたいですが、何も思いつきません。
しばらく椅子を温めて、コンテストが終了しました・・・
コンテスト結果・感想
A~F6完（75:16 + 5ペナ）で 797位、1668パフォ(推定)でした😭😭
なんとか青パフォは取れましたが、CとEでのペナが痛すぎです。前回のABCで入黄しててほんと良かったです。
さて、日曜日はARC (Div. 2)があります！ここを耐えてさらなる高みを目指したいです！
落青はダメ・・・落青は嫌だ・・・お願い、落青だけは・・・
ABC Ratedに戻ってこないよう、精進がんばります！！！！
(ARC等で落青しなければ)ABCはこれからもアンレですが、参加は続けるつもりです！ブログ担当も続けるのでよろしくお願いします！！！！
