結果

問題 No.2490 Escalator
ユーザー Sillpherth
提出日時 2025-04-21 17:04:54
言語 Java
(openjdk 23)
結果
TLE  
実行時間 -
コード長 2,458 bytes
コンパイル時間 3,999 ms
コンパイル使用メモリ 82,644 KB
実行使用メモリ 60,172 KB
最終ジャッジ日時 2025-04-21 17:05:14
合計ジャッジ時間 19,006 ms
ジャッジサーバーID
（参考情報） 		judge1 / judge5
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 3
other AC * 31 TLE * 1 -- * 41
権限があれば一括ダウンロードができます

ソースコード

diff # 

import java.util.*;

public class SymmetryCheckerWithWildcard {

    static final int WILDCARD = -1;

    // LPS構築：ワイルドカードにも対応
    static int[] buildLPS(int[] pattern, int start, int m)
    {
        int[] lps = new int[m];
        int len = 0;
        for (int i = 1; i < m; ) {
            if (match(pattern[i+start], pattern[len+start])) {
                lps[i++] = ++len;
            } else if (len > 0) {
                len = lps[len - 1];
            } else {
                i++;
            }
        }
        return lps;
    }

    // 一致判定（ワイルドカード対応）
    static boolean match(int a, int b) {
        return a == b || a == WILDCARD || b == WILDCARD;
    }
    

    // KMP検索：revA in A+A を探す（ワイルドカード対応）
    static boolean existsCentrallySymmetricRotation(int[] AA, int[] revA, int start) {
        int N = revA.length/4+1;

        int[] lps = buildLPS(revA, start, N);
        int j = 0; int i = 0;
        while (i < AA.length) {
            if (match(AA[i], revA[j+start])) {
                i++; j++;
            } else if (j > 0) {
                j = lps[j - 1];
            } else {
                i++;
            }

            if (j == N) {
                int pos = i - j;
                //System.out.println(pos);
                if (pos >= 0 && pos <= (AA.length - N)) {
                    return true;
                }
                j = lps[j - 1];
            }
        }

        return false;
    }

    // テスト
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int len = 2 * sc.nextInt(); // 長さ 2N
        int[] A = new int[len];
        for (int i = 0; i < len; i++) {
            A[i] = sc.nextInt();
        }
        int[] revA = new int[len];
        for (int i = 0; i < len; i++) {
            revA[i] = A[len - 1 - i];
        }

        int[] AA = new int[2 * len];
        int[] revAA = new int[2 * len];
        for (int i = 0; i < len; i++) {
            AA[i] = A[i];
            AA[i + len] = A[i];
            revAA[i] = revA[i];
            revAA[i + len] = revA[i];
        }
        

        for(int i=0; i<len; i++)
        {
        	//System.out.println(i);
        	if(existsCentrallySymmetricRotation(AA, revAA, i))
        	{
        		System.out.println("Yes");
        		System.exit(0);
        	}
        }
        System.out.println("No");
    }
}
0