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

A問題

• R とある数を足して，下2桁を 00 にすれば，レートは上がったと考えて良い．
• つまり， 100 から R を 100 で割った余り(R%100)を引いたものが答えとなる．

A.py

"""
<方針>
- `R` とある数を足して，下2桁を `00` にすれば，レートは上がったと考えて良い．
- つまり， `100` から `R` を `100` で割った余り(`R%100`)を引いたものが答えとなる．
"""
# 標準入力からRを受け取る．
R = int(input())

# 100で割った余り
reminder = R%100

# 100から余りを引く
ans = 100 - reminder

# 答えを出力する
print(ans)

B問題

• 日付を経過させて，シミュレーションすれば答えが出る．
• 日数 i が経過したとみなす．
• その時，髪の長さが l+i となり，これが T 以上となった人形の数を変数 count に記録する．
• count が P 以上になった時，その時の日数 i を出力して，関数 exit() でプログラムを終了する．

B.py

"""
<方針>
- 日付を経過させて，シミュレーションすれば答えが出る．
- 日数 `i` が経過したとみなす．
- その時，髪の長さが `l+i` となり，これが `T` 以上となった人形の数を変数 `count` に記録する．
- `count` が `P` 以上になった時，その時の日数 `i` を出力して，関数 `exit()` でプログラムを終了する．
"""
# 標準入力を受け取る．
N, T, P = map(int, input().split())
L = list(map(int, input().split()))

# 経過日数0から始める．
i = 0
while True:
  count = 0
  # 人形の髪の長さを一つずつ取り出す．
  for l in L:
    # 人形の髪の長さがT以上になった時，countを増やす．
    if(l+i>=T):
      count += 1
  
  # 髪の長さがT以上になった人形の数がP以上になった時，
  if(count>=P):
    # 経過日数を出力し，シミュレーションを終了させる．
    print(i)
    exit()
  
  # 日数を経過させる．
  i += 1

C問題

方針

• 文字列を全パターン並び替える．
• 並び替えた文字列 s が K の長さで回文になっていないかを最初の文字からずらしながら調べる．
• 重複したものまで調べると，答えが増えてしまうため，重複をあらかじめ消す必要がある．
• Python の set で重複を消すと，実装の関係で， tle してしまうケースがある．
• 従って， more_itertools.distinct_permutations を使えば，あらかじめ重複の無いものが得られる．

余談

• 頑張って，ワンライナーで答えを作ろうとしたけど，内包表記のオーバーヘッドが大きいせいか， tle してしまう．．． print(sum(1 if all(any(s[i+j] != s[i+K-j-1] for j in range(K//2)) for i in range(N-K+1)) else 0 for s in more_itertools.distinct_permutations(S)))
• もし，内包表記を使ったワンライナーがかける方法をご存知の方いたら，教えてください．．．

C.py

"""
<方針>
- 文字列を全パターン並び替える．
- 並び替えた文字列 `s` が `K` の長さで回文になっていないかを最初の文字からずらしながら調べる．
- 重複したものまで調べると，答えが増えてしまうため，重複をあらかじめ消す必要がある．
- `Python` の `set` で重複を消すと，実装の関係で， `tle` してしまうケースがある．
- 従って， `more_itertools.distinct_permutations` を使えば，あらかじめ重複の無いものが得られる．
<余談>
- 頑張って，ワンライナーで答えを作ろうとしたけど，内包表記のオーバーヘッドが大きいせいか， `tle` してしまう．．． `print(sum(1 if all(any(s[i+j] != s[i+K-j-1] for j in range(K//2)) for i in range(N-K+1)) else 0 for s in more_itertools.distinct_permutations(S)))`
"""
# ライブラリ
import more_itertools

# 標準入力
N, K = map(int, input().split())
S = input()

ans = 0
# 全ての並び替えでループさせる
for s in more_itertools.distinct_permutations(S):
  # 回文が存在しない判定フラグ
  ok = True
  # i~i+Kが回文かどうかの判定
  for i in range(N-K+1):
    permutate = True
    for j in range(K//2):
      if s[i+j] != s[i+K-j-1]:
        permutate = False
    if permutate:
      ok = False
  
  if ok:
    ans += 1
print(ans)

D問題

• N がデカすぎて， O(N) すら許されない．
• となると，効率的な探し方があるはずだ．
• 実は，i 桁の回文数において， i が大きいほど，数字が大きくなるのは当然である．
• 次に，同じ i 桁においての大小判定を考える．
• まず， i が偶数の時は，右半分の数字で大小を見れば十分であることがわかる．
• また， i が奇数の時は， i+1 (偶数) と同じ考え方で大丈夫である．
• つまり， N 番目の回文数は i 桁であることを判定し，そこから差分の数字 right を作成し， right を逆向きにしたものと right を結合すれば良い．
• i 桁の回文数は 9 * pow(10, (i - 1) // 2) 個存在することを考えると，あとは実装するだけである．

D.py

"""
<方針>
- `N` がデカすぎて， `O(N)` すら許されない．
- となると，効率的な探し方があるはずだ．
- 実は，`i` 桁の回文数において， `i` が大きいほど，数字が大きくなるのは当然である．
- 次に，同じ `i` 桁においての大小判定を考える．
- まず， `i` が偶数の時は，右半分の数字で大小を見れば十分であることがわかる．
- また， `i` が奇数の時は， `i+1` (偶数) と同じ考え方で大丈夫である．
- つまり， `N` 番目の回文数は `i` 桁であることを判定し，そこから差分の数字 `right` を作成し， `right` を逆向きにしたものと `right` を結合すれば良い．
- `i` 桁の回文数は `9 * pow(10, (i - 1) // 2)` 個存在することを考えると，あとは実装するだけである．
"""
N = int(input())

# 基準値を調整する．
N -= 2

# 桁数を決定する．
i = 1
while True:
  # i桁に存在する種類
  count = 9 * pow(10, (i - 1) // 2)
  # N番目はi桁の時，
  if N < count:
    break
  # N番目はi桁よりも大きい時，
  else:
    N -= count
    i += 1

# i桁の回文数の右側を作成する．
right = str(10**((i + 1) // 2 - 1) + N)


# 奇数桁か偶数桁かに応じて回文を生成
if i % 2 == 0:
    ans = right + right[::-1]
else:
    ans = right + right[-2::-1]

print(ans)

E問題

• i 年経過した時に，初めて海面以下(浸水するとは限らない)になるところをあらかじめ変数 E 記録しておく．
• 1年ずつ経過させてシミュレーションする．
• では， i 年経過して初めて海面以下になったところについて考える．
• 海面以下になった島の上下左右が浸水していれば，その島も浸水させる．
• 浸水したら，上下左右の島で，海面以下だが，浸水していないところについても同様に浸水するかを考える．
• これを繰り返せば良いが，再帰で実装すると tle になるため，非再帰で頑張って実装しよう or ChatGPT に C++ へトランスパイルしてもらおう．

E.py

"""
<方針>
- `i` 年経過した時に，初めて海面以下(浸水するとは限らない)になるところをあらかじめ変数 `E` 記録しておく．
- 1年ずつ経過させてシミュレーションする．
- では， `i` 年経過して初めて海面以下になったところについて考える．
- 海面以下になった島の上下左右が浸水していれば，その島も浸水させる．
- 浸水したら，上下左右の島で，海面以下だが，浸水していないところについても同様に浸水するかを考える．
- これを繰り返せば良いが，再帰で実装すると `tle` になるため，非再帰で頑張って実装しよう or `ChatGPT` に `C++` へトランスパイルしてもらおう．
"""
# 標準入力
H, W, Y = map(int, input().split())
AA = []
# 初めて海面以下になる島のリスト
E = [[] for i in range(Y+1)]
for i in range(H):
  A = list(map(int, input().split()))
  for j in range(W):
    a = A[j]
    if(a<=Y):
      E[a].append([i, j])
  AA.append(A)

# 海面以下になった場所
under = [[False]*W for i in range(H)]
# 浸水した場所
water = [[False]*W for i in range(H)]
# 現在の島の数
ans = H*W

# シミュレーションする．
for A in E[1:]:
  for I, J in A:
    # 海面以下になった
    under[I][J] = True
    # 浸水するかどうかを探索するスタック
    stack = [(I, J)]
    while stack:
      i, j = stack.pop()
      # 浸水判定をする．
      # 4方が浸水していれば，自分も浸水する．
      sink = False
      for id, jd in [(-1, 0), (1, 0), (0, -1), (0, 1)]:
        y, x = i+id, j+jd
        if (not (0 <= y < H and 0 <= x < W)) or water[y][x]:
          sink = True
          break
      if sink and not water[i][j]:
        # 浸水したとき，
        water[i][j] = True
        # 島の数を減らす．
        ans -= 1
        
        # 他の4方がが海面以下で，浸水してなければ，スタックに追加する．
        for id, jd in [(-1, 0), (1, 0), (0, -1), (0, 1)]:
          y, x = i+id, j+jd
          if 0 <= y < H and 0 <= x < W and under[y][x] and not water[y][x]:
            stack.append((y, x))
  print(ans)

補足

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

• 今回のコンテスト

筆者について

• Atcoderアカウント
• 今回の成績(ooooo--)
• 解説で示したA問題の提出
• 解説で示したB問題の提出
• 解説で示したC問題の提出
• 解説で示したD問題の提出
• 解説で示したE問題の提出

その他

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

最後に一言

• 未来なんか知らなくても覚悟はあった．覚悟ができてないのは俺自身だ．