AtCoder ABC106参戦記

非常に悔しいコンテスト結果となりました。C,D問題どちらも解けそうであと一歩及ばす、結果的に2完ということに。C問題は解法は分かったものの、D問題に手を出してしまったため時間が足りず、終了後10分でAC通しました...素直にC問題を先に終わらせればよかった。以下CとD問題のAC取ったコードです。

C問題 (To Infinity)

S = input()
K = int(input())
 
one = True
for i in range(K):
  if S[i] != "1":
    print(int(S[i]))
    one = False
    break
if one:
  print(1)

与えられた各数字iをi^{5*10^15}したときに左からK文字目はなにかという問題ですが、Kは高々10¹⁸なのでわざわざ計算する必要はありません。2の5000兆乗ですらKよりもはるかに大きいので、実際は文字列のK文字目までに1が続いているか、続いていなければ最初に出てくる1以外の数字は何か、という問題でした。

D問題 (AtCoder ExPress 2)

N, M, Q = map(int, input().split())
 
LR =[[0 for j in range(N+2)] for i in range(N+1)]
for i in range(M):
    L, R = map(int, input().split())
    LR[L][R] += 1
    LR[0][R] -= 1
    LR[L][N+1] -= 1
    LR[0][N+1] += 1
 
for i in range(1, N+1): #R方向への累積和
    for j in range(1, N+2):
        LR[i][j] += LR[i][j-1]
for i in range(N-1, -1, -1): #L方向への累積和
    for j in range(1, N+2):
        LR[i][j] += LR[i+1][j]
 
ans = []
for i in range(Q):
    p, q = map(int, input().split())
    ans.append(LR[p][q])
 
for i in range(Q):
    print(ans[i])

二次元累積和(いもす法)を用いることで入力に対してO(1)で解くことができます。そのための前計算にO(N²)です。1を加える範囲の取り方に少しだけ気を付ける必要があって、L軸では1 ~ L, R軸ではR ~ Nになります。