【競技プログラミング】AtCoder Beginner Contest 363_C問題

問題

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

一覧ページ

解法手順1

与えられた文字列 $ S $ の全ての順列を生成し、その中から「長さ $ K $ の回文を部分文字列として含まないもの」の数を求める問題を解く。

---

解法手順

1. 入力の受け取りと初期処理

n, k = map(int, input().split())
s = input()

• $ n $: 文字列 $ S $ の長さ。
• $ k $: 回文の長さ。
• $ s $: 与えられる文字列。

2. 全ての文字が異なる場合の特別処理

if len(set(s)) == n:
    ans = 1
    for i in range(1, n + 1):
        ans = ans * i
    print(ans)
    exit()

• もし $ S $ の全ての文字が異なる場合（つまり、文字列内に重複がない場合）、全ての順列は異なる。このとき、総順列数は単純に $ n! $（階乗）で求められる。
• この場合、回文を含むかどうかの判定は不要であるため、計算結果を出力して終了する。

3. 全順列の生成

a = set(permutations(s))

• itertools.permutations を用いて、文字列 $ S $ の全ての順列を生成する。
• set を使うことで重複する順列を取り除く。

4. 回文を含む順列のカウント

count = 0

for i in a:
    for j in range(n - k + 1):
        temp_str = i[j:j + k]
        if temp_str == temp_str[::-1]:
            count += 1
            break

• 各順列について、長さ $ K $ の部分文字列（スライス）を全て調べる。
• 部分文字列が回文（逆から読んでも同じ）であれば、その順列は条件に合わないため、カウントする。
• 一度でも回文が見つかった場合、その順列については以降のチェックを省略する（break）。

5. 条件を満たす順列数の計算と出力

print(len(a) - count)

• 全ての順列数（len(a)）から、回文を含む順列数（count）を引くことで、条件を満たす順列数を求める。
• 最終的な結果を出力する。

---

補足説明

回文判定について

• 部分文字列 temp_str が回文かどうかは、Python のスライス機能 [::-1] を使って簡単に判定する。

解法手順2

このプログラムは、与えられた文字列 $S$ の全ての順列を生成し、それらの中から「長さ $K$ の回文を部分文字列として含まないもの」の個数を求める問題を解く。

---

解法手順

1. 入力の受け取りと準備

N, K = map(int, input().split())
S = list(input())

• $N$: 文字列 $S$ の長さ。
• $K$: 回文の長さ。
• $S$: 与えられる文字列をリスト形式に変換（リストにすることで要素の並べ替えが容易になる）。

2. 辞書順で次の順列を生成する関数 next_permutation の実装

def next_permutation(arr) -> bool:
    # 1. 後ろから前に向かって、最初に降順が崩れる位置 (i) を探す
    # 例: arr = [1, 2, 3, 6, 5, 4] の場合、i = 2 (arr[2] = 3)
    i = len(arr) - 2
    while i >= 0 and arr[i] >= arr[i + 1]:
        i -= 1

    # 配列全体が降順の場合（例: [6, 5, 4, 3, 2, 1]）、次の順列は存在しない
    if i == -1:
        return False

    # 2. iより右側で、arr[i] より大きい最小の値を探す位置 (j) を決定
    # この値は、辞書順で次の順列を作るために必要
    j = len(arr) - 1
    while arr[j] <= arr[i]:
        j -= 1

    # 3. arr[i] と arr[j] を交換することで、辞書順で次に進む準備をする
    arr[i], arr[j] = arr[j], arr[i]

    # 4. i+1以降の部分を昇順に並べ替える（これが辞書順で次の最小となる）
    # ソートによって、現在の部分配列を最小化する
    arr[i + 1:] = sorted(arr[i + 1:])

    # 次の順列が生成されたため True を返す
    return True

この関数は、現在の配列 arr を辞書順で次の順列に変換する。

1. 降順部分を探す: 配列の右端から左に向かって、最初に降順が崩れる位置を見つける（i を求める）。
2. 交換対象を探す: i より右側で、arr[i] より大きい最小の値を探し、その位置（j）と交換する。
3. 後半部分を昇順に並べ替える: i+1 以降の要素を昇順にソートする。
4. 次の順列が生成されれば True を返し、最後の順列の場合には False を返す。

---

3. 初期処理：辞書順最小の順列からスタート

S.sort()
ans = 0

• 入力文字列 $S$ をソートして、辞書順最小の状態からスタートする。
• 条件を満たす順列数をカウントする変数 ans を初期化。

---

4. 回文判定と初回チェック

has_palind = False
for head in range(N-K+1):
    palind = True
    for j in range(K // 2):
        if S[head+j] != S[head+K-j-1]:
            palind = False
            break
    if palind:
        has_palind = True
        break

if not has_palind:
    ans += 1

• 現在の順列 $S$ に対して、長さ $K$ の回文が存在するか判定する。
• 部分文字列が回文かどうかは、左右対称な位置にある文字が一致しているか逐一確認する。
• 回文が存在しない場合（has_palind == False）、その順列は条件を満たすため、カウント変数 ans をインクリメント。

---

5. 全ての辞書順順列をチェック

while next_permutation(S):
    has_palind = False
    for head in range(N-K+1):
        palind = True
        for j in range(K // 2):
            if S[head+j] != S[head+K-j-1]:
                palind = False
                break
        if palind:
            has_palind = True
            break

    if not has_palind:
        ans += 1

• next_permutation(S) を用いて次の辞書順順列を生成し、それぞれについて回文判定を行う。
• 各順列について、長さ $K$ の回文が存在しない場合のみカウントする。
• 全ての辞書順順列が処理されるまでループする。

---

6. 結果の出力

print(ans)

条件を満たす全ての順列数（ans）を出力する。

---

解法全体の流れ

1. 入力文字列 $S$
   を辞書順最小にソートして開始する。
2. 辞書順で全ての可能な並び替え（順列）について、長さ $K$ の回文が存在しないか確認する。
3. 条件を満たす場合のみカウントし、最後にその個数を出力する。