[ABC378] ABC 378(Atcoder Beginner Contest)のA~D(A,B,C,D)問題をPythonで解説(復習)
A問題
- 何色のボールが何個あるかを管理するリスト
lsColorを作成する． -
Aの入力に対して，lsColorを更新していく． - それぞれの
lsColorを2で割った時の商の合計値が捨てられる操作の最大値．
A.py
"""
<方針>
- 何色のボールが何個あるかを管理するリスト `lsColor` を作成する．
- `A` の入力に対して， `lsColor` を更新していく．
- それぞれの `lsColor` を `2` で割った時の商の合計値が捨てられる操作の最大値．
"""
# 入力
A1234 = list(map(int, input().split()))
# ボールを管理するリスト
lsColor = [0]*5
# A1~A4に対して処理を行う．
for A in A1234:
# ボールを新しく登録する．
lsColor[A] += 1
# 答え
ans = 0
for color in lsColor:
# 2で割った時の商を答えに追加
ans += (color//2)
# 出力
print(ans)
B問題
-
dをqで割ってみる．- 余りが
rであった時，dが答え． - 余りが
rより小さい時，余りを省いた分とrの和が答え． - 余りが
rより大きい時，余りを省いた分とqとrの和が答え．
- 余りが
B.py
"""
<方針>
- `d` を `q` で割ってみる．
- 余りが `r` であった時， `d` が答え．
- 余りが `r` より小さい時，余りを省いた分と `r` の和が答え．
- 余りが `r` より大きい時，余りを省いた分と `q` と `r` の和が答え．
"""
# ゴミの種類
N = int(input())
# それぞれのゴミを捨てる日を記録する．
trash = [list(map(int, input().split())) for _ in range(N)]
# 質問の個数
Q = int(input())
for _ in range(Q):
# 質問
t, d = map(int, input().split())
# ゴミの種類を記録しているlistは0-indexedなので
t -= 1
# ゴミを捨てる日の情報を取得
q, r = trash[t]
# 割ってみる
di, mo = divmod(d, q)
if(mo==r):
ans = d
if(mo<r):
ans = di*q + r
if(mo>r):
ans = di*q + q + r
# 質問の答え
print(ans)
C問題
方針
- 毎回
Aの配列を捜査してその数値が出たかどうかを確認すると，O(N^2)よりTLEする． - 今まででた値を
O(1)で確認できる方法があれば良い．-
listを使うと，Aが大きすぎてMLEの方向で良くない．
-
-
dictを使い，keyをAの値とし，valueを前回値が出た時の位置とすれば良い． - すると，全体では
O(N)となって間に合う．
前提
-
C問題あたりで，TLEになる人は，制約条件を見る癖をつけよう． -
AとB問題では，基本的に制約条件を見ずにやっても解ける． - しかし，
C問題以降では，制約条件を見ないと必ずTLEすると思っても良い． - 詳しい話は私の352回の記事 の
C問題の解説に記したので，是非参照してほしい．
C.py
"""
<方針>
- 毎回 `A` の配列を捜査してその数値が出たかどうかを確認すると， `O(N^2)` より `TLE` する．
- 今まででた値を `O(1)` で確認できる方法があれば良い．
- `list` を使うと， `A` が大きすぎて `MLE` の方向で良くない．
- `dict` を使い， `key` を `A` の値とし， `value` を前回値が出た時の位置とすれば良い．
- すると，全体では `O(N)` となって間に合う．
"""
# 入力
N = int(input())
A = list(map(int, input().split()))
# 答え
ans = []
# 値が出たかどうかのdict
dic = dict()
# 位置と値を取得
for i, a in enumerate(A):
# 値が既に発見されてる時
if(a in dic):
# 前回の位置を取得
past = dic[a]
# 位置を0-indexedを考慮して出力
ans.append(past+1)
# 位置を記録
dic[a] = i
# 値がまだ発見されてない時
else:
# 答えを-1とする．
ans.append(-1)
# 位置を記録
dic[a] = i
# 出力
print(*ans)
D問題
- 計算量は気にするほど大きくない．実装できるかどうかである．
- 障害物が無いところ全てから始めて，順々に動いたところを盤面に記録していき，
K回移動したら，答えに追記する． - 定数倍が怖いので，盤面
Sをstrではなく，boolで管理し，多重リストでなく，一次元リストで管理する．
D.py
"""
<方針>
- 計算量は気にするほど大きくない．実装できるかどうかである．
- 障害物が無いところ全てから始めて，順々に動いたところを盤面に記録していき， `K` 回移動したら，答えに追記する．
- 定数倍が怖いので，盤面 `S` を `str` ではなく， `bool` で管理し，多重リストでなく，一次元リストで管理する．
"""
# 入力
H, W, K = map(int, input().split())
TT = [input() for _ in range(H)]
# 障害物があるところはFalseとして一次元リストで管理する．
S = []
for i in range(H):
for j in range(W):
S.append(TT[i][j] == ".")
# 再帰的に探索する関数
def rec(y, x, k, S):
# 上下左右への移動
for dy, dx in [
(1, 0),
(0, 1),
(-1, 0),
(0, -1)
]:
# 移動先の座標
Y = y+dy
X = x+dx
# 枠内に収まってる時
if(0<=Y<H and 0<=X<W):
# 一次元に直した時のインデックス
tar = Y*W + X
# 障害物がなくて，まだ歩いてない時
if(S[tar]):
# 現在の盤面のコピーをとる．
T = S[:]
# 今の位置を歩いたところとして記録する．
T[tar] = False
# 歩いた回数がKに達した時
if(k+1 == K):
# 答えに追記する．
global ans
ans += 1
# 歩いた回数がKに達さない時，
else:
# 再帰的に歩み進める
rec(Y, X, k+1, T)
# 答え
ans = 0
# 全ての位置からスタートできるかを確認する．
for i in range(H):
for j in range(W):
# 一次元に直した時のインデックス
tar = i*W + j
# 障害物でない時，
if(S[tar]):
# 盤面のコピーをとる．
T = S[:]
# 現在の位置を歩いたところとして記録する．
T[tar] = False
# 再帰的に歩み始める．
rec(i, j, 0, T)
# 出力
print(ans)
補足
関係するリンク(参考文献など)
筆者について
- Atcoderアカウント
- 今回も不参加のため，成績なし．
- 解説で示したA問題の提出
- 解説で示したB問題の提出
- 解説で示したC問題の提出
- 解説で示したD問題の提出
その他
- 間違いを含んでいる可能性があります．
- 方針と言いつつ，方針ではない感想などを書いている可能性があります．
- A問題から解説がだんだん省略されます．
- コードに書かれている解説の文言と，その上に書いてある解説の文言を変えている場合があります．
最後に一言
- おねむねむ．やらなきゃいけないことをやってなくてやばい．