【Python】AtCoder Beginner Contest 372 【Dまで解説】

「AtCoder Beginner Contest 372」のPythonの解説です。

A – delete . 【AC】

英小文字および . からなる文字列 S が与えられます。
S から . を全て削除した文字列を求めてください。
出典: A – delete .

Python

S = input()

print(S.replace(".",""))

Pythonであれば文字列.replace(対象,置き換え先)でOK。

B – 3^A 【未回答】

正整数 $M$ が与えられます。以下の条件を全て満たす正整数 $N$ と非負整数列 $A = (A_{1}, A_{2}, \dots, A_{N})$ を一つ求めてください。

$1 \leq N \leq 20$

$0 \leq A_{i} \leq 10$ $(1 \leq i \leq N)$

$\sum_{i = 1}^{N} 3^{A_{i}} = M$

ただし、制約下では条件を満たす $N$ と $A$ の組が必ず存在することが証明できます。
出典: B – 3^A

※下記の解答は提出 #58657909を参照しています。

Python

import math
def main():
    M = int(input())
    N = 0
    ans=[]
    while True:
        if M >= 3:
            num = int(math.log(M,3)) # 3を底としたMの対数。int()で小数点以下を切り捨てることで、3の個数となる
            ans.append(num) # 3の個数がそのまま答えになる
            M -= pow(3,num) # {3**個数}をMから引く
            N += 1 
        elif M>0:
            ans.append(0) # Mが3以下の場合は 1 = 3**0 が答えになる
            M-=1
            N += 1
        else: # Mが0になるまで繰り返す
            break
    print(N)
    for a in ans:
        print(a,end=" ") # end = " "は出力した値の直後に半角空白を追加する。何も指定しなければ値の後に改行コードが出力されるため、縦に数値が並んでしまう

if __name__ == "__main__": # importでは実行しない
    main()

この問題は、「3」の個数と「3」以下の個数を求める問題。
例題の答えが2 0 2 4など順序がばらばらになっているため紛らわしいが、そこを超えると理解しやすくなる。

C – Count ABC Again 【TLE】

長さ $N$ の文字列 $S$ が与えられます。クエリが $Q$ 個与えられるので、順番に処理してください。

$i$ 番目のクエリは以下の通りです。

整数 $X_{i}$ と文字 $C_{i}$ が与えられるので、 $S$ の $X_{i}$ 番目の文字を $C_{i}$ に置き換える。その後、 $S$ に文字列 ABC が部分文字列として何箇所含まれるかを出力する。

ここで、 $S$ の 部分文字列 とは、 $S$ の先頭から $0$ 文字以上、末尾から $0$ 文字以上削除して得られる文字列のことをいいます。
例えば、ab は abc の部分文字列ですが、ac は abc の部分文字列ではありません。
出典: C – Count ABC Again

※下記の解答は提出 #587 6 5832を参照しています。

Python

N, Q = list(map(int, input().split()))
S = list(input())
X = []
C = []
for i in range(Q):
    x,c = input().split()
    x = int(x)
    X.append(x)
    C.append(c)

# 文字列Sに"ABC"が何箇所含まれているか？
cnt = 0
for i in range(1,N-1):
    if S[i-1:i+2] == ["A","B","C"]:
        cnt += 1

# i番目のクエリを実行
for i in range(Q):
    # 入れ替える文字を含む文字列に"ABC"が含まれる場合、カウントを減らす
    if X[i] - 3 >= 0 and S[X[i]-3:X[i]] == ["A","B","C"] or X[i] - 2 >= 0 and S[X[i]-2:X[i]+1] == ["A","B","C"] or X[i] - 1 >= 0 and S[X[i]-1:X[i]+2] == ["A","B","C"]:
        cnt -= 1
    
    # 指定位置の文字を、与えられた文字で置き換える
    S[X[i]-1] = C[i]
    
    # もし置き換えた上で"ABC"のままならば、減らしたカウントを元に戻す
    if S[X[i]-3:X[i]] == ["A","B","C"] or S[X[i]-2:X[i]+1] == ["A","B","C"] or S[X[i]-1:X[i]+2] == ["A","B","C"]:
        cnt += 1
    
    # 一連の処理後にSに"ABC"が何個含まれているかを出力する
    print(cnt)

この問題は、与えられた文字列に対して文字の置換を行い、その都度文字列に部分文字列 “ABC” が何箇所含まれるかを求めるという問題です。問題文で指示されている処理を素直にコードで実装することが求められています。

問題を解くためには、以下の手順が必要です。

初期状態の文字列に部分文字列 “ABC” が何箇所含まれるかを数える。
各クエリに対して、以下の処理を行う。
- 文字の置換によって部分文字列 “ABC” が消えるかどうかを判定し、消える場合は数を1減らす。
- 指定された位置の文字を置換する。
- 文字の置換によって新たに部分文字列 “ABC” が出現するかどうかを判定し、出現する場合は数を1増やす。
- 現在の部分文字列 “ABC” の出現回数を出力する。

この問題の難しさは、文字列のスライス（部分文字列）を扱うことに慣れていないと、コードを書いている内にパニックになりがちな点にあります。文字列のスライスを使って、特定の位置を中心とした部分文字列を取得し、条件判定を行う必要があるからです。

しかし、問題文で求められている処理を忠実にコードで表現することができれば、問題を解くことができます。文字列のスライスについて理解を深め、与えられた条件に基づいて適切に処理を行うことがポイントとなります。

D – Buildings 【未回答】

ビル $1$ , ビル $2$ , $\dots$ , ビル $N$ の $N$ 棟のビルがこの順で一列に並んでいます。ビル $i (1 \leq i \leq N)$ の高さは $H_{i}$ です。

各 $i = 1, 2, \dots, N$ について、次を満たす整数 $j (i < j \leq N)$ の個数を求めてください。

ビル $i$ とビル $j$ の間にビル $j$ より高いビルが存在しない。

出典: D – Buildings

※下記の解答はD – Buildings 解説 by toamを参照しています。

Python

N = int(input()) # ビルの数
H = list(map(int, input().split())) # 各ビルの高さ


table = [0] * N # 各ビルから見える右側のビルの数
stc = [] # スタック。見えるビルのインデックスを保持する

for i in range(N-2, -1, -1): # 後ろより2番目のビルから左に向かって走査(N-2から始まり0で終了する)。
    while stc and not H[i + 1] <= H[stc[-1]] :
        # "stc"は、スタックが空でないことを確認するための条件。スタック stc が空でない限り、以下の処理を繰り返す。
        # not H[i + 1] <= H[stc[-1]]  は、「現在のビル（H[i+1]）が右隣のビル（H[stc[-1]]）より低くない時」という意味。スタックは一番奥が前回のインデックスなので、現在ビルの右隣となる。
        # つまり、現在のビルが右隣のビルより高い時に、右隣のビルを削除する
        stc.pop() # pop()は末尾だけ、つまり右隣のビルのインデックス削除する。これを繰り返し、現在のビルより高いビルが現れるまでスタックを削除し続ける
    stc.append(i + 1) # 現在のビルのインデックスを追記する
    table[i] = len(stc) # table配列の右側からスタックの数を追記していく。スタックをappendで追加してからlenを追記するので、最小値は1となる。一方、最後尾だけはiが後ろより2番目からなのでi+1が上書きされず、必ずゼロとなる。
print(*table)

この問題は、各ビルから見て右側の高いビルの数を求める問題です。

問題を解くためのポイントは、以下の2点です。

ビルを右から左に向かって処理することで、各ビルから右側に見える隣のビルを求めることができる。
単調スタック（monotonic stack）と呼ばれるデータ構造を使用することで、各ビルについて右隣の「高い」ビルを高速に求めることができます。

具体的には、以下のようなアルゴリズムを使用します。

アルゴリズム

ステップ1
ビルの高さを保持する配列 H と、結果を格納する配列 table を用意します。tableはNの数だけゼロを詰めます。
ステップ2
ビルのインデックスを保持するスタック stc を初期化します。
ステップ3
ビルを右から左に向かって走査します。各ビルについて以下の処理を行います。
1. スタックの先頭要素に対応するビル（右隣のビル）の高さが、現在のビルの高さより低ければ、スタックから要素を取り除きます。
2. 高いビルが出るまで繰り返します。
3. 現在のビルのインデックスをスタックの先頭（stc配列の末尾）に追加します。
4. スタックの長さを table の対応する位置に格納します。これが、現在のビルから見える右側のビルの数になります。
ステップ4
最後に、table の内容を出力します。

このアルゴリズムの時間計算量は $O (N)$ です。各ビルについて、スタックへの追加と削除が最大で1回ずつ行われるため、全体では $O (N)$ の操作となります。

この問題の難しさは、逆側から考えてさらにスタックを使うところです。一見すると、各ビルから右側を順に見ていく単純な方法が思い浮かびますが、それでは計算量が大きくなってしまいます。

代わりに、右側から左側へと処理を進めることで、効率的に解を求めることができます。この逆向きの発想は、直感的ではないため難しく感じる部分です。

さらに、単調スタックという特殊なデータ構造を使用することで、ビルを高速判定できます。単調スタックとは、スタックの要素が常に単調増加または単調減少になるスタック^[1]です。単調スタックにすることで、右側の高いビルの情報だけが保持され不要なビルの情報は自動的に取り除かれます。

この「逆から考える」という発想と「単調スタック」という効率的なデータ構造の組み合わせが、この問題の解法の核心であり、同時に難しさの源でもあります。

E – K-th Largest Connected Components 【未回答】

※作成中ですのしばらくお待ち下さい

F – 【未回答】

※作成中ですのしばらくお待ち下さい

G – 【未回答】

※作成中ですのしばらくお待ち下さい

まとめ

この記事では、「AtCoder Beginner Contest 372」のA問題からD問題までをPythonで解説しました。

A問題は文字列操作の基本、B問題は3の冪乗の和の表現、C問題は文字列の部分文字列の数え上げ、D問題はUnion-Findデータ構造を用いたグラフ問題を扱いました。

各問題は、基本的なプログラミングスキルから効率的なアルゴリズムの実装まで幅広い能力を試す内容で、全体を通してデータ構造とアルゴリズムの理解と応用が重要な問題セットでした。

Monotonic Stack の解説と応用例 #Python – Qiita ↩︎

スポンサーリンク

A – delete . 【AC】

B – 3^A 【未回答】

C – Count ABC Again 【TLE】

D – Buildings 【未回答】

E – K-th Largest Connected Components 【未回答】

F – 【未回答】

G – 【未回答】

まとめ