Hard No.1 : D - Gathering Children
発想
移動する過程を考えると、'RRRRR'や'LLLLL'といった同じ文字が連続した部分には子供はいなくなります。'LR'の部分にも子供はいなくなります。最終的には'RL'と書かれた部分を子供達は往復し続けることになります。よって'RL'の左側にある'R'の個数と右側にある'L'の個数を数えていけば良いでしょう。
実装
現在が'RL'よりも左側なのか右側なのかを変数rightで持ちます。左側にいる時は変数rで'R'の個数を数え、右側にいる時は変数lで'L'の個数を数えます。また、変数tmpは現在位置を表します。以下は実際のコードになります。
S = input()
Ans = [0]*len(S)
r = 0
l = 0
right = True
for i in range(len(S)):
if right:
if S[i] == 'R':
r += 1
else:
right = False
if r % 2 == 0:
Ans[i] += r//2
Ans[i-1] += r//2
else:
Ans[i-1] += (r+1)//2
Ans[i] += (r-1)//2
r = 0
l += 1
tmpi = i
if i == len(S) - 1:
Ans[i] += 1
else:
if S[i] == 'L':
l += 1
if i == len(S) - 1:
if l % 2 == 0:
Ans[tmpi-1] += l//2
Ans[tmpi] += l//2
else:
Ans[tmpi-1] += (l-1)//2
Ans[tmpi] += (l+1)//2
else:
right = True
if l % 2 == 0:
Ans[tmpi-1] += l//2
Ans[tmpi] += l//2
else:
Ans[tmpi-1] += (l-1)//2
Ans[tmpi] += (l+1)//2
l = 0
r += 1
for ans in Ans:
print(ans, end=' ')
偶奇で分ける必要があり、少し面倒ですが、この方法でO(N)で解けます。
Hard No.2 : B - Kleene Inversion
発想
転倒数の問題です。愚直に計算するとO((NK)^2)かかるので到底間に合いません。転倒数を求めるときにBITを使うとO(NKlog(NK))まで計算量を落とせますが、これでも今回の問題は間に合いません。
今回は数列Bの並び方が数列Aの繰り返しになっていることに注目します。二つの数が転倒している時、それは
（１）同じAの内部で転倒する
（２）違うAの間で転倒する
場合が考えられます。それぞれの場合で分けて計算し、後で足せば良いです。
実装
（１）同じAの内部で転倒する場合
Nは2000程度ですのでO(N^2)でも十分間に合います。AはK個あるので最後にK倍するのを忘れないように注意が必要です。
N, K = map(int, input().split())
A = list(map(int, input().split()))
ans1 = 0
for i in range(N-1):
for j in range(i+1, N):
if A[i] > A[j]:
ans1 += 1
ans1 *= K
（２）違うAの間で転倒する場合
まずは同じA内部の転倒数を求めていきますが、今回は異なるA間の転倒数を求めるのが目的ですので、A内部の順番については気にしなくてよいことになります。
二つの異なるAの選び方は$_KC_2$になりますので、求めた値に$_KC_2$をかければ良いです。
ans2 = 0
for i in range(N):
for j in range(N):
if A[i] > A[j]:
ans2 += 1
ans2 *= K * (K-1) // 2
ans = ans1 + ans2
ans %= 10**9 + 7
print(ans)
全体の計算量はO(N^2)程度になります。
Hard No.3 : A - Range Flip Find Route
発想１
昔、大学受験をしていた頃、数学の参考書で「ハッと目覚める確率」という本がありました。この本の中で非常に印象に残っている言葉がありまして、それは「題意は結局どういうことなのか解析する」というものです。つまり、分かりやすい幾つかの状況で実験してみて、解きやすい形に言い換えをしてみよということです。ですので、今回の問題も言い換えをしてみます。
実験
（１）全てのマスが白の場合
何もする必要はない
（２）全てのマスが黒の場合
全てのマスを一回で白に変えることで"良い状態"にできる。
（３）スタートとゴールの間に一本の帯状の黒マスがある場合
黒マスを一回で白に変えることで"良い状態"にできる。
言い換え
実験の結果を見ると帯状の黒マスの本数と操作回数が一致することがわかります。もう少し言い換えをすると
現在白マスにいる状態から帯状の黒マスに侵入するときに操作回数が１増える
ことがわかります。
発想２
結論を言うと今回は動的計画法（DP)を使います。それは操作回数が1増えるか増えないかの2択しかないからです。いきなり全体の操作回数を求めるのは難しいけど、一個前のマスから現在のマスに移動するときに１増えるかどうかの２択しかないので、その実装をするのは簡単だからです。一般的に最小手数の問題はDPを疑うのが良いと言われています。
実装
dpは以下のように定めれば良いです。
dp[i][j] : 現在(i, j)マスにいる時の、現在地に来るまでの操作回数の最小値
H, W = map(int, input().split())
S = []
for i in range(H):
s = input()
S.append(s)
dp = []
for i in range(H):
dp.append([10**6]*W)
ans = 0
#初期位置が黒か白かで初期値が変化
if S[0][0] == '.':
dp[0][0] = 0
else:
dp[0][0] = 1
for i in range(H):
for j in range(W):
if i-1 >= 0:
#移動前と後のマスの色が変化しない場合
if S[i-1][j] == S[i][j]:
dp[i][j] = min(dp[i][j], dp[i-1][j])
#移動前の色が黒の場合
elif S[i-1][j] == '#':
dp[i][j] = min(dp[i][j], dp[i-1][j])
#白から黒に移動する時
else:
dp[i][j] = min(dp[i][j], dp[i-1][j] + 1)
if j-1 >= 0:
if S[i][j-1] == S[i][j]:
dp[i][j] = min(dp[i][j], dp[i][j-1])
elif S[i][j-1] == '#':
dp[i][j] = min(dp[i][j], dp[i][j-1])
else:
dp[i][j] = min(dp[i][j], dp[i][j-1] + 1)
print(dp[H-1][W-1])
移動前の位置が枠の外にはみ出ないように注意が必要です。計算量はO(HW)です。
Hard No.4 : B - Between a and b ...
発想
制約の中に$10^{18}$とかあると明らかにO(1)を思いついたら勝ち！思いつかなかったら負け！敗者に人権は無い！って感じがして辛い気持ちになります。
xで割り切れる数字はxの倍数です。
ある数y以下のxの倍数の個数とyをxで割った商は一致しますので、a-1をxで割った商とbをxで割った商の引き算をすれば良いです。ただし0も割り切れる数字とみなしますので商に1を足すことになります。
実装
aが０になる場合があるので、そこだけ注意が必要です。
a, b, x = map(int, input().split())
cnt_b = b // x + 1
if a == 0:
cnt_a = 0
else:
cnt_a = (a-1)//x + 1
print(cnt_b - cnt_a)
O(1)で解けましたので人権を得ました。
Hard No.5 : D - Powerful Discount Tickets
発想
高い商品に割引券を使えば良さそうだなと思います。割引券は１つの商品にまとめて使いたくなりますが、何枚使えばいいのかはわかりません。結局は１枚づつ使っていくことになります。
一番高い商品をリストから取り出すのにO(N)、割引券の枚数がM枚なので、全体でO(NM)になり、間に合いません。
そこで優先度付きキュー(heap)を使います。heapはO(logN)で配列の最小値を取り出してくれます。今回は最大値を取り出したいので、要素全てに-1をかけた状態にしておきます。
実装
import heapq
N, M = map(int, input().split())
A = list(map(int, input().split()))
for i in range(N):
A[i] *= -1
heapq.heapify(A)
for _ in range(M):
#割引したい商品の価格を取り出す
tmp = heapq.heappop(A)
#負の値を正にする
tmp *= -1
#割引
tmp //= 2
#負の数に戻す
tmp *= -1
#heapに戻す
heapq.heappush(A, tmp)
ans = -sum(A)
print(ans)
O(MlogN)で解けます。
Hard No.6 : C - Dubious Document 2
発想
とりあえず前からS'の文字を見ていってTをはめられるか考えます。この時、答えの候補が複数出てくるから一旦リストに入れておきます。辞書順最小と言っているので、'?'の部分は全て'a'に置き換えて良いです。
実装
Sp = input()
T = input()
#答えの候補を入れるリスト
Ans = []
for i in range(len(Sp) - len(T) + 1):
for j in range(len(T)):
#TをS'にはめられなければbreak
if Sp[i+j] != T[j] and Sp[i+j] != '?':
break
else:
#TをS'にはめられた場合の文字列tmp
tmp = Sp[:i] + T
#Tをはめた後、len(tmp)<len(S')の場合
if i + len(T) < len(Sp):
tmp += Sp[i+len(T):]
Ans.append(tmp)
#答えの候補がなかった場合
if Ans == []:
print('UNRESTORABLE')
exit()
#辞書順最小のものを探す
for i in range(len(Ans)):
Ans[i] = Ans[i].replace('?', 'a')
Ans = sorted(Ans)
print(Ans[0])
Hard No.7 : D - Integer Cards
発想
M回の操作後の最大値を求めるので、
（１）選んだカードの値が$C_j$より小さいなら$C_j$に置き換える
（２）置き換えられる回数は$B_j$回まで
カードの選び方は常にN枚のカードの最小値を選べば良いのでheapを使います。
実装
XにはM回のクエリが入っていますが、これは$C_j$が大きい値からsortしておきます。大きい値から置き換え作業をしていき、あるところで置き換えしなくなったら、それ以降の置き換えは全てしなくて良いです。
N, M = map(int, input().split())
A = list(map(int, input().split()))
heapq.heapify(A)
X = []
for i in range(M):
b, c = map(int, input().split())
X.append([c, b])
X = sorted(X, reverse=True)
M回の操作とb回の置き換えをしていく。あるところで置き換えしなくなったら、それ以降の置き換えも操作もしなくて良いので、２重ループから抜け出します。
#M回の操作
for i in range(M):
c = X[i][0]
b = X[i][1]
#b回の置き換え作業
for _ in range(b):
a = heapq.heappop(A)
#取り出した値がcより小さいなら置き換え
if c > a:
heapq.heappush(A, c)
#置き換えしないなら2重break
else:
heapq.heappush(A, a)
break
else:
continue
break
ans = sum(A)
print(ans)
実際のところ取り出し回数は最大でもN回になるので計算量はO(min(M*sum(B), N)logN)程度です。
Hard No.8 : E - Double Factorial
発想
受験勉強でも似たような考え方をした気がします。末尾につく０の個数と10の倍数の個数は等しく、１０の倍数は２の倍数と５の倍数の１セットから１つ生成されます。５の倍数の方が数が少ないので、５の倍数の数を数えれば良いです。
実装
Nが奇数の場合は０です。５を含む個数でループします。Nが$10^{18}$であってもループ回数は20回程度かと思います。
N = int(input())
if N % 2 == 1:
print(0)
exit()
ans = 0
for i in range(1, N):
num5 = 2*(5**i)
if num5 > N:
break
ans += N//num5
print(ans)
Hard No.9 : B - Template Matching
発想
Aの中のどこかにBと一致するパターンがあればYes、どこにもなければNo。Aの端から端まで全ての場所を全探索すれば良いです。
実装
２重ループをうまく抜け出せるようにすれば良いです。
N, M = map(int, input().split())
A = []
for i in range(N):
a = input()
A.append(a)
B = []
for i in range(M):
b = input()
B.append(b)
for di in range(N-M+1):
for dj in range(N-M+1):
for i in range(M):
for j in range(M):
if A[i+di][j+dj] != B[i][j]:
break
else:
continue
break
else:
print('Yes')
exit()
print('No')
Hard No.10 : D - Enough Array
発想
連続部分列の左端と右端を全探索すると$O(N^2)$となりTLEします。これはしゃくとり法と呼ばれるアルゴリズムで実装します。この方法なら計算量は$O(N)$で済みます。条件を満たす連続部分列の場合の数はしゃくとり法を疑うとうまく求められる場合があります。
実装
しゃくとり法の考え方
まずは左端から次々と要素を足していき、条件を満たした時、その右端の位置を変数curで記録します。この問題の条件は「連続部分列がK以上になること」です。連続部分列の左端はforループの変数iで固定されてますので、iを固定した時の条件を満たす場合の数はN-1-(cur-1)+1になります。よってこれを答えの変数ansに足して、iを１つ右に動かします。そしてまた右端を、条件を満たすまで右に動かしていき、、、と言うことを繰り返すことで$O(N)$で計算できます。
N, K = map(int, input().split())
A = list(map(int, input().split()))
tmp = 0
cur = 0
ans = 0
for i in range(N):
if cur < N:
while tmp < K:
tmp += A[cur]
cur += 1
if cur == N:
break
if tmp < K:
break
ans += N-1 - (cur-1) + 1
tmp -= A[i]
print(ans)