[ABC400] ABC 400(Atcoder Beginner Contest)のA~D(A,B,C,D)問題をPythonで解説(復習)
A問題
- とりあえず除算で
Bを求めてみる。 - 積算で長方形かどうかを確かめる。
A.py
"""
<方針>
- とりあえず除算で `B` を求めてみる。
- 積算で長方形かどうかを確かめる。
"""
# 入力
A = int(input())
# B
B = 400 // A
# 確認して出力
if(A*B == 400):
print(B)
else:
print(-1)
- 順番に足していき、
10**9を超えるかを逐一チェックする。
B問題
B.py
"""
<方針>
- 順番に足していき、`10**9` を超えるかを逐一チェックする。
"""
# 入力
N, M = map(int, input().split())
X = 0
# 足していく
for i in range(M+1):
X += N**i
# inf確認
if(X > 10**9):
print("inf")
exit()
# 出力
print(X)
C問題
方針
-
Nがデカすぎるので、線形探索は許されない。 - (aが奇数の)
N//2or （aが偶数の）N//4以下の平方数の数が答え。 - 平方数の数は、
X以下の最大の平方数を考えればよく、今回は二分探索でやってみる。
前提
-
C問題あたりで，TLEになる人は，制約条件を見る癖をつけよう． -
AとB問題では，基本的に制約条件を見ずにやっても解ける． - しかし，
C問題以降では，制約条件を見ないと必ずTLEすると思っても良い． - 詳しい話は私の352回の記事 の
C問題の解説に記したので，是非参照してほしい．
C.py
"""
<方針>
- `N` がデカすぎるので、線形探索は許されない。
- (aが奇数の) `N//2` or （aが偶数の）`N//4` 以下の平方数の数が答え。
- 平方数の数は、`X` 以下の最大の平方数を考えればよく、今回は二分探索でやってみる。
"""
# 入力
N = int(input())
# 答え
ans = 0
#
for X in [N//2, N//4]:
# 二分探索で最大の平方数を探す。
ok = 0
ng = X+1
while abs(ok-ng) > 1:
mid = (ok+ng)//2
if(mid**2 <=X):
ok = mid
else:
ng = mid
# 答えを更新
ans += (ok)
# 出力
print(ans)
D問題
- 公式解説と一緒です。
D.py
"""
<方針>
- 公式解説と一緒です。
"""
from collections import deque
INF = float("inf")
# 入力
H, W = map(int, input().split())
SS = [list(input()) for _ in range(H)]
A, B, C, D = map(lambda x: int(x) - 1, input().split())
V = [[INF for _ in range(W)] for _ in range(H)]
q = deque()
q.append([0, A, B])
# 0-1BFS
while q:
c, i, j = q.popleft()
if(V[i][j] != INF):
continue
V[i][j] = c
# いくつ先を見るか
for d in [1, 2]:
# 上下左右
for dy, dx in [
[-1, 0],
[0, -1],
[+1, 0],
[0, +1],
]:
# 先を見る
I = i + dy*d
J = j + dx*d
# 枠内
if(0<=I<H and 0<=J<W):
# まだ決定してない
if(V[I][J] == INF):
# 壁を破壊しなくて良い時
if(
# 一個先を見るとき、そこが道
(d == 1 and SS[I][J] == ".") or
# ２個先を見るとき、そことその一個手前が道
(d == 2 and SS[I][J] == SS[i+dy][j+dx] == ".")
):
# 0
q.appendleft([c, I, J])
else:
# 1
q.append([c+1, I, J])
print(V[C][D])
補足
関係するリンク(参考文献など)
筆者について
- Atcoderアカウント
- 今回も不参加のため，成績なし．
- 解説で示したA問題の提出
- 解説で示したB問題の提出
- 解説で示したC問題の提出
- 解説で示したD問題の提出
その他
- 間違いを含んでいる可能性があります．
- 方針と言いつつ，方針ではない感想などを書いている可能性があります．
- A問題から解説がだんだん省略されます．
- コードに書かれている解説の文言と，その上に書いてある解説の文言を変えている場合があります．
最後に一言
- 初めての
0-1BFS