[ABC382] ABC 382(Atcoder Beginner Contest)のA~D(A,B,C,D)問題をPythonで解説(復習)

Posted at 2024-12-05

[ABC382] ABC 382(Atcoder Beginner Contest)のA~D(A,B,C,D)問題をPythonで解説(復習)

A問題

最初の空き箱の数 + 経過した日数

A.py

"""
<方針>
- `最初の空き箱の数` + `経過した日数`
"""
# 入力
N, D = map(int, input().split())
S = input()

# 最初の空き箱の数 + 経過した日数
ans = S.count(".") + D

# 出力
print(ans)

B問題

シミュレーションして愚直に解く．
D 日，一番右のクッキー @ を空箱 . にする．
S を書き換え可能にするため，list で受け取る．

B.py

"""
<方針>
- シミュレーションして愚直に解く．
- `D` 日，一番右のクッキー `@` を空箱 `.` にする．
- `S` を書き換え可能にするため，`list` で受け取る．
"""
# 入力
N, D = map(int, input().split())
S = list(input())

# D日シミュレーション
for _ in range(D):
  # 右から順番に見る
  for i in reversed(range(N)):
    # クッキーがあったら
    if(S[i] == "@"):
      # クッキーを食べて空箱にする．
      S[i] = "."
      # 次の日に行く
      break

# 出力
print("".join(S))

C問題

方針

流れてきた寿司を誰が食べるかを順番に見ていては，O(N^2) かかってしまい，間に合わない．
A の情報から，あらかじめ特定の美味しさの寿司は誰が食べるかのリスト who_eat を計算しておく．O(N)
- 既に食べられている美味しさ min_taste を用いると O(N) でできそう．
あとは，計算しておいたリスト who_eat を用いて全ての B の値について計算すると O(N) で処理ができる．
全体として，O(N) で処理ができた．

前提

C問題あたりで，TLEになる人は，制約条件を見る癖をつけよう．
AとB問題では，基本的に制約条件を見ずにやっても解ける．
しかし，C問題以降では，制約条件を見ないと必ずTLEすると思っても良い．
詳しい話は私の352回の記事のC問題の解説に記したので，是非参照してほしい．

C.py

"""
<方針>
- 流れてきた寿司を誰が食べるかを順番に見ていては，`O(N^2)` かかってしまい，間に合わない．
- `A` の情報から，あらかじめ特定の美味しさの寿司は誰が食べるかのリスト `who_eat` を計算しておく．`O(N)`
  - 既に食べられている美味しさ `min_taste` を用いると `O(N)` でできそう．
- あとは，計算しておいたリスト `who_eat` を用いて全ての `B` の値について計算すると `O(N)` で処理ができる．
- 全体として，`O(N)` で処理ができた．
"""
# 入力
N, M = map(int, input().split())
A = list(map(int, input().split()))
B = list(map(int, input().split()))

# 想定される美味しさの最大値+1
MAX = 2*10**5 + 1

# 誰が食べるかのリスト
## index: 美味しさ
## value: 誰が食べるか
who_eat = [-1]*MAX

# 既に食べられた最低の美味しさ
min_taste = MAX
# 手前の人から美食度をみる
for i, a in enumerate(A):
  # 未だに誰も食べたことのない低い美味しさの場合
  if(a<min_taste):
    # その人間が食べることを示していく．
    while min_taste != a:
      # 最低の美味しさを更新
      min_taste -= 1
      # 誰が食べるかを記録
      who_eat[min_taste] = (i + 1)

# 誰が食べるかを出力
for b in B:
  # 答え
  print(who_eat[b])

D問題

頑張って再帰で実装する．
左の値から考えて，次の値はどこまでありえるかを考えればいける．

D.py

"""
<方針>
- 頑張って再帰で実装する．
- 左の値から考えて，次の値はどこまでありえるかを考えればいける．
"""
# 再帰のおまじない
import pypyjit
pypyjit.set_param('max_unroll_recursion=-1')
import sys
sys.setrecursionlimit(10**6)

# 入力
N, M = map(int, input().split())

# 再帰
def rec(ANS):
  # 現在の一つあたりの長さ
  n = len(ANS[0])
  # 目的の長さになったら終了
  if n == N:
    return ANS
  else:
    # 戻り値
    RET = []
    # 入力値を一つずつ見る
    for ans in ANS:
      # 次の値を考える
      for new in range(ans[-1]+10, M-10*(N-n-1)+1):
        # 次の値を加えたものを追加する．
        RET.append(ans[:] + [new])
    # さらなる次を追加してもらったものが答え
    return rec(RET)

# 再帰の実行．
ANS = rec([[x] for x in range(1, M-10*(N-1)+1)]) # 初期値は[[1], [2], ...[M-10*(N-1)]]

# 出力
print(len(ANS))
for ans in ANS:
  print(*ans)

補足

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

今回のコンテスト

筆者について

その他

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

最後に一言

とある友人へ．「謝　罪　の　何　様」でしたね．すみません．

You get articles that match your needs
You can efficiently read back useful information
You can use dark theme

What you can do with signing up