はじめに
こんにちは！jastawayです。ABC384の参加記です！
今回を含めて今年のABCも残すところあと3回となりました。年内にレート1900いけたら嬉しいですね。
目次
ABC384
参加前の私のレートは1801でした。私の前回の記事の回で全完大勝利を収め、先々週のABC382で60位、初カンストパフォでしたが、先週のABC, ARCで青下位パフォでレートを溶かしました😭。(青パフォでレート下がるのまだ慣れない・・・)
今回の配点は100-200-300-400-450-500-575で、F問題までは落とせず、全完も不可能ではないセットだと思いました。
溶かしたレートを取り戻す意気込みでスタート！！
以下、各問題の考察&感想です。
A問題
問題文: A - aaaadaa
KCPCメンバー(rated 参加)のAC数: 9/9
diff: 11
言われたとおりに、forループを回して$S$の各文字について、$c_1$と一致してなければ$c_2$に置き換えればOK
0:45に提出、AC。
B問題
問題文: B - ARC Division
KCPCメンバー(rated 参加)のAC数: 9/9
diff: 30
これは愚直にシミュレーションすればできます。
現在の高橋くんのレート$R$を管理して、レートの範囲に入っていれば$A$を足し込みます。
私はテンプレートに、$x$が$L \leq x < R$を満たすかを返す関数を置いているのでこれを使って少し楽に実装できました。(llはlong longのマクロです)
inline bool inLR(ll x, ll L, ll R){ return (L <= x && x < R); }
2:37に提出、AC。
C問題
KCPCメンバー(rated 参加)のAC数: 9/9
diff: 187
bit全探索の問題です。 名前は各文字を使うor使わないの2通りずつ、全部で $2^{5} - 1 = 31 $ 通り(全部使わないは無い)で、この各文字の使う使わないをbitに対応させます。
例えば、BCEさんは $ 0\cdot 2^{0} + 1\cdot 2^{1} + 1\cdot 2^{2} + 0\cdot 2^{3} + 1\cdot 2^{4} = 22 $ の整数で表されます。
このようにするとすべての名前は$1$〜$31$で表されるのでforで回せばいいです。
逆に数$n$が与えられるとそれを2進数展開すると名前がわかります。
入力は5つの変数で取るのではなく、長さ5の配列として取ると扱いやすいです。
i+'A'とすることで、入力配列と合わせて各文字の処理をfor文で扱えます。
計算した点数と名前は点数を$-1$倍してvector<pair<int, string>>にpush_backすることで、最後にこれを昇順ソートすると、点数の高い順に、同じなら辞書順で小さい順に並び替えれます。
6:19に提出、AC。
D問題
KCPCメンバー(rated 参加)のAC数: 9/9
diff: 666
無限数列は一旦置いといて、数列$A$の連続部分列の和が$S$となるものが存在するかという問題は典型で、$A$の累積和$cA$を用いて$cA_{i} - cA_{j}=S$となる$i,j$の組は存在するかと同じです。
これは今まで見てきた累積和の値の集合$X$を用意して、$i$を前から順に$X$に$cA_{i} - S$が入っているかを調べればよいです。
$X$として標準ライブラリのsetなどを用いると、$O(N \log N)$や$O(N)$で解けます。
周期$N$の無限数列ということは、$ S \geq \sum A_i $だと、答えの連続部分列のうち $A$ がそのまま入っているところを全部消す($ S $を$ \sum A_i $で割ったあまりに置き換える)ことで、$S < \sum A_{i}$として考えてもよいことになります。
また、 $ A_{N - 1 } + A_0 + A_1 + \cdots $ というような前と後ろがくっついた部分も考えたいので、$A$ を2つ並べたものを新しい $A$ として、すべて $ \mod \sum A_{i} $ で考えれば、有限のときと同じ方法で解けます。
ループを$2N$にするのを忘れてたのと、累積和の差などでも$ \mod \sum A_{i} $にしないといけないのを忘れてて2ペナつけてしまいました・・・
13:52 に提出、AC。
E問題
KCPCメンバー(rated 参加)のAC数: 9/9
diff: 1002
現在高橋くんに隣接しているスライムのにおいて、吸収可能なものは今後いつでも吸収できるため、強さが小さい順に貪欲に選んでよいことがわかります。
つまり、priority_queueに隣接するスライムの強さと座標を入れて、最も弱いものが吸収できなくなるまで取り出して、取り出したスライムに隣接するものを更に追加するという方針で良さそうです。
このとき、同じスライムを複数回入れないように、入れたスライムを管理する必要があります。
この方針で提出！！・・・WA×2？？？？
怪しい部分がないか見直すと、吸収できるかの比較でオーバーフローしていそうだと気づきました・・・
$1/X$倍未満ということで整数の範囲で扱うために$X$をかけていたのですが、そこがダメでした。
めんどくさかったので、C++の__int128tにキャストして対応しました。
27:45 に提出、AC。
F問題
問題文: F - Double Sum 2
KCPCメンバー(rated 参加)のAC数: 1/9
diff: 1908
Eまでだいぶ早く解きましたが、3ペナもしているので、Fを解かなければどんどん抜かれるだろうと思って不安になってました。
最近よく見る、2重シグマの問題です。
はじめ2で割れる回数だと誤読してて、少し時間をロスしてしまいました・・・
まず、そのまま足されるのは、偶数+奇数となるもので、2の倍数になるのは、偶数と奇数に分けてさらに2bit目で分けて・・・とか考えてましたが、ちょっと違いそう。
最終的に、$ k=1, \dots , 30 $くらいに対して、和が $2^{k - 1}$ の倍数であるが、 $2^{k}$の倍数ではないペアの総和を計算できればいいと気づきました。
各$k$についてmap<ll, pair<ll, ll>> sumでこれまでの、$A_{i}$を$2^{k}$で割ったあまりが$r$のものの総和とその個数を管理することで、$A_{j}$を使うときはあまりを$r$とすると$rp = 2^{k - 1} - r \mod 2^{k}$を用いて、sum[rp].first + A[j]*sum[rp].secondを足していけば上のペアの総和が求められます。
77:21 に提出、AC。
3114 msで危なかったです(制限4秒)
G問題
問題文: G - Another Shuffle Window
KCPCメンバー(rated 参加)のAC数: 0/9
diff: 2343
3ペナがあるのでまだ安心はできず、G問題にチャレンジ！
$X, Y$が固定されてたら、seg木やfenwick木のソートした位置に値と個数を入れることで、$A_{i}$ or $B_{i}$より大きいところと小さいところで分けて総和をとれば$O(N \log N)$で解けるのは有名です。
しかし、$X, Y$が$K \leq 10^{4}$個あるので、そのままは使えません。
$X, Y$を1動かしたときの答えの差分は$O(\log N)$くらいで計算できるので、これはMo's algorithmで解けそうだと思いました！
残り時間は10分程度なので、急いで実装に取り掛かります。
手元にあるMoのライブラリは改変が難しそうだったので、改変が簡単そうなものをググって拝借させていただきます。
そうこうしているうちに、時間切れ・・・。全完とはなりませんでした・・・
コンテスト結果・感想
A~F6完（77:21 + 3ペナ）で 369位、1973パフォ 、レートは1801→1819でした！
勝ちではありますが、DEでの3ペナが痛いですね・・・。これがなければ黃パフォ取れそうでした。
やはりGの方針はあってたので、Moの練習をもっとすべきですね。
ところで、年明けにKUPC(2025/1/5)があります！！
私も微力ながら運営に携わらせていただくので、興味のある方はぜひご参加ください！！！お待ちしております！！！
