はじめに
こんにちは！jastawayです。ABC411の参加記です！！(ABC412ではありません)
投稿が次のABC終わりになってすみません🙇♂️
最近はICPC国内予選のチーム練を頑張っています！
私はチームbogosortで今年度のICPCに参加します！！
国内予選は他の大学のチームとの争いというより、京大内での争いが激しいですが、横浜目指してがんばります！
目次
ABC411
参加前の私のレートは1946でした。
ABC409で98位カンストパフォを取り、無事再入黄を果たしましたが、ARC200(Div.2)で0完☀️を取り落青となりました🥺🥺🥺
そのため今回のABCはRatedとなります。
今回の配点は100-200-350-425-450-525-600で6完は必須、Gも解きたいところです。
カンストパフォ取れば黄色復帰できるので、早解きしたいです。
以下、各問題の考察&感想です。
A問題
問題文: A - Required Length
KCPCメンバー(rated 参加)のAC数: 21/21
diff: 11
$S$ をstringで受け取って、そのサイズを $L$ と比較するだけです。
S.size()で $S$ のサイズを取得できます。
0:47に提出、AC。
B問題
問題文: B - Distance Table
KCPCメンバー(rated 参加)のAC数: 21/21
diff: 32
駅 $i, j$ 間の距離を計算するのは累積和を前計算しておくと各 $O(1)$ 時間で求められます。
具体的には以下のように書くと求められます。
// 累積和 for(int i = 0; i < N-1; i++) sD[i+1] = sD[i] + D[i] // i-jの距離 sD[i+1] - sD[j]
あとは出力形式に注意して出力すれば全体で $O(N^2)$ 時間で求められます。
制約的には累積和を使わなくても $O(N^3)$ で通るし、始点を決めれば足してくだけで $O(N^2)$ で解けます。
2:54に提出、AC。
C問題
問題文: C - Black Intervals
KCPCメンバー(rated 参加)のAC数: 19/21
diff: 234
350点C問題です。
$N, Q$ の制約が大きいので、愚直に毎回数えているのでは間に合いません。
そこで、黒の区間をset<pair<int, int>>で管理することを考えます。
白を黒に変えるときは、その座標が隣接している区間を取り出して、伸ばしたり、結合したりします。
黒を白にかえるときは、属している区間を取り出して、縮めたり、分割したりします。
これらは、set.lower_bound()などを使って頑張って区間を取り出します。
間違えたくなかったので、左右の色の全8パターンを場合分けして実装しました。
350点とはいえ、実装重すぎないか？と思いましたが、なんとか実装できました。
13:48に提出、AC。
コンテスト後、黒の区間の増減だけ考えれば良くて、それは左右の色だけで決まると聞いて確かにとなりました・・・
D問題
問題文: D - Conflict 2
KCPCメンバー(rated 参加)のAC数: 12/21
diff: 1018
愚直に文字列をコピーしていては間に合いません。
最後のサーバーだけ知りたいので、無駄な処理をしないことを考えます。
例えば、コピーしたあとに参照せずに別の文字列で置き換えたとき、最初の置き換えはいらないということになります。
また、最後のサーバーに影響しない置き換えも必要ありません。
直感では、クエリを後ろから見ていって参照していくところを移動すればできそうですが、具体的にどうすればいいのかすぐに思いつきません。
沼りそうだったので、一旦E問題に移りました。
E問題
問題文: E - E [max]
KCPCメンバー(rated 参加)のAC数: 11/21
diff: 1400
Dが解けてなくてやばいです。早くEを解いてDに戻りたい。
最大値が $k$ となる確率 $P(X=k)$ を求めたいです。
これは受験数学でよくある(?)もので、 $P(X=k) = P(X \leq k) - P(X \leq k - 1)$ を使います。
つまり、上を向いた面に書かれた数字がすべて $k$ 以下になる確率を求めればいいです。
これは、各サイコロについて、最大値が $k$ になる確率を求めて(高々6通り)、答えの配列のある区間にその確率をかけ込めばできます。
区間にかけ込むのは、愚直にやれば時間がかかってしまいますが、全体で取りうる値を座標圧縮しておき、imos法でその値と逆元を端にかければあとから求めれます。
このとき、最大値になりえないところは $0$ にする必要がありますが、それは最後に $0$ にすれば大丈夫です。
確率が求まると、期待値はすぐに求まります。
47:33 に提出、AC。
D問題再び
色々考えて、やっぱり、後ろから考えるのが良さそうです。
答えの文字列を用意しておいて、今見るべき場所を管理します。初期値はそれぞれ、空とサーバーです。
クエリ先読みをし、後ろのクエリから考えます。
1番目のクエリで、 $p$ が今見ているPCなら、今見る場所をサーバーに変更します。
2番目のクエリで、 $p$ が今見ているPCなら、答えの先頭に $s$ を追加します。
3番目のクエリで、 今見ているのがサーバーなら、PC $p$ に変更します。
これをすると答えが求まります。
実装上は、逆順の答えを持っておいて、入力を逆順にして後ろにinsertしました。
47:33 に提出、AC。
不安でしたがなんとか通せてよかったです。
F問題
問題文: F - Contraction
KCPCメンバー(rated 参加)のAC数: 3/21
diff: 1507
遅いのでFは通さないとやばいです。
無向グラフを隣接リストのように持っておいた時、辺を縮約するのは、そのリストをマージする感じで、マージされる側(?)の頂点に隣接する頂点についてもリストを変更する必要があります。
これはマージテクによって実現できそうです。
頂点を削除したりマージしたりしないといけないので、このリストをset<int>で持つことを考えます。
また、握手補題より、辺の本数は次数の総和の半分。つまり、リストに入っている頂点数の総和の半分と等しいのでこれを数えることにしました。
Union Findなどで縮約できるかを管理し、マージするときは要素が多い方に少ない方入れる、マージテクと呼ばれる手法を使うと、頂点の移動が全体で高々 $O(N \log N)$ 回しかかからないので、これで頑張って実装します。
頑張って実装しますが、なぜかサンプルが合いません。
色々デバッグした結果、頂点を受け取るときに0-indexedに直すのを忘れてただけでした・・・😭😭😭
87:11 に提出、AC。
G問題
問題文: G - Count Cycles
KCPCメンバー(rated 参加)のAC数: 0/21
diff: 2093
Fまで時間がかかりすぎなので、Gも通したいが時間がありません
読むと、bitDPするだけでは？となりました。
「 $dp[st][S][j] = st$ を始点として集合 $S$ を1度ずつ通って今 $j$ にいる場合の数」みたいなDPで解けそうです。
時間もないので、急いで実装をしますが、ここで時間切れ・・・
コンテスト後、延長戦をして書き切りますが、TLE・・・
よく考えると $N \leq 20$ なので $O(2^{N} N^3)$ は通りませんでした・・・
高速化で、始点 $st$ を決めると、 $j$ は $j \geq st$ のみを考えればいいので、それで実装すると通りました・・・提出 (定数倍高速化ではなく、 $O( \sum 2^{k} k^2 ) = O(2^N N^2)$ で計算量が落ちてました。)
コンテスト結果・感想
A~F6完（87:11 + 0ペナ）で 330位、1955パフォ、レートは1945→1946でした。
ノーペナなのはいいですが、D,Fが遅くて負けました・・・
時間があればGは解ける問題だったので惜しいです・・・
早く黄色に戻りたいです・・・
