[ABC374] ABC 374(Atcoder Beginner Contest)のA~D(A,B,C,D)問題をPythonで解説(復習)
A問題
- スライス
[:]を利用して末尾の文字列を取得する．
A.py
"""
<方針>
- スライス `[:]` を利用して末尾の文字列を取得する．
"""
# 入力
S = input()
# 末尾3文字を取得
endS = S[-3:]
# sanだったら
if(endS == "san"):
print("Yes")
else:
print("No")
B問題
- 今何文字かの変数
nowを利用する． -
itertools.zip_longest()を利用して，文書の長さが違うケースを発見する． -
exit()を利用して，実行を即座に終わらせる．
B.py
"""
<方針>
- 今何文字かの変数 `now` を利用する．
- `itertools.zip_longest()` を利用して，文書の長さが違うケースを発見する．
- `exit()` を利用して，実行を即座に終わらせる．
"""
# ライブラリのインポート
import itertools
# 入力
S = list(input())
T = list(input())
now = 0
for s, t in itertools.zip_longest(S, T):
# 何文字目
now += 1
# 偽造されたかどうか
if(s != t):
print(now)
exit()
print(0)
C問題
方針
-
N==20程度なので，グループAに属させるかどうかの全パターンO(2^N)を試してもTLEしない．
前提
-
C問題あたりで，TLEになる人は，制約条件を見る癖をつけよう． -
AとB問題では，基本的に制約条件を見ずにやっても解ける． - しかし，
C問題以降では，制約条件を見ないと必ずTLEすると思っても良い． - 詳しい話は私の352回の記事 の
C問題の解説に記したので，是非参照してほしい．
C.py
"""
<方針>
- `N==20` 程度なので，グループ `A` に属させるかどうかの全パターン `O(2^N)` を試しても `TLE` しない．
"""
# 入力
N = int(input())
K = list(map(int, input().split()))
# 最適値
ans = float("inf")
# Aに属するかどうかを全パターン試す．
for i in range(1<<N):
# AとBのグループそれぞれの人数
A = 0
B = 0
# Aに属するかBに属するかをみる
for j in range(N):
if(i>>j & 1):
A += K[j]
else:
B += K[j]
# AとBで人数が多かった方で更新する．
ans = min(ans, max(A, B))
# 出力
print(ans)
D問題
- それぞれの線分をどの順番で印字するか
O(N!)． - それぞれの線分をどちら(
ABorCD)から印字するかO(2^N)． - 毎回線分を足し合わせる操作
O(N)． -
N==6なので，O(N! * 2^N * N) <= 276480より十分間に合いそう．
D.py
"""
<方針>
- それぞれの線分をどの順番で印字するか`O(N!)`．
- それぞれの線分をどちら(`AB` or `CD`)から印字するか`O(2^N)`．
- 毎回線分を足し合わせる操作`O(N)`．
- `N==6` なので，`O(N! * 2^N * N) <= 276480` より十分間に合いそう．
"""
# ライブラリ
import itertools
# 入力
N, S, T = map(int, input().split())
ABCD = [list(map(int, input().split())) for _ in range(N)]
# 距離を計算する関数
def dis(y, x, Y, X):
return ((y-Y)**2 + (x-X)**2)**(1/2)
# 最短距離
ans = float("inf")
# どの順番で印字するか
for seq in itertools.permutations(range(N)):
# どちらから印字するか
for i in range(1<<N):
tmp = 0 # 現在の距離
y = 0 # 現在の位置
x = 0 # 現在の位置
# 線分を足し合わせる操作
for j in range(N):
# 線分を決定
A, B, C, D = ABCD[seq[j]]
# ABまで位置を合わせる
if(i>>j & 1):
tmp += (dis(y, x, A, B)/S)
y = C
x = D
# CDまで位置を合わせる
else:
tmp += (dis(y, x, C, D)/S)
y = A
x = B
# ABとCDの間を書く
tmp += (dis(A, B, C, D)/T)
# 最短距離の更新
ans = min(ans, tmp)
# 出力
print(ans)
補足
関係するリンク(参考文献など)
筆者について
- Atcoderアカウント
- 今回も不参加のため，成績なし．
- 解説で示したA問題の提出
- 解説で示したB問題の提出
- 解説で示したC問題の提出
- 解説で示したD問題の提出
その他
- 間違いを含んでいる可能性があります．
- 方針と言いつつ，方針ではない感想などを書いている可能性があります．
- A問題から解説がだんだん省略されます．
- コードに書かれている解説の文言と，その上に書いてある解説の文言を変えている場合があります．
最後に一言
- 誰か〜．この提出の
WA取って〜〜