[ABC425] ABC 425(Atcoder Beginner Contest)のA~D(A,B,C,D)問題をPythonで解説(復習)
A問題
- 数式（
((-1)**i) * (i**3)）を立式すればいけそう。 - あとは
for文を回すだけ。
A.py
"""
<方針>
- 数式（`((-1)**i) * (i**3)`）を立式すればいけそう。
- あとは `for` 文を回すだけ。
"""
# 入力
N = int(input())
# 総計
ans = 0
# 1~Nでループ
for i in range(1, N+1):
# 総計に加える
ans += ((-1)**i) * (i**3)
# 出力
print(ans)
B問題
-
-1がワイルドカードを表しており、それ以外が重複してないことを確認すれば存在するかはわかりそう。 -
Pを構築するには、存在していなかったものを順番に当てていけば良さそう。
B.py
"""
<方針>
- `-1` がワイルドカードを表しており、それ以外が重複してないことを確認すれば存在するかはわかりそう。
- `P` を構築するには、存在していなかったものを順番に当てていけば良さそう。
"""
# 入力
N = int(input())
A = list(map(int, input().split()))
# 重複の有無を確認する。（0-indexed管理）
exists = [False]*(N)
for i in range(N):
a = A[i]
# -1は無視
if(a == -1):
continue
# 重複がある時は終了
if(exists[a - 1]):
print("No")
exit()
# 存在を記憶する
exists[a - 1] = True
# 存在しなかったものだけを
wild_candidates = []
for i in range(N):
if not (exists[i]):
wild_candidates.append(i+1)
# Pの構築
P = []
# ワイルドカードを順番に消費していくもの
current_wild = 0
for i in range(N):
# ワイルドカードの消費
if(A[i] == -1):
P.append(wild_candidates[current_wild])
# 次のワイルドカードをみる
current_wild += 1
else:
# 既存のAを使う
P.append(A[i])
# 出力
print("Yes")
print(*P)
C問題
方針
-
Aの先頭を本当にぐるぐる移動 させてたら時間が足りないO(NQ) -
Aを環状で考えてあげて（マージンをとって２倍にしておく）、先頭の移動は、headで管理させてあげれば良さそう。 - とはいえ、
[l, r)を毎回計算していたら、これもまたO(NQ)になってしまう（一敗）。 - そこは累積和
Bを用いて、あらかじめ計算しておき（O(N)）、[0, r) - [0, l-1)としてクエリ毎に計算（O(Q)）すれば良い。 - 全体として、
O(N+Q)となった。
前提
-
C問題あたりで，TLEになる人は，制約条件を見る癖をつけよう． -
AとB問題では，基本的に制約条件を見ずにやっても解ける． - しかし，
C問題以降では，制約条件を見ないと必ずTLEすると思っても良い． - 詳しい話は私の352回の記事 の
C問題の解説に記したので，是非参照してほしい．
C.py
"""
<方針>
- `A` の先頭を本当にぐるぐる移動 させてたら時間が足りない `O(NQ)`
- `A` を環状で考えてあげて（マージンをとって２倍にしておく）、先頭の移動は、`head` で管理させてあげれば良さそう。
- とはいえ、`[l, r)` を毎回計算していたら、これもまた `O(NQ)` になってしまう（一敗）。
- そこは累積和 `B` を用いて、あらかじめ計算しておき（`O(N)`）、`[0, r) - [0, l-1)` としてクエリ毎に計算（`O(Q)`）すれば良い。
- 全体として、`O(N+Q)` となった。
"""
N, Q = map(int, input().split())
A = list(map(int, input().split()))
# マージンをとって２倍
A = A[:] + A[:]
# 累積和を計算する。
B = [0]
for i in range(2*N):
B.append(B[-1]+A[i])
# 先頭を管理する変数
head = 0
# クエリ毎の処理
for _ in range(Q):
query = list(map(int, input().split()))
match query:
# 1, c のとき、
case [1, c]:
# 先頭を動かす
head += c
# 2*Nのサイズに収まるようにしておく
head %= N
# 2, l, r のとき、
case [2, l, r]:
# [0, r) - [0, l-1) を計算する。
print(B[head+r] - B[head+l-1])
D問題
- 探索をしていけば良さそう。
- 探索をする際は、まとめて更新せずに、
DFS,BFSを行うと、正しく解けないので注意（n敗）。
D.py
"""
<方針>
- 探索をしていけば良さそう。
- 探索をする際は、まとめて更新せずに、`DFS`, `BFS` を行うと、正しく解けないので注意（n敗）。
"""
# 入力
H, W = map(int, input().split())
SS = [list(input()) for _ in range(H)]
# 十字キー https://en.wikipedia.org/wiki/D-pad
D_PAD = [
[+1, +0],
[-1, +0],
[+0, +1],
[+0, -1],
]
# 探索する対象
target = []
for i in range(H):
for j in range(W):
if(SS[i][j] == "#"):
target.append([i, j])
# 探索をする
while True:
# 探索対象がなければ終了する。
if not (target):
break
# 探索対象をまとめて塗る
for y, x in target:
SS[y][x] = "#"
# 次の対象を管理
new_target = []
# 次の対処を探す
for y, x in target:
# 上下左右
for dy, dx in D_PAD:
Y = y + dy
X = x + dx
# 枠内
if(0<=Y<H and 0<=X<W):
# まだ塗られていない
if (SS[Y][X] == "."):
# 上下左右の黒の数を探す
cnt = 0
for dr, dc in D_PAD:
R = Y + dr
C = X + dc
if(0<=R<H and 0<=C<W):
if(SS[R][C] == "#"):
cnt += 1
# 黒が一つしかない時、
if(cnt == 1):
# 次の探索に加える（黒で塗る）
new_target.append([Y, X])
# 新しい対象に変える
target = new_target
# 出力
ans = 0
for i in range(H):
for j in range(W):
if(SS[i][j] == "#"):
ans += 1
print(ans)
補足
関係するリンク(参考文献など)
筆者について
- Atcoderアカウント
- 今回も不参加のため，成績なし．
- 解説で示したA問題の提出
- 解説で示したB問題の提出
- 解説で示したC問題の提出
- 解説で示したD問題の提出
その他
- 間違いを含んでいる可能性があります．
- 方針と言いつつ，方針ではない感想などを書いている可能性があります．
- A問題から解説がだんだん省略されます．
- コードに書かれている解説の文言と，その上に書いてある解説の文言を変えている場合があります．
最後に一言
- チェンソーマンにハマってます。