【Python3】十億連勝 (paizaランク S 相当)をやってみた

問題: ゲームの隠し要素を満たす連勝数を数える

入力: N個のステージと各ステージでの試合数A_i、最大連勝数X
出力: X連勝を達成する方法の通り数の下9桁

アプローチ:

1. ステージを順に進み、各試合結果を考慮して連勝数を更新。
2. 特定の連勝数に達する方法を動的計画法(DP)で記録。
3. DP状態は (連勝数, X連勝達成フラグ) の組み合わせ。
4. 最終結果を計算し、9桁に収める。

コード:

def push(dic, key, val):
    """辞書に値を追加または更新するヘルパー関数"""
    if key in dic:
        dic[key] += val
    else:
        dic[key] = val

# 入力を読み込む
N, X = map(int, input().split())
A = [int(input()) for _ in range(N)]
mod = 10 ** 9

# 状態を初期化 (初期状態: 連勝0, X連勝未達成)
states = {}
states[(0, False)] = 1

# 各ステージを順に処理
for i in range(N):
    new_states = {}
    for (wins, cond), comb in states.items():
        if wins + A[i] <= X:
            # ステージiの試合全てに勝つ場合
            push(new_states, (wins + A[i], cond), comb)
            # ステージiの試合中どこかで負ける場合
            push(new_states, (0, cond), comb * A[i])
        else:
            # ちょうどX連勝で負ける場合
            push(new_states, (0, True), comb)
            # X連勝未満で負ける場合
            push(new_states, (0, cond), comb * (X - wins))

    # 組み合わせの数を下9桁に制限
    for key in new_states:
        new_states[key] %= mod

    states = new_states

# 最終的な結果を計算
ans = 0
for (wins, cond), comb in states.items():
    if cond or wins == X:
        ans += comb

# 下9桁の結果を出力
print(ans % mod)

コードの説明:

1. push関数:

   • key (状態) に対応する val (通り数) を辞書 dic に追加または更新。

2. 入力の読み込み:

   • N と X を読み込み、各ステージの試合数 A をリストに格納。

3. 状態の初期化:

   • 初期状態 (連勝数0, X連勝未達成) に対応する通り数を1とする。

4. 各ステージの処理:

   • 各ステージで新しい状態を計算し、連勝数と条件達成フラグを更新。
   • 全勝と途中負けのケースを考慮し、新しい状態と通り数を更新。

5. 結果の計算:

   • 最終的な状態から、X連勝達成または条件達成フラグが真の通り数を合計し、9桁の結果を出力。

このプログラムは、与えられた試合数と連勝条件に対して、隠し要素を満たすプレイの仕方の総数を計算します。