[ABC379] ABC 379(Atcoder Beginner Contest)のA~D(A,B,C,D)問題をPythonで解説(復習)
A問題
- 入力を
list(input())で受け取ることで，桁数毎のlistで受け取れる． -
joinメソッドを使うことで，listを連結して出力できるので，それを使う．
A.py
"""
<方針>
- 入力を `list(input())` で受け取ることで，桁数毎の `list` で受け取れる．
- `join` メソッドを使うことで， `list` を連結して出力できるので，それを使う．
"""
N = list(input())
a, b, c = N
print("".join([b, c, a]), "".join([c, a, b]))
B問題
- 左の歯から順番に🍓を食べさせよう！！
- 高橋くんの🦷
Sをlistで管理する． - 長さ
Kの 良い🦷good_teethと悪い🦷bad_teethを準備する． - 🍓を食べさせるときは，🦷が良いか確認して，食べさせた後はちゃんと悪くさせよう！！
B.py
"""
<方針>
- 左の歯から順番に🍓を食べさせよう！！
- 高橋くんの🦷 `S` を `list` で管理する．
- 長さ `K` の 良い🦷 `good_teeth` と悪い🦷 `bad_teeth` を準備する．
- 🍓を食べさせるときは，🦷が良いか確認して，食べさせた後はちゃんと悪くさせよう！！
"""
# 入力
N, K = map(int, input().split())
S = list(input())
# 良い🦷
good_teeth = ["O"]*K
# 悪い🦷
bad_teeth = ["X"]*K
# 何回🍓を食べられるか
ans = 0
# 左から順番に見ていく．
for i in range(N-K+1):
# 🦷が良いとき
if S[i:i+K] == good_teeth:
# 🍓を食べさせる
ans += 1
# 🦷を悪くする．
S[i:i+K] = bad_teeth
# 出力
print(ans)
C問題
方針
-
Nがとんでもなくでかいので，O(N)すら許されない．つまり，Nのfor文は使えない． - だが，
O(M)は許されそうなので，Mのfor文での解決を試みる． - 「石が置かれている位置を左から順番に見る作業」に加えて，「横に置いていく作業」を行えば
O(M)で行けそう． - 「石が置かれている位置を左から順番に見る作業」は普通に
for文でシミュレーションすれば良い．計算量はO(M)である． - 注意しなければならないのが，「横に石を置いていく作業」であり，これもシミュレーションしてしまうと，
O(N)がさらにかかってしまう． - 「横に石を置いていく作業」は，「各マスに一個ずつ石を置く作業」と「手持ちの余った石を次に石が置いてある場所に全部移動する作業」に分割できる．
- これらの作業を
O(1)で計算で頑張って求めれば良い． - 前準備として，移動した回数
ansと 手持ちの石rockをグローバルに持たせる．また，全体のマスの左右に番兵[[-1,1]][[N,1]]を付け加えるとやりやすい． - 石を置いていく途中で手持ちの石
rockが負になったり，最後に手持ちの石rockが正になったら-1を出力する． - ちなみに，最初に石を左から順番に
sortするのにO(MlogM)かかるのがボトルネックだが，十分実行時間に間に合う．
前提
-
C問題あたりで，TLEになる人は，制約条件を見る癖をつけよう． -
AとB問題では，基本的に制約条件を見ずにやっても解ける． - しかし，
C問題以降では，制約条件を見ないと必ずTLEすると思っても良い． - 詳しい話は私の352回の記事 の
C問題の解説に記したので，是非参照してほしい．
C.py
"""
<方針>
- `N` がとんでもなくでかいので， `O(N)` すら許されない．つまり， `N` の `for` 文は使えない．
- だが，`O(M)` は許されそうなので，`M` の `for` 文での解決を試みる．
- 「石が置かれている位置を左から順番に見る作業」に加えて，「横に置いていく作業」を行えば `O(M)` で行けそう．
- 「石が置かれている位置を左から順番に見る作業」は普通に `for` 文でシミュレーションすれば良い．計算量は `O(M)` である．
- 注意しなければならないのが，「横に石を置いていく作業」であり，これもシミュレーションしてしまうと， `O(N)` がさらにかかってしまう．
- 「横に石を置いていく作業」は，「各マスに一個ずつ石を置く作業」と「手持ちの余った石を次に石が置いてある場所に全部移動する作業」に分割できる．
- これらの作業を `O(1)` で計算で頑張って求めれば良い．
- 前準備として，移動した回数 `ans` と 手持ちの石 `rock` をグローバルに持たせる．また，全体のマスの左右に番兵 `[[-1,1]]` `[[N,1]]` を付け加えるとやりやすい．
- 石を置いていく途中で手持ちの石 `rock` が負になったり，最後に手持ちの石 `rock` が正になったら `-1` を出力する．
- ちなみに，最初に石を左から順番に `sort` するのに `O(MlogM)` かかるのがボトルネックだが，十分実行時間に間に合う．
"""
# 入力
N, M = map(int, input().split())
X = list(map(int, input().split()))
A = list(map(int, input().split()))
# 0-indexedにする．
X = [x-1 for x in X]
# 石の位置と個数をセットで管理する．
XA = [[x, a] for x, a, in zip(X, A)]
# 左から順番にする．
XA.sort()
# 左右に番兵をつける．
XA =[[-1,1]]+XA+[[N, 1]]
rock = 0 # 現在手持ちの石の数
ans = 0 # 移動回数
# シミュレーション
for i in range(M+1):
# 石が置かれているマス, 石が置かれている個数
x, a = XA[i]
# 次に石が置かれているマス
nextX = XA[i+1][0]
# 手持ちの石の数を増やす
rock += a
# 石が置かれているマスに一つ石を置き去りにする．
rock -= 1
# 次の石が置かれているマスとの間に置かなければならない石の個数
d = nextX - x - 1
# その分の石を，手持ちの石の数から減らす．
rock -= d
# もし，手持ちの石が負になってしまったら(間に石が置けなかったことを意味する．)-1を出力する．
if rock<0:
print(-1)
exit()
# 「各マスに一個ずつ石を置く作業」
ans += d*(d+1)//2
# 「手持ちの余った石を次に石が置いてある場所に全部移動する作業」
ans += rock*(d+1)
# 最後まで手持ちの石が正だったら(石が超過していることを指す)，-1を出力する．
if(rock>0):
print(-1)
exit()
# 出力
print(ans)
D問題
- シミュレーションはしない．
- 木を収穫するのは最後に回す．
- いもす法を使って，木の高さを構築する．
- 後回しにした分，収穫したかった木の高さ
Hを経過したTだけ増やせば問題無い(未来に植えた木は切れないのでOK)． - 木の高さが降順なので，二分探索をする．
- 既に収穫した木は，新しく収穫できないことに注意する．
D.py
"""
<方針>
- シミュレーションはしない．
- 木を収穫するのは最後に回す．
- いもす法を使って，木の高さを構築する．
- 後回しにした分，収穫したかった木の高さ `H` を経過した `T` だけ増やせば問題無い(未来に植えた木は切れないのでOK)．
- 木の高さが降順なので，二分探索をする．
- 既に収穫した木は，新しく収穫できないことに注意する．
"""
Q = int(input())
# 木を収穫するとき状況を保存するリスト
whenT = []
# 植物の高さを管理するリスト
plant = []
# 収穫したい木の高さのリスト
H = []
# 入力
for _ in range(Q):
query = list(map(int, input().split()))
match query:
case [1]:
# シミュレーションは後回し．木を植えるだけ．
plant.append(0)
case [2, t]:
# [経過させたい日数, 現在の植木鉢の数(収穫は想定しない), 既に収穫したい回数]
whenT.append([t, len(plant), len(H)])
case [3, h]:
# 収穫したい木の高さ
H.append(h)
# いもす法のための番兵
plant.append(0)
# いもす法のための番兵
H.append(0)
# Hのいもす法は別リストを作成する必要がある．
accH = [0]*len(H)
# いもす法のフラグを埋め込む
for t, p, h in whenT:
# 植物
plant[0] += t
plant[p] -= t
# 収穫
accH[0] += t
accH[h] -= t
# いもす法の累積和
for i in range(len(plant)-1):
plant[i+1] += plant[i]
# いもす法の累積和
for i in range(len(H)-1):
accH[i+1] += accH[i]
# いもす法をした内容を元の収穫したい木の高さに加える．
for i in range(len(H)):
H[i] += accH[i]
# 既に収穫した木の最大index
cut = -1
# 収穫を行う
for h in H[:-1]:
# めぐる式二分探索
ok = -1
ng = len(plant)
while abs(ok-ng)>1:
mid = (ok+ng)//2
if plant[mid] >= h:
ok = mid
else:
ng = mid
# 収穫した木の本数を出力
print(max(ok-cut, 0))
# 収穫した木の最大indexを更新
cut = max(cut, ok)
補足
関係するリンク(参考文献など)
筆者について
- Atcoderアカウント
- 今回も不参加のため，成績なし．
- 解説で示したA問題の提出
- 解説で示したB問題の提出
- 解説で示したC問題の提出
- 解説で示したD問題の提出
その他
- 間違いを含んでいる可能性があります．
- 方針と言いつつ，方針ではない感想などを書いている可能性があります．
- A問題から解説がだんだん省略されます．
- コードに書かれている解説の文言と，その上に書いてある解説の文言を変えている場合があります．
最後に一言
- ちゅ．理解力が低くてごめん．