結果

問題 No.1909 Detect from Substrings
ユーザー gew1fw
提出日時 2025-06-12 19:53:54
言語 PyPy3
(7.3.15)
結果
TLE  
実行時間 -
コード長 2,082 bytes
コンパイル時間 165 ms
コンパイル使用メモリ 82,044 KB
実行使用メモリ 77,476 KB
最終ジャッジ日時 2025-06-12 19:54:57
合計ジャッジ時間 4,453 ms
ジャッジサーバーID
（参考情報） 		judge1 / judge3
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 3
other AC * 5 TLE * 1 -- * 30
権限があれば一括ダウンロードができます

ソースコード

diff # 

import sys
from collections import defaultdict

def main():
    N, M = map(int, sys.stdin.readline().split())
    S = [sys.stdin.readline().strip() for _ in range(N)]

    # Check each position k (0-based) for the characters in all S_i
    C = []
    possible = True
    for k in range(M):
        chars = set()
        for s in S:
            chars.add(s[k])
        if len(chars) >= 3:
            possible = False
        C.append(chars)
    if not possible:
        print(0)
        return

    # Preprocess each position's type and possible characters
    types = []
    for k in range(M):
        chars = C[k]
        if len(chars) == 1:
            types.append((1, list(chars)[0]))
        else:
            sorted_chars = sorted(chars)
            types.append((2, sorted_chars[0], sorted_chars[1]))

    # Initialize DP for the first step (k=0 in 0-based, which is position 1 in T)
    dp = defaultdict(int)
    first_type = types[0]
    if first_type[0] == 1:
        x = first_type[1]
        for d in 'abcdefghijklmnopqrstuvwxyz':
            if d == x:
                dp[d] += 26
            else:
                dp[d] += 1
    else:
        y, z = first_type[1], first_type[2]
        dp[z] += 1
        dp[y] += 1

    # Process remaining positions (k=1 to M-1 in 0-based)
    for k in range(1, M):
        current_type = types[k]
        new_dp = defaultdict(int)
        if current_type[0] == 1:
            x = current_type[1]
            for c in dp:
                cnt = dp[c]
                if c == x:
                    for d in 'abcdefghijklmnopqrstuvwxyz':
                        new_dp[d] += cnt
                else:
                    new_dp[x] += cnt
        else:
            y, z = current_type[1], current_type[2]
            for c in dp:
                cnt = dp[c]
                if c == y:
                    new_dp[z] += cnt
                elif c == z:
                    new_dp[y] += cnt
        dp = new_dp
        if not dp:
            print(0)
            return

    print(sum(dp.values()))

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