結果

問題 No.3500 01 String
コンテスト
ユーザー Azaki
提出日時 2026-04-18 01:19:46
言語 Python3
(3.14.3 + numpy 2.4.4 + scipy 1.17.1)
コンパイル:
python3 -mpy_compile _filename_
実行:
python3 _filename_
結果
WA  
実行時間 -
コード長 1,708 bytes
記録
記録タグの例:
初AC ショートコード 純ショートコード 純主流ショートコード 最速実行時間
コンパイル時間 375 ms
コンパイル使用メモリ 20,696 KB
実行使用メモリ 15,492 KB
最終ジャッジ日時 2026-04-18 01:20:06
合計ジャッジ時間 7,768 ms
ジャッジサーバーID
（参考情報） 		judge1_0 / judge3_0
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample WA * 3
other WA * 20
権限があれば一括ダウンロードができます

ソースコード

diff #
raw source code 

MOD = 998244353

def count_possible(A: str) -> int:
    N = len(A)
    # dp0: 現在の位置までで、左から1伝播が「開いていない」状態の通り数
    # dp1: 左から1伝播が「開いている」（次位置以降を1にできる）状態の通り数
    dp0, dp1 = 1, 0   # 初期 (i=0 の前)
    
    for i in range(N):
        new_dp0 = 0
        new_dp1 = 0
        c = A[i]
        
        if c == '1':
            # 1の場合
            # 状態0 (伝播なし) から：
            #   - 広げない → 次状態0
            #   - 広げる   → 次状態1
            new_dp0 = (new_dp0 + dp0) % MOD
            new_dp1 = (new_dp1 + dp0) % MOD
            # 状態1 (すでに伝播中) から：
            #   - 必ず1、伝播継続 → 次状態1
            new_dp1 = (new_dp1 + dp1) % MOD
        else:  # c == '0'
            # 0の場合
            # 状態1 (左から1伝播中) から：強制的に1になる、伝播継続
            new_dp1 = (new_dp1 + dp1) % MOD
            # 状態0 (伝播なし) から：
            #   - 右に広げない → 次状態0
            #   - 右に広げる   → 次に0を強制するが、状態としては「次で0固定」だがシンプルに
            # 実際はこのモデルでは0の右伝播は「次の状態に影響を与えない」形で扱う必要調整
            new_dp0 = (new_dp0 + dp0) % MOD   # 広げない場合
            # 広げる場合も、現在の0は変わらず、次位置で0にできるが状態は0のまま（独立）
            new_dp0 = (new_dp0 + dp0) % MOD   # 広げる選択
        
        dp0, dp1 = new_dp0, new_dp1
    
    return (dp0 + dp1) % MOD
0