結果

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

ソースコード

diff #
raw source code 

import sys

def solve():
    # Read input
    try:
        line1 = sys.stdin.readline()
        if not line1:
            return
        n = int(line1.strip())
        a = sys.stdin.readline().strip()
    except ValueError:
        return

    # Store original positions of 0s and 1s
    pos0 = [i for i, char in enumerate(a) if char == '0']
    pos1 = [i for i, char in enumerate(a) if char == '1']
    
    count0 = len(pos0)
    count1 = len(pos1)
    
    MOD = 998244353
    
    # dp[i][j] = number of ways to pick i zeros and j ones
    # to fill the first (i+j) positions of the result string.
    dp = [[0] * (count1 + 1) for _ in range(count0 + 1)]
    dp[0][0] = 1
    
    for i in range(count0 + 1):
        for j in range(count1 + 1):
            if dp[i][j] == 0:
                continue
            
            # current_idx is the position in the new string we are filling
            current_idx = i + j
            
            # Try placing a '0' next
            if i < count0:
                # Rule: Ai = 0 and i < N, then Ai+1 = 0
                # A 0 can stay at its index or move RIGHT.
                # So original index must be <= target index.
                if pos0[i] <= current_idx:
                    dp[i+1][j] = (dp[i+1][j] + dp[i][j]) % MOD
            
            # Try placing a '1' next
            if j < count1:
                # Rule: Ai = 1 and i > 1, then Ai-1 = 1
                # A 1 can stay at its index or move LEFT.
                # So original index must be >= target index.
                if pos1[j] >= current_idx:
                    dp[i][j+1] = (dp[i][j+1] + dp[i][j]) % MOD
                    
    print(dp[count0][count1])

if __name__ == "__main__":
    solve()
0