【競技プログラミング】AtCoder Beginner Contest 229_D問題

問題

要約

1. 変数

   • S: 'X' と '.' からなる文字列
   • K: 操作の最大回数

2. 操作

   • '.' を 'X' に置き換える
   • この操作は0回以上K回以下行うことができる

3. 目的
   操作後に、連続する 'X' の最大数を求める

4. 制約

   • 操作回数は0回以上K回以下

既存投稿一覧ページへのリンク

一覧ページ

アプローチ

尺取法を用いて最適な連続する'X'の長さを求める

解法手順

1. 入力文字列Sと最大操作回数Kを受け取る。

2. 文字列の長さnを取得する。

3. 二つのポインタiとjを用意し、iは現在のウィンドウの開始位置、jは終了位置を示す。

4. 変数cを用意し、現在のウィンドウ内で'.'から'X'に変換した数を記録する。

5. 変数ansを用意し、最大の連続する'X'の長さを記録する。

6. iを0からn-1まで移動させ、以下の操作を行う：
   a. jがn未満で、かつcに(S[j]が'.'である場合の1)を加えてもK以下である間、jを進める。
   b. jを進めるたびに、S[j]が'.'ならcをインクリメントする。
   c. 現在のウィンドウの長さ(j-i)とansを比較し、大きい方をansに格納する。
   d. iを進める前に、S[i]が'.'ならcをデクリメントする。

7. 最終的なansを出力する。

ACコード

ac.py

def io_func():
    # 入力文字列Sを受け取る
    S = input()
    # 最大操作回数Kを整数として受け取る
    K = int(input())
    return S, K

def solve(S, K):
    # 文字列の長さを取得
    n = len(S)
    # jは現在のウィンドウの終了位置
    j = 0
    # cは現在のウィンドウ内で'.'から'X'に変換した数
    c = 0
    # ansは最大の連続する'X'の長さ
    ans = 0
    
    # iを0からn-1まで移動させる
    for i in range(n):
        # jがn未満で、かつcに(S[j]が'.'である場合の1)を加えてもK以下である間、jを進める
        while j < n and c + (S[j] == '.') <= K:
            # S[j]が'.'ならcをインクリメント
            c += (S[j] == '.')
            j += 1
        # 現在のウィンドウの長さ(j-i)とansを比較し、大きい方をansに格納
        ans = max(ans, j - i)
        # iを進める前に、S[i]が'.'ならcをデクリメント
        c -= (S[i] == '.')
    
    # 最終的なansを返す
    return ans

def main():
    # 入力を受け取る
    S, K = io_func()
    # 解を求める
    result = solve(S, K)
    # 結果を出力
    print(result)

if __name__ == '__main__':
    main()

###
# S: 入力文字列
# K: 最大操作回数
# n: 文字列Sの長さ
# j: 現在のウィンドウの終了位置
# c: 現在のウィンドウ内で'.'から'X'に変換した数
# ans: 最大の連続する'X'の長さ
# i: 現在のウィンドウの開始位置

# 1. io_func関数:
#    - 標準入力から文字列Sと整数Kを読み取る
#    - SとKを返す

# 2. solve関数:
#    - 引数としてSとKを受け取る
#    - 尺取法を用いて最適な連続する'X'の長さを求める
#    - 最大の連続する'X'の長さを返す

# 3. main関数:
#    - io_func関数を呼び出して入力を受け取る
#    - solve関数を呼び出して解を求める
#    - 結果を出力する

# 4. プログラムのエントリーポイント:
#    - main関数を呼び出す

思考過程

連続する'X'の最大長を効率的に求める。
尺取法を使用することで、文字列を一度だけ走査しながら最適解を見つけることができる。
ウィンドウを拡大しながら'.'を'X'に変換し、Kを超えたら縮小するという方法で探索する。

計算量の概算

O(n)