Yuulis.log

トンネルを抜けるとそこは参照エラーであった。

【AtCoder】AtCoder Beginner Contest 401 - 参加記 | 緑コーダーが解くAtCoder

AtCoder-ABC-コンテストまとめ AtCoder-ABC AtCoder ABC コンテストまとめ競技プログラミング

コンテスト時間: 2025-04-12(土) 21:00 ~ 2025-04-12(土) 22:40 (100分)

A - Status Code

Difficulty: ??? / NoviSteps: 8Q

解答時間: 1:13

$100$ 以上 $999$ 以下の整数 $S$ が与えられるので、 $S$ が $200$ 以上 $299$ 以下のときSuccess、そうでないときFailureと出力せよ。

$S$ を受け取り、言われたとおりに条件分岐してやればよい。

B - Unauthorized

Difficulty: ??? / NoviSteps: 6Q

解答時間: 2:45

高橋くんはあるウェブサイトに対して $N$ 回の操作を行った(操作4種類は省略)。高橋くんがログインしていない状態で非公開ページにアクセスした時、ウェブサイトは認証エラーを返す。はじめ、高橋くんはログインしていない状態である。 $N$ 回の操作のうち、高橋くんが認証エラーを受け取った回数を出力せよ。

現在のログインフラグを持っておくと、認証エラーになるのは、「フラグが立っていない状態で $S_i =$ privateである」とき。
あとは操作をシミュレーションしながらこのような $i$ の個数をカウントしていけばよい。

C - K-bonacci

Difficulty: ??? / NoviSteps: 3Q

解答時間: 10:01

正整数が与えられる。長さの数列の各要素の値を、以下の方法で定義するとき、をで割った余りを求めよ。
- $0\leq i \lt K$ のとき、 $A_i=1$
- $K\leq i$ のとき、 $A_i=A_{i-K}+A_{i-K+1}+\cdots+A_{i-1}$

素直にやると $K \leq i$ のときの $A_i$ の計算に $O(K)$ の時間がかかってしまう。
ここを累積和で処理して $O(1)$ に高速化すれば、全体を $O(N)$ で計算できる。
mod の計算には、 ACL のmodintを使うと楽。なんで $10^9 + 7$ でないのかは謎。

D - Logical Filling

Difficulty: ??? / NoviSteps: 1D

., o, ?のみからなる長さの文字列が与えられる。全ての?をそれぞれ.またはoで置き換えて得られる文字列のうち、以下の条件を全て満たすものの集合をとする( が空集合出ないことは保証される)。
- oの個数がちょうど $K$ 個
- oが連続しない
以下を満たす、長さの文字列を出力せよ。
- $X$ に含まれる全ての文字列の $i$ 文字目が.である場合： $T_i=$ .
- $X$ に含まれる全ての文字列の $i$ 文字目がoである場合： $T_i=$ o
- $i$ 文字目が.である文字列もoである文字列も $X$ に含まれている場合： $T_i=$ ?

まず、oは隣接して配置できないので、oに隣接している?は.で確定する。
その上で、もし $S$ 内のoの個数が $K$ に等しいならば、それ以上oは配置できないので、残りの?を全て.に置き換えて出力する。
内のoの個数がよりも少ないとき、連続した?の区間(seg)を抽出してくる。このsegそれぞれに対して、可能な限りoを詰めこむことを考える。このときのoの個数は、segの長さとして個である。全てのsegに対するこの個数の総和をとする。
- $\mathrm{max\_o} = K$ のとき、segの長さが奇数であるものについてはoと.を交互に配置する方法で一意に定まるが、偶数であるものについては先頭をoにするか.にするかで2通り考えられるので確定しない。
- 問題は $\mathrm{max\_o} \gt K$ のときなのだが、このときの処理がよくわからずごまかして提出したら WA になってしまった(他の箇所でバグっていたのかもしれない)。

結論としては、 $S$ そのものを出力してしまえばよいようだ(証明は公式解説参照)。

結果

Performance: 942

1003 → 997 (-6)

そろそろ停滞期に入ってきたか...？