[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.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!)．
それぞれの線分をどちら(AB or CD)から印字するか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)

補足

関係するリンク(参考文献など)

今回のコンテスト

筆者について

その他

間違いを含んでいる可能性があります．
方針と言いつつ，方針ではない感想などを書いている可能性があります．
A問題から解説がだんだん省略されます．
コードに書かれている解説の文言と，その上に書いてある解説の文言を変えている場合があります．

最後に一言

誰か〜．この提出の WA 取って〜〜