[ABC387] ABC 387(Atcoder Beginner Contest)のA~D(A,B,C,D)問題をPythonで解説(復習)
A問題
- 我々がすることは特にない．
- 計算機に頑張ってもらう．
A.py
"""
<方針>
- 我々がすることは特にない．
- 計算機に頑張ってもらう．
"""
# 入力
A, B = map(int, input().split())
# 計算
ans = (A+B)**2
# 出力
print(ans)
B問題
- 九九の値
numを順番に見ていく． - それが
Xと合致しなければ，答えに足す．
B.py
"""
<方針>
- 九九の値 `num` を順番に見ていく．
- それが `X` と合致しなければ，答えに足す．
"""
# 入力
X = int(input())
# 総和
ans = 0
# 九九をみる
for i in range(1, 10):
for j in range(1, 10):
# 九九の値を取得
num = i*j
# Xに一致しなければ
if(num!=X):
# 総和に足す
ans += num
# 出力
print(ans)
C問題
方針
- 明らかに
O(N)は間に合わない． - 桁ごとでうまくみていけば，あとは実装力の問題だ．
-
L~Rという条件が知りたければ，X以下さえ分かる関数snakeを求めれば，snake(R) - snake(L-1)を求めれば良い． - <パターンA>
Xの桁数よりも小さい桁を全部列挙すれば良い． - <パターンB>
Xの桁数において，Xの先頭の数をXの実際の先頭の数いかを試せば良い． - <パターンC>
Xの桁数において，Xの先頭も固定した状態で考える．その時，「Xの先頭の数」進数で考えると良さそう．
-
前提
-
C問題あたりで，TLEになる人は，制約条件を見る癖をつけよう． -
AとB問題では，基本的に制約条件を見ずにやっても解ける． - しかし，
C問題以降では，制約条件を見ないと必ずTLEすると思っても良い． - 詳しい話は私の352回の記事 の
C問題の解説に記したので，是非参照してほしい．
C.py
"""
<方針>
- 明らかに `O(N)` は間に合わない．
- 桁ごとでうまくみていけば，あとは実装力の問題だ．
- `L~R` という条件が知りたければ，`X` 以下さえ分かる関数 `snake` を求めれば， `snake(R) - snake(L-1)` を求めれば良い．
- <パターンA> `X` の桁数よりも小さい桁を全部列挙すれば良い．
- <パターンB> `X` の桁数において，`X` の先頭の数を `X` の実際の先頭の数いかを試せば良い．
- <パターンC> `X` の桁数において，`X` の先頭も固定した状態で考える．その時，「`X` の先頭の数」進数で考えると良さそう．
"""
# 入力
L, R = map(int, input().split())
def snake(X):
# L==10の時，L-1==0になるため，その対処
if X<=9:return 0
# 基本情報
block = str(X)
head = int(block[0])
length = len(block)
# 出力
ans = 0
## パターンA
for i in range(2, length):
for j in range(1, 10):
ans += j**(i-1)
## パターンB
for i in [length]:
for j in range(1, head):
ans += j**(i-1)
## パターンC
tmp = "" # head進数を作る
fla = True # head<=iを見てないフラグ
for ind, s in enumerate(block[1:]):
i = int(s)
if(head>i and fla):
tmp += s
else:
tmp += str(head-1)
fla = False
# head進数の計算
for i, s in enumerate(reversed(tmp)):
ans += int(s)*(head**i)
# 「10」のパターンを足す
ans += 1
# 出力
return ans
ans = snake(R)-snake(L-1)
print(ans)
D問題
- マスの縦横インデックスの和を2で割った余り(
(y+x)%2)によって縦or横に移動できるかを制限をかけておく．- これを2通り試せば良い．
-
Pythonの再帰は遅いので，非再帰BFSで実装する．-
popleftをすると，BFSになり，popをすると，DFSになる．
-
D.py
"""
<方針>
- マスの縦横インデックスの和を2で割った余り(`(y+x)%2`)によって縦or横に移動できるかを制限をかけておく．
- これを2通り試せば良い．
- `Python` の再帰は遅いので，非再帰BFSで実装する．
- `popleft` をすると，`BFS` になり，`pop` をすると，`DFS` になる．
"""
from collections import deque
# 入力
H, W = map(int, input().split())
INF = float("inf")
SS = []
start = None
goal = None
for i in range(H):
_S = input()
S = []
for j, s in enumerate(_S):
match s:
case ".":
S.append(INF)
case "#":
S.append(-1)
case "S":
S.append(INF)
start = (i, j)
case "G":
S.append(INF)
goal = (i, j)
SS.append(S)
# BFS
def bfs(way):
# 盤面を新しく作成
TT = []
for S in SS:
TT.append(S[:])
# deque
q = deque()
# 初期値
TT[start[0]][start[1]] = 0
q.append(start)
# ループ
while q:
# 取り出す
y, x = q.popleft() # BFS
# 上下左右への移動
for dy, dx in [
(-1, 0),
(0, -1),
(1, 0),
(0, 1),
]:
# 新しいindex
Y = y + dy
X = x + dx
# 枠内にあるか
if(0<=Y<H and 0<=X<W):
# 上下移動or左右移動を許可
if(((y+x)%2==way)==(dy==0)):
# 新しいコスト
cost = TT[y][x] + 1
# 新しいコストの方が条件が良ければ，更新してdequeに入れる
if(cost < TT[Y][X]):
TT[Y][X] = cost
q.append([Y, X])
# GOALの値を出力
return TT[goal[0]][goal[1]]
# 上下or左右パターンの両者のうち，最適な方を選択
ans = min(bfs(0), bfs(1))
# 到達できなければ，-1にする．
if(ans == INF):
ans = -1
# 出力
print(ans)
補足
関係するリンク(参考文献など)
筆者について
- Atcoderアカウント
- 今回も不参加のため，成績なし．
- 解説で示したA問題の提出
- 解説で示したB問題の提出
- 解説で示したC問題の提出
- 解説で示したD問題の提出
その他
- 間違いを含んでいる可能性があります．
- 方針と言いつつ，方針ではない感想などを書いている可能性があります．
- A問題から解説がだんだん省略されます．
- コードに書かれている解説の文言と，その上に書いてある解説の文言を変えている場合があります．
最後に一言
- C問題の<パターンC>の発想は友人の力を借りました．