結果

問題 No.1481 Rotation ABC
ユーザー gew1fw
提出日時 2025-06-12 20:57:31
言語 PyPy3
(7.3.15)
結果
TLE  
実行時間 -
コード長 2,185 bytes
コンパイル時間 196 ms
コンパイル使用メモリ 81,900 KB
実行使用メモリ 90,248 KB
最終ジャッジ日時 2025-06-12 21:01:03
合計ジャッジ時間 5,277 ms
ジャッジサーバーID
（参考情報） 		judge2 / judge1
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 3
other AC * 10 TLE * 1 -- * 27
権限があれば一括ダウンロードができます

ソースコード

diff # 

import sys
from collections import deque

MOD = 998244353

def main():
    N = int(sys.stdin.readline())
    S = list(sys.stdin.readline().strip())
    
    # We can model each state as a tuple for hashing
    initial = tuple(S)
    visited = set()
    queue = deque()
    
    visited.add(initial)
    queue.append(initial)
    
    count = 0
    
    while queue:
        current = queue.popleft()
        count += 1
        
        # For each possible triplet, check if it's in A,B,C state
        # Consider all possible orderings
        # We need to look for triplets (i,j,k) in any of the three orderings where S_i=A, S_j=B, S_k=C
        # For each such triplet, apply the operation and enqueue the new state if not visited
        for i in range(N):
            for j in range(N):
                for k in range(N):
                    if i == j or j == k or k == i:
                        continue
                    # Check the three orderings
                    valid = False
                    # Check order 1: i < j < k
                    if i < j < k:
                        if current[i] == 'A' and current[j] == 'B' and current[k] == 'C':
                            valid = True
                    # Check order 2: j < k < i
                    elif j < k < i:
                        if current[i] == 'A' and current[j] == 'B' and current[k] == 'C':
                            valid = True
                    # Check order 3: k < i < j
                    elif k < i < j:
                        if current[i] == 'A' and current[j] == 'B' and current[k] == 'C':
                            valid = True
                    if valid:
                        # Create a new state
                        new_state = list(current)
                        new_state[i] = 'B'
                        new_state[j] = 'C'
                        new_state[k] = 'A'
                        new_state_tuple = tuple(new_state)
                        if new_state_tuple not in visited:
                            visited.add(new_state_tuple)
                            queue.append(new_state_tuple)
    
    print(count % MOD)

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