- PythonでAtcoderに参加する一般人の備忘録です。
- 解けた問題のソースコードと解き方のメモとなりますので最適解ではないことが多々あります。
- ご指摘ありましたらコメントしていただければ気づいたときに返信します。
目次
A-Filter
B-ASCII Art
C-Merge Sequences
D-Bank
E-2xN Grid
A-Filter
問題ページ：A-Filter
手法
入力が1行リストなので、要素を一つずつ確認し偶数のものを解答用リストに挿入ないし、出力します。
偶数の判定に関しては、$A$%$B$で$A$を$B$で割った余りを計算できます。
コード
def main():
N = input()
A = list(map(int,input().split())
ans = []
for i in A:
if i % 2 == 0:
ans.append(i)
print(*ans)
if __name__ == '__main__':
main()
B-ASCII Art
問題ページ：B-ASCII Art
手法
問題を解く上で必要となってくるポイントは数字をアルファベットに変換する点です。
これは、$chr(x)$関数で数値$x$をコードとする$Unicode$文字を求められるので利用しました。
アルファベット大文字は$65$~$90$、小文字は$97$~$123$ですが自分は忘れるので必要になる度に調べてます。
def main():
H,W = map(int,input().split()
A = [list(map(int, input().split())) for l in range(H)]
for i in range(H):
temp = ''
for j in range(W):
if A[i][j] == 0:
temp += '.'
else:
temp += chr(A[i][j]+64)
print(temp)
if __name__ == '__main__':
main()
C-Merge Sequences
問題ページ：C-Merge Sequences
手法
$C$の$i$番目には$A$の要素と$B$の要素のどちらが入るのかを求める問題でした。
制約条件として二つのリストは一つとして同一の要素を持たず、入力時点で二つのリストはソート済みです。
$A[i]$と$B[j]$の要素を比較し、$A[i]$の方が小さければ$A[i]$を$n$に書き換えて$i$に$1$を加えて右に$1$つずらす作業を繰り返します。
※解答2は解答1が読みずらいため、後から$Deque$を使用して書き直したものになります。
コード
解答1
def main():
N,M = map(int,input().split())
A = list(map(int,input().split()))
B = list(map(int,input().split()))
indexA = 0
indexB = 0
for i in range(N+M):
if indexA < N and indexB < M:
if A[indexA] < B[indexB]:
A[indexA] = i+1
indexA += 1
else:
B[indexB] = i+1
indexB += 1
if indexA == N:
for j in range(N+M-i-1):
B[indexB+j] = i+j+2
break
if indexB == M:
for j in range(N+M-i-1):
A[indexA+j] = i+j+2
break
print(*A)
print(*B)
if __name__ == '_main__':
main()
解答2(Deque使用)
from collections import deque
def main():
N,M = map(int,input().split())
A = deque()
B = deque()
AL = list(map(int,input().split()))
BL = list(map(int,input().split()))
indexlist_A = deque()
indexlist_B = deque()
for a in AL:
A.append(a)
for b in BL:
B.append(b)
for i in range(N+M):
if len(A) > 0 and len(B) > 0:
Ai = A.popleft()
Bi = B.popleft()
if Ai < Bi:
indexlist_A.append(i+1)
B.appendleft(Bi)
if Ai > Bi:
indexlist_B.append(i+1)
A.appendleft(Ai)
elif len(A) == 0 and len(B) > 0:
B.popleft()
indexlist_B.append(i+1)
else:
A.popleft()
indexlist_A.append(i+1)
print(*indexlist_A)
print(*indexlist_B)
if __name__ == '__main__':
main()
D-Bank
問題ページ：D-Bank
手法
$Query[i]$によって異なる処理が行われます。
- 1の場合：一度も呼び出していない最も小さい番号を呼び出し$Que$に挿入する。
- 2の場合：$i$を呼び出し番号$Que$から取り除く。
- 3の場合：解答用$Que$に呼び出し番号$Que$で左にあるものを一つ挿入する。
コードでは、$Query[i]$が$2$の場合には受付済み番号$Set$に挿入する操作のみ行い、$Query[i]$が$3$の場合に受付済み番号$Set$に含まれる番号を呼び出し番号$Que$から削除する操作を行った上で、最も小さい番号を解答用$Que$に挿入する操作行っています。
※$Deque$と$Set$を使用しています。
コード
from collections import deque()
def main():
N,Q = map(int,input().split())
ans = deque()
call = deque()
go = set()
indicate = 1
for _ in range(Q):
print(*call)
print(*go)
query = inp.l()
if query[0] == 1:
call.append(indicate)
indicate += 1
if query[0] == 2:
go.add(query[1])
if query[0] == 3:
while len(call) > 0:
x = call.popleft()
if x in go:
go.remove(x)
else:
ans.append(x)
call.appendleft(x)
break
print(*ans)
if __name__ == '__main__':
main()
E-2xN Grid
問題ページ：E-2xN Grid
手法
$L$の範囲が広いため$i$番目が条件を満たしているか1つずつ確認していくのは諦めました。
この問題で必要なのは連長圧縮を適切に処理していくことでした。
問題では$L$列を連長圧縮することで$N_1+N_2$列まで圧縮し、制約より最大でも$2×10^5$の範囲に収まっています。
1行目と2行目の整数列の連長圧縮をそれぞれ$Deque$で管理し、1行目と2行目でどちらか、あるいは両方の整数が変わるポイント間を確認しながらカウントを行っていきます。
$l_1$と$l_2$で長い方を$Deque$に戻す。このとき$l_i$の値は$|l_1-l_2|$の値に変更しています。
また、$v_1$と$v_2$の値が等しい場合、問題の条件を満たしているので、条件を満たしている区間"$min(l_1,l_2)$"をカウントに加算していく。
この操作を$v_1$と$v_2$がなくなるまで繰り返すことで問題の解答を得られました。
コード
from collections import deque
def main():
L,N1,N2 = map(int,input().split())
v1 = deque()
v2 = deque()
l1 = deque()
l2 = deque()
for _ in range(N1):
x,y = map(int,input().split())
v1.append(x)
l1.append(y)
for _ in range(N2):
x,y = map(int,input().split())
v2.append(x)
l2.append(y)
count = 0
while len(v1) > 0 and len(v2) > 0:
v1t = v1.popleft()
v2t = v2.popleft()
l1t = l1.popleft()
l2t = l2.popleft()
if l1t < l2t:
l2.appendleft(l2t-l1t)
v2.appendleft(v2t)
if v1t == v2t:
count += l1t
elif l1t > l2t:
l1.appendleft(l1t-l2t)
v1.appendleft(v1t)
if v1t == v2t:
count += l2t
else:
if v1t == v2t:
count += l1t
print(count)
if __name__ == '__main__':
main()