ABC346(Atcoder Beginner Contest)のA~E(A,B,C,D,E)問題をPythonで解説(復習)
A問題
-
A_(i)とA_(i+1)の間の掛け算をN-1回行う。
A.py
"""
<方針>
- `A_(i)`と`A_(i+1)`の間の掛け算を`N-1`回行う。
"""
# 標準入力を受け取り
N = int(input())
A = list(map(int, input().split()))
# 答えを格納するリスト
ans = []
# N-1回ループする。
for i in range(N-1):
# 掛け算の結果を格納する。
ans.append(A[i]*A[i+1])
# リストを空白区切りで出力する。
print(*ans)
B問題
- 鍵盤は
wbwbwwbwbwbwの周期でサイクルしている。これは、wが7個、bが5個の周期である。 -
WとBの両方の値が、上述の鍵盤のサイクルの値よりも大きいときは、WとBを7と5ずつ減らしても問題ない。 - 削った
WとBの値をもとに、鍵盤が最小サイクル内で表現できるか、indexをずらして一つずつ調べる。 - 一つのサイクルをどこのindexから始めても問題が無いように、
Pythonのマイナスindex参照で、すべての1サイクルを実現する。
B.py
"""
<方針>
- 鍵盤は`wbwbwwbwbwbw`の周期でサイクルしている。これは、`w`が`7`個、`b`が`5`個の周期である。
- `W`と`B`の両方の値が、上述の鍵盤のサイクルの値よりも大きいときは、`W`と`B`を`7`と`5`ずつ減らしても問題ない。
- 削った`W`と`B`の値をもとに、鍵盤が最小サイクル内で表現できるか、indexをずらして一つずつ調べる。
- 一つのサイクルをどこのindexから始めても問題が無いように、`Python`のマイナスindex参照で、すべての1サイクルを実現する。
"""
# 標準入力
W, B = map(int, input().split())
# WとBどちらかを7未満or5未満にする。ループ
while True:
# Wが7未満のとき終了
if(W<7):
break
# Bが5未満のとき終了
if(B<5):
break
# WとBをそれぞれ7,5ずつ減らす。
W -= 7
B -= 5
# 鍵盤の1サイクル分
cyc = "wbwbwwbwbwbw"
# 鍵盤のサイクルを開始するindex
for i in range(len(cyc)):
# 鍵盤がいくつになったかをカウントする。
w = 0
b = 0
# 鍵盤を-iずらして開始させて、1サイクル参照する。
for j in range(len(cyc)):
# 鍵盤がwのとき、
if(cyc[j-i]=="w"):
# wをカウントする。
w += 1
# 鍵盤がbのとき
else:
# bをカウントする。
b += 1
# 鍵盤のカウントがwhileループで補正された入力値と合致した場合
if(w==W and b==B):
# Yesを出力する。
print("Yes")
# プログラムを終了し、これより下を実行させない。
exit()
# サイクルで同じ鍵盤数を検知できなかったとき、No
print("No")
C問題
-
Aを昇順にソートする。 - ソートされた
Aを順番にみて、それが1~Kの値であれば、重複の無いように、集合に追加する。 -
1~Kまでの総和から前述の集合の合計値を引いて出力する。
C.py
"""
<方針>
- `A`を昇順にソートする。
- ソートされた`A`を順番にみて、それが`1`~`K`の値であれば、重複の無いように、集合に追加する。
- `1`~`K`までの総和から前述の集合の合計値を引いて出力する。
"""
N, K = map(int, input().split())
A = list(map(int, input().split()))
# Aを昇順にソート
A.sort()
# 重複なく値を保持する集合
exists = set()
# Aを順番に見る。
for i in range(N):
# AがK以上になったら、これ以上先を見ても意味がないので、ループを脱出
if(A[i]>K):
break
# 集合に重複無いようにAの値を追加
exists.add(A[i])
# 1~Kの総和から集合の総和を引いて出力
print((K*(K+1)//2) - (sum(exists)))
D問題
- 良い文字列であることを偶奇に分けて考える。
- Nが偶数の時、
101...0110...101または、010...0110...010のように、両端が同じ値であり、値が連続しているところ以外は左右それぞれから、0-1交互の値になっている。 - Nが奇数の時、
101...0110...010または、010...0110...101のように、両端が違う値であり、値が連続しているところ以外は左右それぞれから、0-1交互の値になっている。 - 左右からそれぞれから、そして
0と1それぞれから、0-1交互になるように、文字を作成したときに、かかるコストを前計算する。 - 値が連続する場所を順番にずらし、最小コストを見つける。
D.py
"""
<方針>
- 良い文字列であることを偶奇に分けて考える。
- Nが偶数の時、`101...0110...101`または、`010...0110...010`のように、両端が同じ値であり、値が連続しているところ以外は左右それぞれから、`0-1`交互の値になっている。
- Nが奇数の時、`101...0110...010`または、`010...0110...101`のように、両端が違う値であり、値が連続しているところ以外は左右それぞれから、`0-1`交互の値になっている。
- 左右からそれぞれから、そして`0`と`1`それぞれから、`0-1`交互になるように、文字を作成したときに、かかるコストを前計算する。
- 値が連続する場所を順番にずらし、最小コストを見つける。
"""
N = int(input())
S = input()
C = list(map(int, input().split()))
# T: Sを0と1からなる数字のリストで表現する。
T = []
for i in range(N):
if(S[i] == "0"):
T.append(0)
else:
T.append(1)
# 左から0または1から始めたときのコスト
l0 = [0]*N
l1 = [0]*N
# 右から0または1から始めたときのコスト
r0 = [0]*N
r1 = [0]*N
# 左から0番目の値を計算
if(T[0]==0):
l0[0] = 0
l1[0] = C[0]
else:
l0[0] = C[0]
l1[0] = 0
# 累積和的に、i番目の値を計算
for i in range(1, N):
# i-1番目の値をとりあえずコピー
l0[i] = l0[i-1]
l1[i] = l1[i-1]
# (0-indexedとし、)偶数番目であることと、i番目が0であることのbooleanが一致したとき、
if((i%2==0) == (T[i]==0)):
# 1初めの方にコストを足す
l1[i] += C[i]
else:
# 0はじめの方にコストを足す
l0[i] += C[i]
### 左からの計算と考え方は一緒なので、説明は省略
if(T[N-1]==0):
r0[N-1] = 0
r1[N-1] = C[N-1]
else:
r0[N-1] = C[N-1]
r1[N-1] = 0
for i in range(N-2, -1, -1):
r0[i] = r0[i+1]
r1[i] = r1[i+1]
# 左から始めたときの条件に加えて、Nの偶奇条件も追加している。
if(((i%2==0) == (T[i]==0)) == (N%2==1) ):
r1[i] += C[i]
else:
r0[i] += C[i]
ans = float("inf")
# 0または1が連続する場所を順番に探す。
for i in range(N-1):
# Nが偶数の時,左右が同じ0または1から始める
if(N%2==0):
ans = min(ans, l0[i]+r0[i+1], l1[i]+r1[i+1])
# Nが奇数の時、左右を異なる0と1から始める。
else:
ans = min(ans, l0[i]+r1[i+1], l1[i]+r0[i+1])
print(ans)
E問題
- 提供された色を逆順に塗り、既に塗られたところを塗らない方法でやっても、題意は変えない。
- とある行を(逆順に)塗るマスの数は、「横の長さ」-「すでに(逆順に)塗られた列の数」となる。(列の場合も同様の考え方ができる。)
- 塗られた数などのアクセスO(1)でやるために、必要なデータは毎回記録する。
E.py
H, W, M = map(int, input().split())
TAX = []
for i in range(M):
t, a, x = list(map(int, input().split()))
# aは0-indexedにする。
TAX.append([t, a-1, x])
# 行と列がそれぞれ最終的に何で塗られたかが書かれたリスト。初期値は0で塗られたとする。
w = [0]*W
h = [0]*H
# 行と列が最終的に何で塗られたかを更新していく。
for tax in TAX:
t, a, x = tax
if(t==1):
h[a] = x
else:
w[a] = x
# 行、列、それぞれが既に塗られたかを記録するリスト。
wDone = [False]*W
hDone = [False]*H
# 行、列、それぞれがいくつ塗られたかを記録する値。
wCnt = 0
hCnt = 0
# a[i] := 色iが何マスに塗られているかが格納されている。
ans = [0]*(2*10**5 + 2)
# マスを塗った回数。
acc = 0
# マスを入力値の後ろから順番に仮想的に塗り、同じところを2回塗らないように進めていく。
for i in range(M):
t, a, x = TAX[M-i-1]
# 行の時、
if(t==1):
# まだ塗られていないとき、
if(not hDone[a]):
# a行目を塗ったことを記録する。
hDone[a] = True
# 塗られて行数が一つ増える
hCnt += 1
# 色xに追加で塗るマス数は{(横幅)-(既に塗られた"列"数)}
ans[x] += (W - wCnt)
# 塗ったマスの回数を記録する。
acc += (W - wCnt)
# 列の時、(行の時とコードは一緒なので、解説は省略する。)
else:
if(not wDone[a]):
wDone[a] = True
wCnt += 1
ans[x] += (H - hCnt)
acc += (H - hCnt)
# 行と列、それぞれすべて塗られたら終了する。
if(hCnt == H and wCnt == W):
break
# そもそも入力値が少ない関係などで、まだ塗られていないところがあれば、それは色0で塗られたとして、ans[0]をその分増やす。
ans[0] += (H*W)-acc
# 何色で塗られたかを記録する。
kinds = 0
# それぞれの色を見る。
for i in range(len(ans)):
# その色が使われていれば、
if(ans[i]!=0):
# インクリメント
kinds += 1
# 何色で塗られたかを出力
print(kinds)
# それぞれの色を見る。
for i in range(len(ans)):
# その色が使われていれば、
if(ans[i]!=0):
# その色と使われた回数を出力
print(i, ans[i])
補足
関係するリンク(参考文献など)
筆者について
その他
- 間違いを含んでいる可能性があります．
- 方針と言いつつ，方針ではない感想などを書いている可能性があります．
- A問題から解説がだんだん省略されます．
最後に一言
- Fの解説読んで、理解はできたけど、実装で無限にエラー発生したから投稿してません。。（ごめん。。）
- とりあえず、こういう定期的な記事は続けることが大事だと誰かから言われた気がしたので、解説がいつも以上に雑(自分が本番に提出したコードをほぼそのまま使ってます。。)な気がしますが、とりあえず書くことにしました。ご了承下さい。