はじめに
初の4完でした。やったぜ。
成績：ABCD4完（1000）
A
sが200以上299以下ならSuccess、そうでなければFailureを出力する。
s = int(input())
if s >= 200 and s <= 299:
print("Success")
else:
print("Failure")
A問題としても簡単な部類に思える。
B
ログインしているかどうかをフラグ管理し、loginとlogoutが入力されたらその都度切り替える。で、ログインしていない状態でprivateが入力されたらエラー回数に加算する。
n = int(input())
login = False
err = 0
for _ in range(n):
s = input()
if s == "login":
login = True
elif s == "logout":
login = False
elif s == "private":
if login == False:
err += 1
print(err)
これも特にコメントすることがない。
C
$A_0$から$A_{K-1}$までは1が並び、$A_K$は$K$、 その後は自分より前の$K$項の合計が$A_N$まで続く。ということで$A_{K+1}$以降が何になるかを計算するが、毎回愚直にやっていると間に合わないので前の区間からの差分を考える。
$A_{i+1}$を求めたいとき、$A_{i-k}$から$A_{i-1}$までの合計が$A_i$であることを考えると、$A_{i-k+1}$から$A_{i}$までの合計である$A_{i+1}$は、$A_{i}$から$A_{i-k}$を引いて$A_{i}$を足すことで求められる。
n,k = map(int,input().split())
num = 10**9
if n < k:
print(1)
exit()
A = []
for _ in range(k):
A.append(1)
A.append(k)
for i in range(k,n):
A.append(A[i]%num + A[i]%num - A[i-k]%num)
print(A[-1]%num)
求める項は常にその前$k$個の項の合計なので、$k$個の区間を1つずつずらしていくと考えるとイメージしやすかった。
なお、以下のようにAに追加するところでもう一度除算する方が安全な気がする。
A.append((A[i]%num + A[i]%num - A[i-k]%num)%num)
今回は$10^9$のあまりなので提出したコードでも正解したが、998244353とかだったら1ペナついていたのではないか。
D
求める文字列$T$は元の文字列$S$で?となっている場所を置き換えたものなので、$S$で.やoである場所はそのまま。また、$X$の2番目の条件から、$S$でoである場所の隣は.であることも分かる。
以上の条件を満たすように$T$を仮組みした上で、?のうちまだ確定させられる部分があるかを考えていくと、以下の2つの場合で確定させられることに気づく。
①$k$が$S$に含まれるoの数と同じとき
これは単純で、もうoを入れる余地がないので$T$の?になっている部分はすべて.としてよい。
②?にoを最大限詰め込んだときのoの数と$k$の値が同じとき
$k$の値的に$T$にoを最大限詰め込める時、$T$で?となっている場所に可能な限りoを詰め込んでいくと、?が奇数個並んでいる場所はo.o.oのように1通りに確定するが、?が偶数個並んでいる場所はo.o.と.o.oのように2通り考えられるので確定しない。
ということで、?が奇数個並んでいる時のみo.o.o……と順番に入れていくとそれが$T$になる。
n,k = map(int,input().split())
s = input()
ans = ['?' for _ in range(n)]
ocnt = 0
for i in range(n):
if s[i] == '.':
ans[i] = '.'
elif s[i] == 'o':
ans[i] = 'o'
ocnt += 1
elif i >= 1 and s[i-1] == 'o':
ans[i] = '.'
elif i < n-1 and s[i+1] == 'o':
ans[i] = '.'
if ocnt == k: #もうoを全部使ったならあとは全部.
for i in range(n):
if ans[i] == '?':
ans[i] = '.'
print("".join(ans))
exit()
#最大パターンを作る。
maxp = ans.copy()
cont = []
combo = 0
for i in range(n):
if ans[i] == '?' and combo == 0:
start = i
combo += 1
elif ans[i] == '?':
combo += 1
elif ans[i] != '?' and combo != 0:
cont.append((start,i-1))
combo = 0
if combo != 0:
cont.append((start,n-1))
omaxp = ocnt
for start,end in cont:
if (end-start)%2 == 1:
omaxp += (end-start+1)//2
pass
else:
omaxp += (end-start+2)//2
for i in range(start,end+1):
if i%2 == start%2:
maxp[i] = 'o'
else:
maxp[i] = '.'
if omaxp == k:
print("".join(maxp))
else:
print("".join(ans))
②を満たすkの値を先に計算しようとしたが面倒だったので、②の場合の$T$を作ってしまってその時のoの数と$k$が一致したときだけ採用するという形にした。
①$\leq k \leq$②である時は確定できる?はないだろうと直感的に思ったのでそのまま進めた。
ついに初4完達成！C問題までが素直な内容で30分以内に解けたこと、D問題も制約から考察で解くやつだと早めに見抜けたのが良かった。緑になるにはこの「Cまでを早めに解いてDをときどき通す」という方針を繰り返していくことだろう。