[ABC414] ABC 414(Atcoder Beginner Contest)のA~D(A,B,C,D)問題をPythonで解説(復習)
A問題
- 一人ずつ全部見れるかを確認する。
A.py
"""
<方針>
- 一人ずつ全部見れるかを確認する。
"""
# 入力
N, L, R = map(int, input().split())
XY = [list(map(int, input().split())) for _ in range(N)]
# 全部見れるやつだけ抽出
full = list(filter(lambda xy: xy[0]<=L and R<=xy[1], XY))
# 人数を取得
ans = len(full)
# 出力
print(ans)
B問題
-
Sを作っていって、長すぎたら処理を中断する。
B.py
"""
<方針>
- `S` を作っていって、長すぎたら処理を中断する。
"""
# 入力
N = int(input())
# 答え
S = ""
# Sを作っていく。
for _ in range(N):
# 入力
c, l = input().split()
# intに変更
l = int(l)
# 長過ぎるかどうか
if(100 < len(S) + l):
print("Too Long")
exit()
# Sに追加する。
S += c*l
# 出力
print(S)
C問題
方針
-
Nの線形時間は許されない。 - 十進法の回文列挙は左右に分割して考えれば十分なので、
O(√N)となる。 - 列挙した十進法の回文が、
A進法になるかどうかを確認してけば良い。 - 実行が
3秒制限だが、それでも結構重たい処理なので、気をつけて処理をしないと、TLEになる。- 特に、
A = 2, N = 1000000000000には気をつけた方がいい。
- 特に、
前提
-
C問題あたりで，TLEになる人は，制約条件を見る癖をつけよう． -
AとB問題では，基本的に制約条件を見ずにやっても解ける． - しかし，
C問題以降では，制約条件を見ないと必ずTLEすると思っても良い． - 詳しい話は私の352回の記事 の
C問題の解説に記したので，是非参照してほしい．
C.py
"""
<方針>
- `N` の線形時間は許されない。
- 十進法の回文列挙は左右に分割して考えれば十分なので、`O(√N)` となる。
- 列挙した十進法の回文が、`A` 進法になるかどうかを確認してけば良い。
- 実行が `3` 秒制限だが、それでも結構重たい処理なので、気をつけて処理をしないと、`TLE` になる。
- 特に、`A = 2, N = 1000000000000` には気をつけた方がいい。
"""
A = int(input())
N = int(input())
# 両方で回文になるものの総和
ans = 0
# 十進法の回文を出すために必要なもの
LEFT = [""] + [str(x) for x in range(1, 10**6)]
RIGHT = [""] + [str(x)[::-1] for x in range(1, 10**6)]
MID = [""] + [str(x) for x in range(0, 10)]
for left, right in zip(LEFT, RIGHT):
for mid in MID:
# 十進法の回文
strNum10 = left + mid + right
# 空文字は除く
if(strNum10 == ""):
continue
# 数字にする
intNum10 = int(strNum10, 10)
# 1~Nのものだけを抽出
if not (1<=intNum10<=N):
continue
# A進法を生成
strNumA = []
n = intNum10
while n > 0:
n, mo = divmod(n, A)
strNumA.append(str(mo))
# A進法での回文判定
ok = True
for ind in range(len(strNumA)//2):
if(strNumA[ind] != strNumA[-(ind+1)]):
ok = False
break
# 総和に追加
if(ok):
ans += intNum10
print(ans)
D問題
-
Xがデカ過ぎるので、Xをリストで持つことはできない。 - 家の座標を全て出す。
- 隣の家との距離を出す。
- 基地局が足らない分を、距離が近い順から答えに追記していく。
D.py
"""
<方針>
- `X` がデカ過ぎるので、`X`をリストで持つことはできない。
- 家の座標を全て出す。
- 隣の家との距離を出す。
- 基地局が足らない分を、距離が近い順から答えに追記していく。
"""
N, M = map(int, input().split())
# 重複する座標が無いように、全ての家の座標を小さい順から取得
X = sorted(list(set(map(int, input().split()))))
# 重複座標が無いように、家の個数を数える
N = len(X)
# 隣の家との距離を計算する。
Y = []
for i in range(N-1):
Y.append(X[i+1]-X[i])
# 距離が近い順にする。
Y.sort()
# 基地局が足りない分を計算する
diff = max(0, N-M)
# 最小の電波強度を計算する。
ans = 0
for i in range(diff):
ans += Y[i]
print(ans)
補足
関係するリンク(参考文献など)
筆者について
- Atcoderアカウント
- 今回も不参加のため，成績なし．
- 解説で示したA問題の提出
- 解説で示したB問題の提出
- 解説で示したC問題の提出
- 解説で示したD問題の提出
その他
- 間違いを含んでいる可能性があります．
- 方針と言いつつ，方針ではない感想などを書いている可能性があります．
- A問題から解説がだんだん省略されます．
- コードに書かれている解説の文言と，その上に書いてある解説の文言を変えている場合があります．