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

A問題

植物の高さを2**dayずつ足してあげる．
高橋くんの身長(H)を越したら，printして，breakする．

A.py

"""
<方針>
- 植物の高さを`2**day`ずつ足してあげる．
- 高橋くんの身長(`H`)を越したら，`print`して，`break`する．
"""
# 標準入力を受け取る．
H = int(input())

# 日付
day = 0
# 植物の身長
plant = 0

# 1日ずつ経過させる．
while True:
  # 植物の身長を伸ばす
  plant += 2**day
  
  # 日付を経過させる．
  day += 1
  
  # 高橋くんの身長を植物が越した時，
  if(H<plant):
    # 日付を出力する．
    print(day)
    # 無限ループを脱出する．
    break

B問題

SとCはそれぞれstrとintであり，同時に渡されるので，mapせず受け取る．
レートの総和Tを求める．
ユーザー名の順番にsortし，T%N番目の人の名前を出力する．

B.py

"""
<方針>
- `S`と`C`はそれぞれ`str`と`int`であり，同時に渡されるので，`map`せず受け取る．
- レートの総和`T`を求める．
- ユーザー名の順番に`sort`し，`T%N`番目の人の名前を出力する．
"""
# 標準入力を受け取る．
N = int(input()) # ユーザーのかず
S = [] # ユーザー名
C = [] # レート
# それぞれのユーザーごとに入力を受け取る．
for i in range(N):
  # ユーザー名とレートをとりあえず受け取る．
  s, c = input().split()
  # ユーザー名を登録する．
  S.append(s) 
  # レートをintにして登録する．
  C.append(int(c))

# レートの総和を求める．
T = sum(C)

# ユーザー名をsortする．
S.sort()

# T%N番目のユーザー名を出力する．
print(S[T%N])

C問題

前提

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

方針

残すカードのindexを最終的に出力するので，カードに強さAとコストCの情報に追加して，indexの情報も記録することとする．
カード一枚を固定し，強さAとコストCがそれぞれ弱く，コストが高いカードでないものを残せば良い．
だが，自明にカードをN回固定して，N回比較するのはO(N^2)かかるので，TLEしてしまう．
そこで，カードを強さ順でsortするO(NlogN)．
そして，カードを強い順番に見ていくO(N)．
次に，カードを見ていくたびに，カードの強さはだんだん弱くなるので，カードのコストだけを確認すれば良い．
カードを見る毎に，今まで現れたカードのコストで最も低いものを記録しておき，それを下回ったものを残せば良い．

C.py

"""
<方針>
- 残すカードの`index`を最終的に出力するので，カードに強さ`A`とコスト`C`の情報に追加して，`index`の情報も記録することとする．
- カード一枚を固定し，強さ`A`とコスト`C`がそれぞれ弱く，コストが高いカードでないものを残せば良い．
- だが，自明にカードを`N`回固定して，`N`回比較するのは`O(N^2)`かかるので，`TLE`してしまう．
- そこで，カードを強さ順で`sort`するO(NlogN)．
- そして，カードを強い順番に見ていくO(N)．
- 次に，カードを見ていくたびに，カードの強さはだんだん弱くなるので，カードのコストだけを確認すれば良い．
- カードを見る毎に，今まで現れたカードのコストで最も低いものを記録しておき，それを下回ったものを残せば良い．
"""

# 標準入力を受け取る．
N = int(input())
AC = []
for i in range(N):
  a, c = map(int, input().split())
  # 強さ, コスト, indexの情報を登録する．
  AC.append([a, c, i])
  
# 強さの順番でsortする．
AC.sort(lambda x: x[0])

# 残すカードを記録するlist
ans = []
# コストが最も低いものを記録するもの．初期値は無限とする．
mi = float("inf")
# 強い順番にカードを見る
for i in reversed(range(N)):
  # 強さ, コスト, indexの情報を取得する．
  a, c, ind = AC[i]
  # コストが最低を下回った時，
  if(c<mi):
    # 最低コストを更新する．
    mi = c
    # 残すカードを記録する．
    ans.append(ind+1)

# 残すカードのindexをsortする．
ans.sort()

# 出力
print(len(ans))
print(*ans)

D問題

計算量を考えなくて良い問題です．ただ，少々複雑な場合分けが要求されます．
私の解説は少々煩雑かもしれません．ご了承ください．
C-Aの辺に含まれる面積の2倍(W)を求める．
- 原点からx軸に正の方向に見ると，周期4で[2, 1, 0, 1]で面積が変化していることに留意する．
- 原点からy軸に正の方向に見ると，周期2で[2, 1, 0, 1]と[1, 2, 1, 0]で変化していることに留意する．
  - y==0と周期が一致してるWをW0とする．
  - y==1と周期が一致してるWをW1とする．
C-Aの辺に含まれる面積をD-B方向に増やす．
- y軸の方向で周期2で変化しているため，W0+W1の値を(D-B)//2の高さでかける．
- D-Bの値が奇数の時は，W0またはW1をBの奇数に応じて一度足す．

D.py

"""
<方針>
- 計算量を考えなくて良い問題です．ただ，少々複雑な場合分けが要求されます．
- 私の解説は少々煩雑かもしれません．ご了承ください．
- `C-A`の辺に含まれる面積の`2`倍(`W`)を求める．
  - 原点から`x`軸に正の方向に見ると，周期`4`で`[2, 1, 0, 1]`で面積が変化していることに留意する．
  - 原点から`y`軸に正の方向に見ると，周期`2`で`[2, 1, 0, 1]`と`[1, 2, 1, 0]`で変化していることに留意する．
    - `y==0`と周期が一致してる`W`を`W0`とする．
    - `y==1`と周期が一致してる`W`を`W1`とする．
- `C-A`の辺に含まれる面積を`D-B`方向に増やす．
  - `y`軸の方向で周期`2`で変化しているため，`W0+W1`の値を`(D-B)//2`の高さでかける．
  - `D-B`の値が奇数の時は，`W0`または`W1`をBの奇数に応じて一度足す．
"""
# 標準入力
A, B, C, D = map(int, input().split())

# 面積の辺の大きさ
X = C-A
Y = D-B

# 長方形の左下はどのような周期で始まっているかみる．
a = A%4
b = B%2

# 面積の大きさを周期で割った商と余りを求める．
xDi, xMo = divmod(X, 4)
yDi, yMo = divmod(Y, 2)

# 周期
ls = [
  2, 1, 0, 1, 
  2, 1, 0, 1, 
  2, 1, 0, 1, 
  ]

# X方向の辺の面積
W0 = xDi*4 + sum(ls[4+a-0:4+a-0+xMo])
W1 = xDi*4 + sum(ls[4+a-1:4+a-1+xMo])

# 面積を縦方向に増やす．
ans = (W0+W1)*(yDi)

# 高さが奇数のときの処理
if(yMo==1):
  if(b==0):
    ans += W0
  else:
    ans += W1

# 出力
print(ans)

E問題

公式解説と一緒です．

E.py

"""
<方針>
- 公式解説と一緒です．
"""
# 標準入力を受け取る
N = int(input())
A = []
B = []
for i in range(N):
  a, b = map(int, input().split())
  A.append(a)
  B.append(b)
  
# bitDP
## index: ２進数にして，bitが立ってるところのみカードが盤面に残っている状態を表現
## value↓
### 0: 勝つことができない状態
### 1: 勝つことができる状態
### -1: 調べてないから勝てるかどうかわからないorその状態に到達することはない．

# dpの初期化
dp = [-1]*(1<<N)
# 盤面にカードが一枚もない状態は，勝つことができない
dp[0] = 0

# bitをずらしていく
for i in range(1<<N):
  
  # 勝つことができる時に1が入る．公式解説と同様に，2枚取った状態で負ける状態が少なくとも一つあれば，1になる実装にした．
  winnable = 0
  # 取るカードを1枚選択
  for j in range(N):
    # 取るカードを一枚選択
    for k in range(N):
      # j番目とk番目にカードがあるかどうかの判定
      if(i&(1<<j) and i&(1<<k)):
        # j番目とk番目の表裏のいずれかが合致するかの判定
        if(A[j]==A[k] or B[j]==B[k]):
          # j番目とk番目のカードを引いた状態が，勝つことができないかの判定
          if(dp[i^(1<<j)^(1<<k)]==0):
            # カードを引いて，勝つことができない状態を作れるのならば，元の状態は勝つことができる
            winnable = 1
  # 0または1が代入される．
  dp[i] = winnable
  
# 出力
if(dp[-1]==1):
  print("Takahashi")
else:
  print("Aoki")

F問題

公式解説通りです．

F.py

"""
<方針>
- 公式解説通りです．
"""

from bisect import bisect_left

# caseの数
T = int(input())

# case毎
for _ in range(T):
  N = int(input())
  A = list(map(int, input().split()))
  
  # 左方向からLIS
  ls = []
  L = [0]*N
  for i in range(N):
    index = bisect_left(ls, A[i])
    if(index<len(ls)):
      ls[index] = A[i]
    else:
      ls.append(A[i])
    L[i] = index+1
  
  # 右方向からLIS
  ls = []
  R = [0]*N
  for i in reversed(range(N)):
    index = bisect_left(ls, -A[i])
    if(index<len(ls)):
      ls[index] = -A[i]
    else:
      ls.append(-A[i])
    R[i] = index+1
  
  # l+r-1==LISとなる部分を探す
  ans = []
  for i in range(N):
    if(L[i]+R[i]-1==len(ls)):
      ans.append(i+1)
      
  # 出力
  print(len(ans))
  print(*ans)

補足

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

筆者について

その他

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

最後に一言

「ChatGPTなどのAIを競プロで使っていいのか」っていうのが少し話題になりましたね．さて，生成AIに関して個人的に好きな動画を添付させていただきます．