2022年7月2日開催のAtcoder Beginner Contest 258を、備忘的にギリ茶の私の回答と反省を残しつつ、解説を入れていきます。
今回は、B問題で問題の解釈を間違えてドツボにハマるという事態を招きました。問題文は焦らずしっかり読もうという教訓になった回です。。
コンテンツ一覧
A - When?
問題
AtCoder Beginner Contest は通常、日本標準時で 21 時ちょうどに始まり \(\ 100 \) 分間にわたって行われます。
\(\ 0 \) 以上 \(\ 100 \) 以下の整数 \(\ K \) が与えられます。21 時ちょうどから \(\ K \) 分後の時刻を HH:MM の形式で出力してください。ただし、HH は \(\ 24 \) 時間制での時間を、MM は分を表します。時間または分が 1 桁のときは、先頭に \(\ 0 \) を追加して 2 桁の整数として表してください。
制約と入力形式
- \(\ 0 \leq K \leq 100 \)
- \(\ K \) は整数
回答アプローチ
入力された時間（分）を60で割った商に21を足してHH に、剰余をMM とします。ただし、剰余をそのままMM とすると「時間または分が 1 桁のときは、先頭に \(\ 0 \) を追加して 2 桁の整数として表してください。」に適さないので、一桁の場合は０埋めする必要があります。
Pythonの文字列（str）には zfillというメソッドがあります。 桁数を指定すると、文字列がその桁数に満たない場合に満たない分を０で埋めてくれます。
K = int(input())
H = int(K/60) + 21
M = str(K%60).zfill(2)
print(f"{H}:{M}")B - Number Box
問題
正整数\(\ N \)が与えられます。
\(\ N \) 行 \(\ N \) 列のマス目があり、上から \(\ i \) 行目、左から \(\ j \) 列目のマスには数字 \(\ A_{i,j} \) が書かれています。
このマス目は上下および左右がつながっているものとします。つまり以下が全て成り立ちます。
- \(\ (1,i) \) の上のマスは \(\ (N,i) \)であり、 \(\ (N,i) \)の下のマスは \(\ (1,i) \) である。 \(\ (1 \leq i \leq N ) \)
- \(\ (i,1) \) の左のマスは \(\ (i,N) \)であり、 \(\ (i,1) \) の右のマスは \(\ (i,N) \)である。 \(\ (1 \leq i \leq N ) \)
高橋君は、上下左右および斜めの 方向のうちいずれかを初めに選びます。そして、好きなマスから決めた方向に 1 マス移動することを\(\ N - 1 \) 回繰り返します。
高橋君は \(\ N \) 個のマス上を移動することになりますが、高橋君が通ったマスに書かれている数字を左から通った順番に並べた整数としてあり得る最大のものを求めてください。
太字の部分の解釈を間違えていました。移動するたびに好きな方向を選ぶものだと勘違いしていました。
制約と入力形式
- \(\ 1 \leq N \leq 10 \)
- \(\ 1 \leq A_{i,j} \leq 9 \)
- 入力はすべて整数
回答アプローチ
上述の通り、移動する度に毎回好きな方向を選ぶ問題だと勘違いしていたため、ドツボにハマるという事態になりました。Twitterを見ても、私と同じように問題を解釈している人が散見されました。それもあってか、Atcoder Probremsを見てもB問題としては難しい問題となっています。（C問題の方がやや簡単という判定）
最初はリスト内の最大値となるインデックスを炙り出してから、そこから８方向に進み、maxとなる値を出力するという方法を取りましたが、マス上全ての値で全探索してもさほど変わらないので全探索をします。
N = int(input())
A = []
for _ in range(N):
A.append(list(map(int,list(input()))))
index = [[i,j] for i in range(N) for j in range(N)]#マス目の全インデックスをリストとして保持します。二重ループで書くのと一緒です。
XY = [[x,y] for x in [0,1,-1] for y in [0,1,-1] if not x==y==0] #進む方向を予めリストで保持します。x==y==0の時はその場に止まることになるので排除します。
L = []
for i in index:
for x,y in XY:
x_t,y_t = i[0],i[1]
R = str(A[x_t][y_t])
for _ in range(N-1):
x_t = (x_t+x)%N
y_t = (y_t+y)%N
R += str(A[x_t][y_t])
L.append(int(R))
print(max(L))C - Rotation
問題
正整数\(\ N,Q \)と、長さ\(\ N \) の英小文字からなる文字列 \(\ S \) が与えられます。
以下で説明されるクエリを\(\ Q \)個処理してください。クエリは次の\(\ 2 \) 種類のいずれかです。
1 x: 「 \(\ S \) の末尾の文字を削除し、先頭に挿入する」という操作を \(\ x \) 回連続で行う。2 x: \(\ S \) の \(\ x \) 番目の文字を出力する。
制約と入力形式
- \(\ 2 \leq N \leq 5 \times 10^5 \)
- \(\ 1 \leq Q \leq 5 \times 10^5 \)
- \(\ 1 \leq x \leq N \)
- \(\ |S| \ = N \)
- \(\ S \)は英小文字からなる。
2 xの形式のクエリが \(\ 1 \) 個以上与えられる。- \(\ N,Q,x \)はすべて整数。
回答アプローチ
クエリ１の操作は一見文字列を崩しているように見えますが、1文字ずつ後ろの文字を先頭に挿入するので、文字の順序が本質的に崩れているわけではありません。わかりやすくグラフィックに解釈するならば、この文字列の先頭と末尾をネックレスのようにくっつけて、ループするように考えれば、ただ単に先頭をどの文字にしているかを入れ替えているだけということがわかります。タイトルの「Rotation」がある意味ヒントとなっているのかもしれません。
なので、逐次文字列を操作する問題ではなく、先頭のインデックスがどこにズレるかを処理していけば良いです。
ズラす度に\(\ N \) で剰余をとり、リスト外のインデックスにならないようにします。
N,Q = map(int,input().split())
S = list(input())
index = 0
for _ in range(Q):
q,x = map(int,input().split())
if q == 1:
index = (index-x)%N
else:
print(S[(index+x-1)%N])D - Trophy
問題
\(\ N \) 個のステージからなるゲームがあり、\(\ i (1\leq i \leq N) \) 番目のステージは\(\ A_i \) 分間のストーリー映像と\(\ B_i \) 分間のゲームプレイによって構成されます。
初めて\(\ i \) 番目のステージをクリアするためにはストーリー映像の視聴とゲームプレイを両方行う必要がありますが、二回目以降はストーリー映像をスキップすることができるので、ゲームプレイのみでクリアすることができます。
初めから遊べるのは\(\ 1 \) 番目のステージのみですが、\(\ i (1\leq i \leq N-1 ) \) 番目のステージをクリアすることにより, \(\ i +1 \) 番目のステージも遊べるようになります。
合計\(\ X \) 回ステージをクリアするために必要な時間の最小値を求めてください。ただし、同じステージを複数回クリアしたとしても、全てクリア回数に数えられます。
制約と入力形式
- \(\ 1 \leq N \leq 2\times 10 ^ 5 \)
- \(\ 1 \leq A_i,B_i \leq 10^9 (1 \leq i \leq N ) \)
- \(\ 1 \leq X \leq 10^9 \)
- 入力は全て整数
回答アプローチ
B問題で時間を食い過ぎて、この問題を解く余裕なく。。DPかその類のように一見見えますが、最小時間でステージをクリアする場合、結局あるステージを連続してクリアするだけであることがわかる。つまり、わざわざあるステージをクリアした後に、前のステージに戻ったりする必要はない。不可逆的に進めればよく、クリアし続けるステージをどこにするかで全探索すれば良いという問題。
n,x = map(int,input().split())
total = 0
L = []
for _ in range(n):
ab = list(map(int, input().split()))
if x > 1:
x -= 1
total += sum(ab)
L.append(x * ab[-1]+total)
else:
break
print(min(L))