4完2WA
からの?
各問題
A - Status Code
いわれたとおりにやりましょう
B - Unauthorized
ログイン状態を記憶しておき、ログインしていない状態で private が来た回数を数えます。
C - K-bonacci
累積和を取りながら A を埋めていけばよいです。(以下 sum[i + 1] に i までの累積和が入っているとする)
i < K の時は A[i] に 1 を入れます。i >= K の時は sum[i + 1] - sum[i - k] です。
都度 109 で割ったあまりをとるのを忘れずに。
D - Logical Filling
まず S に存在する o
の数が K と一致する場合は、残りの ?
はすべて .
です。(これを忘れていて 1WA)
X が空集合でないことが保証されているので、o
と隣接する ?
は必ず .
としてよいです。
あとは ?
が連続する部分のそれぞれについて、 o
が最大いくつ置けるかを数えていきます。その最大数が、K からすでにある o
の数を引いたものより大きかった場合、o
の位置は特定しないので残っている ?
はそのままにせざるを得ず、それが最終的な答えとなります。
一致した場合、o
はおけるだけおけばいいのですが ?
の連続数が偶数個の場合は .o.o
と o.o.
が決められないので ?
のままになります。奇数個の場合は o.o.o
のように確定します。
E - Reachable Set
1 <= k <= Nについて、頂点 k までの頂点から伸びる辺で構成されたグラフで 1 から k までが連結であるかどうかと、グラフ上で k 以下の頂点が繋がっている k より大きい頂点の数を記憶することで答えが導き出せます。
前者は dsu を使って、接続先の頂点 x が k 未満の辺はマージして、k より大きい辺はいったんプールしておいて x が k 未満になった段階で改めてマージするとすればよいです。後者は各頂点について接続済みかどうかのフラグを持っておけばよいです。
解けたんですが、最初無駄に set を複数使ってしまい TLE を出し、set を使わなくて済む実装を残り 20 秒で思いつき、10秒くらいで慌てて提出したらバグがあって RE でゲームセットでした。そして終了 2 分後に AC を得ました...。
まとめ
緑パフォストリーク継続中ですが、E が通せていれば水色だったので復活の兆しがある、と信じたい。