LoginSignup
4
1
@mattsunkun

ABC369(Atcoder Beginner Contest)のA~F(A,B,C,D,E,F)問題をPythonで解説(復習)

Posted at

ABC369(Atcoder Beginner Contest)のA~F(A,B,C,D,E,F)問題をPythonで解説(復習)

A問題

  • 以下の 3 パターンしかない．
    • A == B のとき， 1 種類のみ
    • (A - B)%2 == 1 のとき，2 種類のみ
    • それ以外の時， 3 種類のみ
A.py
"""
<方針>
- 以下の `3` パターンしかない．
  - `A == B` のとき， `1` 種類のみ
  - `(A - B)%2 == 1` のとき，`2` 種類のみ
  - それ以外の時， `3` 種類のみ
"""
# 入力
A, B = map(int, input().split())

# 1種類
if(A==B):
  print(1)
# 2種類
elif((A-B)%2==1):
  print(2)
# 3種類
else:
  print(3)

B問題

  • 右手と左手で分けて考える．
  • ピアノを弾く時に，手を動かせば最小の疲労になる．
  • 愚直にシミュレーションを行う．
B.py
"""
<方針>
- 右手と左手で分けて考える．
- ピアノを弾く時に，手を動かせば最小の疲労になる．
- 愚直にシミュレーションを行う．
"""
# 入力
N = int(input())
L = []
R = []
for i in range(N):
  # a, bを文字列をして受け取る
  a, b = map(str, input().split())
  # aは数字に変換する
  a = int(a)
  
  # 右手に登録
  if(b=="R"):
    R.append(a)
  # 左手に登録
  else:
    L.append(a)

# 疲労度のシミュレーション
def simulate(hand):
  # 疲労度の合計値
  ret = 0
  # 弾くとき，
  if(len(hand)>0):
    # 最初の位置
    x = hand[0]
    for i in range(1, len(hand)):
      # 疲労度を増やす
      ret += abs(x-hand[i])
      # 次の手の位置
      x = hand[i]
  return ret
  

# 疲労度の合計値
ans = 0
# 左手のシミュレーション
ans += simulate(L)
# 右手のシミュレーション
ans += simulate(R)

print(ans)

C問題

方針

  • 等差数列の左端を固定して，一つずつ考えていては，計算量が N^2 になってしまい， TLE してしまう．
  • そこで，等差数列を成すには，全ての等差が等しくなければならないことを利用する．
    • 等差が等しく連続しているところに分けて，それぞれ O(1) で個数が求められれば，計算量は全体で O(N) となる．
    • 等差が等しく L 個連続するところは，自分自身のみをのぞいて， (L-1)*L//2 と計算できる．(定数時間で求まる)
    • 最後に，自分自身のみ分 N を足せば AC する．

前提

  • C問題あたりで，TLEになる人は，制約条件を見る癖をつけよう．
  • AとB問題では，基本的に制約条件を見ずにやっても解ける．
  • しかし，C問題以降では，制約条件を見ないと必ずTLEすると思っても良い．
  • 詳しい話は私の352回の記事 のC問題の解説に記したので，是非参照してほしい．
C.py
"""
<方針>
- 等差数列の左端を固定して，一つずつ考えていては，計算量が `N^2` になってしまい， `TLE` してしまう．
- そこで，等差数列を成すには，全ての等差が等しくなければならないことを利用する．
  - 等差が等しく連続しているところに分けて，それぞれ `O(1)` で個数が求められれば，計算量は全体で `O(N)` となる．
  - 等差が等しく `L` 個連続するところは，自分自身のみをのぞいて， `(L-1)*L//2` と計算できる．(定数時間で求まる)
  - 最後に，自分自身のみ分 `N` を足せば `AC` する．
"""
# 入力
N = int(input())
A = list(map(int, input().split()))

# 差分を計算する．
dif = []
for i in range(N-1):
  dif.append(A[i]-A[i+1])
dif.append(10**11) # 番兵

# 個数
ans = 0
# 現在の差分
now = 10**10 # 初期値は番兵
# 連続した数
L = 0
for i in range(N):
  # 現在の差分
  d = dif[i]
  
  # 差分が直前と等しいとき
  if(now==d):
    L += 1
  # 差分が直前と等しくなかったので，直前の等差数列の個数を計算
  else:
    ans += (L-1)*L//2 
    # 次回の分
    now = d
    L = 2

# 自分自身のみのパターンを足す
ans += N

# 出力
print(ans)

D問題

  • 今回の敵を偶数回目に倒したかどうかで分けた dp を作成すればいける．
D.py
"""
<方針>
- 今回の敵を偶数回目に倒したかどうかで分けた `dp` を作成すればいける．
"""
# 入力
N = int(input())
A = list(map(int, input().split()))

# dp[i][j]
## i: i匹目までの敵
## j: 0の時，奇数回目で倒した．1の時，偶数回目で倒した．
dp = [[-1]*2 for _ in range(N)]

# 初期値
dp[0][0] = A[0]
dp[0][1] = 0

# 遷移
for i in range(N-1):
  # 「偶数回目で直前倒して，今回倒す」 or 「今回倒さない」
  dp[i+1][0] = max(dp[i][1] + A[i+1], dp[i][0])
  # 「奇数回めで直前倒して，今回倒す」 or 「今回倒さない」
  dp[i+1][1] = max(dp[i][0] + 2*A[i+1], dp[i][1])
  
print(max(dp[N-1]))

E問題

  • N=400 より，ワーシャルフロイドを使って，任意の頂点間の最短距離を求めておく．
  • K=5 より，橋をどの順番で，どの向きで渡るかを全列挙して，最短距離となるパターンを出力する．
  • 計算量は， O(N^3 + Q*K!*2^K) より，10^7 ほどの計算量だが，実行時間が長めなので，多分大丈夫．
E.py
"""
<方針>
- `N=400` より，ワーシャルフロイドを使って，任意の頂点間の最短距離を求めておく．
- `K=5` より，橋をどの順番で，どの向きで渡るかを全列挙して，最短距離となるパターンを出力する．
- 計算量は， `O(N^3 + Q*K!*2^K)` より，`10^7` ほどの計算量だが，実行時間が長めなので，多分大丈夫．
"""
N, M = map(int, input().split())

# 橋のコストを記録する．
INF = 10**20
dp = [[INF]*N for _ in range(N)]
# 単純に橋を記録
L = []
for i in range(M):
  u, v, t = map(int, input().split())
  u -= 1
  v -= 1
  
  # 単純に橋を記録
  L.append([u, v, t])
  
  # 複数の橋がある時は，最短の橋だけを記録する．
  dp[u][v] = min(dp[u][v], t)
  dp[v][u] = min(dp[v][u], t)

# 自分自身への橋は距離0である
for i in range(N):
  dp[i][i] = 0

# ワーシャルフロイド
for k in range(N):
  for i in range(N):
    for j in range(N):
      dp[i][j] = min(dp[i][j], dp[i][k]+dp[k][j])


import itertools

Q = int(input())
for i in range(Q):
  # 入力
  K = int(input())
  B = list(map(lambda x: int(x)-1, input().split()))
  
  # 最短距離
  ANS = INF
  
  # どの橋の順番で渡るかの全パターン
  P = list(itertools.permutations(B))
  for p in P:
    # 橋を右から渡るか左から渡るかの全パターン
    for j in range(1<<K):
      # 渡る島の順番
      ls = []
      ls.append(0) # 最初の島
      # 距離
      ans = 0
      # 島を渡ってみる
      for k in range(K):
        
        # 今の橋の情報
        u, v, t = L[p[k]]
        
        # 指定された橋で渡る
        ans += t
        
        # 左から渡るとき
        if(1<<k & j):
          ls.append(u)
          ls.append(v)
        # 右から渡る時
        else:
          ls.append(v)
          ls.append(u)
      
      ls.append(N-1) # 最後の島
      
      # 指定はされていない橋で渡って，全てを結ぶ
      for k in range(K+1):
        # 指定されていないところだけを足す
        ans += dp[ls[2*k]][ls[2*k+1]]
        
        
      # if(ans<=9):
      #   print(ans)
      # # ans +=
      # print(ls)
      # print(p)
      # print(ans)
      # exit(1)
      ANS = min(ANS, ans)
  print(ANS)
  # exit(1)
      
        
# print(dp)

F問題

  • 公式解説と一緒
F.py
"""
<方針>
- 公式解説と一緒
"""

from bisect import bisect_right as br

H, W, N = map(int, input().split())
V = [list(map(int, input().split())) for _ in range(N)]

# C方向で昇順にする．
V.sort()

# LISを求めている．
dp = [float("inf")]*N
ind = [-1]*N
pre = [-1]*N
for i in range(N):
  it = br(dp, V[i][1])
  dp[it] = V[i][1]
  ind[it] = i
  pre[i] = ind[it - 1] if it > 0 else -1

# 何個コインの間を移動するか．
m = N-1
while ind[m] == -1:
  m -= 1

# 経路を逆順に求めている．
path = [[H, W]]
now = ind[m]
while now != -1:
  path.append(V[now])
  now = pre[now]
path.append([1, 1])
# 正順に戻す．
path.reverse()

# 具体的な求めている．
ans = []
for i in range(len(path)-1):
  # srcとdst
  dst = path[i+1]
  src = path[i]
  
  # DownとRightの個数
  d = dst[0] - src[0]
  r = dst[1] - src[1]
  
  # 答えに追記
  ans.extend(["D"]*d)
  ans.extend(["R"]*r)

# 出力
print(len(path)-2)
print("".join(ans))

補足

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

筆者について

その他

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

最後に一言

  • 惰性石器，スマホ．
4
1
0

Register as a new user and use Qiita more conveniently

  1. You get articles that match your needs
  2. You can efficiently read back useful information
  3. You can use dark theme
What you can do with signing up
Sign upLogin
4
1