[ABC390] ABC 390(Atcoder Beginner Contest)のA~C(A,B,C)問題をPythonで解説(復習)
A問題
- 実際に連続する箇所を入れ替えてみて，昇順に並ぶかどうかで判断する．
A.py
"""
<方針>
- 実際に連続する箇所を入れ替えてみて，昇順に並ぶかどうかで判断する．
"""
# 入力
A = list(map(int, input().split()))
# 連続する場所の入れ替えをやってみる．
for i in range(4):
# Aをコピーする．
tmp = A[:]
# 入れ替えてみる
tmp[i], tmp[i+1] = tmp[i+1], tmp[i]
# 揃えば，Yesを出力して，プログラムを終了する．
if(tmp == [1, 2, 3, 4, 5]):
print("Yes")
exit()
# 不可能
print("No")
B問題
- 連続する部分において，以下の式(比の式)が成り立つことが等比数列であることの必要十分条件(多分)である．
A[i]*A[1] == A[i+1]*A[0]
B.py
"""
<方針>
- 連続する部分において，以下の式(比の式)が成り立つことが等比数列であることの必要十分条件(多分)である．
- `A[i]*A[1] == A[i+1]*A[0]`
"""
# 入力
N = int(input())
A = list(map(int, input().split()))
# 順番に比を見ていく．
for i in range(N-1):
# 比の式
if(A[i]*A[1] != A[i+1]*A[0]):
# 違ってればNoとしてプログラムを終了する．
print("No")
exit()
# 問題なければ，Yesを出力する．
print("Yes")
C問題
方針
- 黒マスのうち，最も上下左右な位置を記録する．
- 白マスのうち，前述の黒マスの範囲に入ってなければ問題ない．
- 全てのマスを閲覧することは，
O(HW)なので問題ない．
前提
-
C問題あたりで，TLEになる人は，制約条件を見る癖をつけよう． -
AとB問題では，基本的に制約条件を見ずにやっても解ける． - しかし，
C問題以降では，制約条件を見ないと必ずTLEすると思っても良い． - 詳しい話は私の352回の記事 の
C問題の解説に記したので，是非参照してほしい．
C.py
"""
<方針>
- 黒マスのうち，最も上下左右な位置を記録する．
- 白マスのうち，前述の黒マスの範囲に入ってなければ問題ない．
- 全てのマスを閲覧することは，`O(HW)` なので問題ない．
"""
H, W = map(int, input().split())
SS = [list(input()) for _ in range(H)]
# 上下左右を保持する．
top = H
bottom = -1
left = W
right = -1
# 黒マスをみて，上下左右を記録する．
for i in range(H):
for j in range(W):
# 黒マスの時
if(SS[i][j] == "#"):
# 更新
top = min(top, i)
bottom = max(bottom, i)
left = min(left, j)
right = max(right, j)
# 白マスを見て，問題が無いかを確認する．
for i in range(H):
for j in range(W):
# 白マスのとき，
if(SS[i][j] == "."):
# 黒マスの範囲に入っているとNG
if((top <= i <= bottom) and (left <= j <= right)):
print("No")
exit()
# 上限をクリアすればOK
print("Yes")
補足
関係するリンク(参考文献など)
筆者について
- Atcoderアカウント
- 今回も不参加のため，成績なし．
- 解説で示したA問題の提出
- 解説で示したB問題の提出
- 解説で示したC問題の提出
その他
- 間違いを含んでいる可能性があります．
- 方針と言いつつ，方針ではない感想などを書いている可能性があります．
- A問題から解説がだんだん省略されます．
- コードに書かれている解説の文言と，その上に書いてある解説の文言を変えている場合があります．
最後に一言
- D,E解けるようになりたいな．