ABC298のA,B,C,D,問題をpythonで解説していきます。
A – Job Interview
入力
N:文字列の長さ
S:文字列
考察
今回条件はxがあった瞬間に一発アウトで、また合格するには文字列を最後まで見たときにoが一個以上ある必要があります。
そのため、事前にoの数をカウントするflgを用意し、文字列を0文字目から見ていったときに、
xがあった瞬間Noを出力しプログラムを終了oがあれが+1
for文が終わったときに、oの数が1以上ならYes,oの数が0ならNoを出力します
コード
N = int(input())
letter = input()
okcnt = 0
for i in range(N):
if letter[i] == "o":
okcnt += 1
elif letter[i] == "x":
print("No")
exit()
if okcnt > 0:
print("Yes")
else:
print("No")B – Coloring Matrix
入力N:文字列
A[i][j]: Aのi行目j列目
B[i][j]: Bのi行目j列目
考察
今回、Aを回転させたときに、A[i][j]==1のとき、B[i][j]==1が成り立つかどうかを判定するプログラムを書きたいです。
ここで、回転させる回数は、(初期位置で判定していない場合)最大でも4回になります。なぜなら4回回転させるとともとの形に戻るためです。
そこで、4回右回転or左回転をさせるには、
- 右回転:上下入れ替え→転置
- 左回転:転置→上下入れ替え
を行うことで回転させることができます。
2次元配列の上下入れ替えるためには、list名[::-1]で上下入れ替えができ、2次元配列の転置は、zip()を使うことで転置できます。
コード
N = int(input())
A_box = []
B_box = []
for i in range(N):
A = list(map(int, input().split()))
A_box.append(A)
for i in range(N):
B = list(map(int, input().split()))
B_box.append(B)
for q in range(4): #今回は、右回転を4回行っています
for i in range(N):
for j in range(N):
if B_box[i][j] == 0 and A_box[i][j] == 1:
#もしA[i][j]が1なのにB[i][j]が1じゃないならだめ
break
else:
continue
break
else:#breakされなかった。つまりすべての点においてしA[i][j]=B[i][j]=1なら
print("Yes")
exit()
#回転させる
A_box = A_box[::-1]#上下転置
new_A_box = []#右回転した新しい配列を格納するlist
for x in zip(*A_box):
new_A_box.append(x)#転置
A_box = new_A_box#右回転したリストをA_boxに代入 これでA_boxが右回転した
#4回のfor文処理が終わったのに、Yesが出力されてなければ
print("No")C – Cards Query Problem
入力
N:空の箱の長さ
Q:クエリの個数
query:3つの処理内容
考察
query2では箱iに入っているカードについて出力し、query3では数iが書かれている箱について出力する必要があります。
そのため、どの箱にどのカードが入っているかを記憶するlistの他に、どの数がどの箱に入っているかを記憶するlistを用意する必要があります。
今回箱の個数も数の最大値も2×10^5以下なので、特別工夫することなくlistを作ることができます
コード
import bisect
#bisectは既に整列されている配列に対して高速で挿入できるライブラリ
#今回は昇順で(整列して)出力する必要があるため使用している
N = int(input())
#query2用のリスト
box = [[] for i in range(N+1)]#1-indexにしたいので、+1
#query3用のリスト
num_box = [[] for i in range(2*(10**5)+1)]#1-indexにしたいので、+1
Q = int(input())
for i in range(Q):
a = list(map(int, input().split()))
ind = a[0]
if ind == 1:#query1なら
i,j = a[1],a[2]
bisect.insort(box[j],i)#j番目のboxにカードiを挿入
bisect.insort(num_box[i],j)#j番目のカードが入っているbox[j]を記憶
elif ind == 2:
i = a[1]
print(*box[i],sep=" ")
elif ind == 3:
i = a[1]
ans = set(num_box[i])#重複なしで出力する必要があるためsetを使用
print(*ans,sep=" ")D – Writing a Numeral 時間内に解けなかった・・・
入力
Q:クエリの数
query:3つの処理内容
考察
今回の問題、一見すぐ溶けそうですが、Qの制約が6×10^5であるため、クエリ1回にかかる時間を最低でもO(log(N))で行う必要があります。
- クエリ1は元の数字を10倍し、新しく入力された値を足せばO(1)で計算でき、
- クエリ3はMODで割るだけなので、O(1)でできます。
しかしクエリ2の処理で、文字列として考え先頭の文字を消したり、[:1]などで転記してしまうとTLEになってしまいます。
letter = letter[:1]の処理は1以降のものを1つずつコピーして渡すので、計算量はO(len(num-1))
TLEにしてしまったコード
MOD = 998244353
Q = int(input())
num = 1
for i in range(Q):
a = list(map(int, input().split()))
if a[0] == 1:
num = str(num)
num += str(a[1])
num = int(num)
elif a[0] == 2:
num= str(num)
num = num[1:]#1:以降のものを1つずつコピーして渡すので、計算量はO(len(num-1))
num = int(num)
elif a[0] == 3:
print(num%MOD)そのため、どうにかしてクエリ2の処理を抑える必要があります。ここで先頭の数字を消すという動作を言い換えて考えてみます。
先頭の数字を消す→現在の数列-現在の桁数×先頭の数字
ex)3141592
3141592 - 30000000=141592
となり、先頭の数字を消すことに成功今回、クエリ1,2の特徴は以下の通りなので
- 取り出しは先頭の数字
- 追加は末尾
dequeを用いることができます。これで先頭の数字を取り出すのをO(1)で行うことができます。
先頭の数字を取り出すことができたら、取り出す前の桁数にするように10を何回か書けたいのですが、その際に繰り返し二乗法(pow)を使用します。
繰り返し二乗法の詳しい説明は省きますが簡単に言うと、べき乗の計算をlog(N)で行うことができる計算方法です
これにより、10を(元の数列の桁数)回かけることができます
その後、元の数列-現在の桁数×先頭の数字を行うことで、実質的に先頭の数字を消すことができます
コード
from collections import deque
S = deque([1])
Q = int(input().strip())
MOD = 998244353
ans = 1
for _ in range(Q):
q = list(map(int, input().strip().split()))
if q[0] == 1:
S.append(q[1])
ans = (ans * 10 + q[1])#
ans %=MOD
elif q[0] == 2:
x = S.popleft()
ans -= pow(10, len(S), MOD) * x#繰り返し二乗法によってlogNで計算できる
elif q[0] == 3:
print(ans%MOD)
コメント