Submission #1059600

Source Code Expand

import java.util.Arrays;
import java.util.Scanner;

/**
 * ARC064_D
 * 
 * http://arc064.contest.atcoder.jp/tasks/arc064_b
 * 
 * @author Cummin
 */
public class Main {

    static StringBuilder S ;   
    static int[] DP ;
    static int total_len ;
    
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        S = new StringBuilder(sc.next());
        total_len = S.length() ;
        DP = new int[S.length()] ; // 初期値=0, 奇数=1, 偶数=2
        
        int [] index= new int[26] ;
        int ptr = 0 ;
        index[S.charAt(0)-'a'] = ptr +1 ;
        ptr ++ ;

        if (solve3(S, index, ptr) == 1) {
            System.out.printf("First\n");
        } else {
            System.out.printf("Second\n");
        }
    }

    static int solve3(StringBuilder s, int[] index, int ptr) {
//        System.out.printf("s=%s, ptr=%d\n", s, ptr) ;
        if (s.length()<3) return 0 ;
        int i ;  // local index
        // 同じ文字が出現するまでスキャン
        for (i= ptr; i< s.length(); i++){
            if (index[s.charAt(i)-'a']==0) {
                index[s.charAt(i)-'a'] =i + 1;
            } else break; 
        }
        // 最終文字までスキャンした ⇒ 終了条件　abc....z
        if (i == s.length()) {
                return s.length()-2 % 2 ;
        }
        // 途中で、過去に出現した文字に出くわした　abc...(a)... または　a..b...(b)...
        if (s.charAt(i)==s.charAt(0)) {  //  abc...(a)....
            // (a)を取らない場合、(a)を残して左右に分割
            int left = (i-2) % 2 ; // i= length([i]-[0])-1
            int right ;
            if ( (s.length()-i) < 3) {
                if (left == 1) return left ; // 勝ちの場合
            }
            if (DP[total_len - (s.length()-i)]!=0) {
//        System.out.printf("DP_use: %d, OE=%d \n", total_len - (s.length()-i),DP[total_len - (s.length()-i)]) ;
                return (DP[total_len - (s.length()-i)] + left) % 2 ;
            }
            StringBuilder right_s = new StringBuilder(s.substring(i, s.length())) ;
            int new_ptr = 0 ;
            int[] new_index = new int[26] ;
            new_index[right_s.charAt(0)-'a'] = new_ptr +1 ;
            new_ptr ++ ;
            right= solve3(right_s, new_index, new_ptr) ;
            DP[total_len - right_s.length()] = 2 - right ;
//        System.out.printf("DP_reg: %d\n", total_len - right_s.length()) ;
            if ((left+right) % 2 == 1) {
                return (left+right) % 2 ;
            }  // 奇数+奇数 または 偶数+偶数は負け。奇数+偶数は勝ち。
                        
        } else {  //  a...b....(b)....
            {
            //  (b)を取らない場合は、(b)を残して左右に分割
                // bを先に取るパターン
                int left =i-1 % 2 ;  
                // bを取らないパターン
                if (left == 0 ){
                int left_left = (index[s.charAt(i)-'a']-1) % 2 ;
                int left_right = (i - index[s.charAt(i) - 'a']) % 2 ;
                left = (left_left + left_right) % 2 ; 
                }
            int right ;
            if ( (s.length()-i) < 3) {
                if (left == 1) return left ; // 勝ちの場合
            }
            if (DP[total_len - (s.length()-i)]!=0) {
//        System.out.printf("DP_use: %d, OE=%d \n", total_len - (s.length()-i),DP[total_len - (s.length()-i)]) ;
                return (DP[total_len - (s.length()-i)] + left) % 2 ;
            }
            StringBuilder right_s = new StringBuilder(s.substring(i, s.length())) ;
            int new_ptr = 0 ;
            int[] new_index = new int[26] ;
            new_index[right_s.charAt(0)-'a'] = new_ptr +1 ;
            new_ptr ++ ;
            right= solve3(right_s, new_index, new_ptr) ;
            DP[total_len - right_s.length()] = 2 - right ;
//        System.out.printf("DP_reg: %d\n", total_len - right_s.length()) ;
            if ((left+right) % 2 == 1) {
                return (left+right) % 2 ;
            }  // 奇数+奇数 または 偶数+偶数は負け。奇数+偶数は勝ち。
}
        }
        // (a) または　(b)を取る場合
        if (i >= s.length() - 1) {
            return 0; // 負けを返す
        }
        if (s.charAt(i - 1) != s.charAt(i + 1)) {
            char del_c = del(s, i);
            int[] new_index = Arrays.copyOf(index, 26);
            if (solve3(s, new_index, i) % 2 == 0) {// returnが偶数 => 自分の手を含めて奇数
                ins(s, i, del_c);
                return 1; // 勝ちを返す
            } else {
                ins(s, i, del_c);
                return 0; // 負けを返す                    
            }
        } else {
            return 0 ; // 負けを返す
        }
    }
    
    static char del(StringBuilder s, int j) {
        char ret = s.charAt(j) ;
        s.deleteCharAt(j) ;
        return ret;
    }

    static void ins(StringBuilder s, int j, char c) {
        s.insert(j, c) ;
    }

}

Submission Info

Submission Time
Task D - An Ordinary Game
User Cummin
Language Java8 (OpenJDK 1.8.0)
Score 0
Code Size 5226 Byte
Status WA
Exec Time 2000 ms
Memory 1009976 KiB

Judge Result

Set Name Sample All
Score / Max Score 0 / 0 0 / 500
Status
AC × 2
WA × 1
AC × 7
WA × 2
MLE × 40
Set Name Test Cases
Sample 0_00.txt, 0_01.txt, 0_02.txt
All 0_00.txt, 0_01.txt, 0_02.txt, 1_00.txt, 1_01.txt, 1_02.txt, 1_03.txt, 1_04.txt, 1_05.txt, 1_06.txt, 1_07.txt, 1_08.txt, 1_09.txt, 1_10.txt, 1_11.txt, 1_12.txt, 1_13.txt, 1_14.txt, 1_15.txt, 1_16.txt, 1_17.txt, 1_18.txt, 1_19.txt, 1_20.txt, 1_21.txt, 1_22.txt, 1_23.txt, 1_24.txt, 1_25.txt, 1_26.txt, 1_27.txt, 1_28.txt, 1_29.txt, 1_30.txt, 1_31.txt, 1_32.txt, 1_33.txt, 1_34.txt, 1_35.txt, 1_36.txt, 1_37.txt, 1_38.txt, 1_39.txt, 1_40.txt, 1_41.txt, 1_42.txt, 1_43.txt, 1_44.txt, 1_45.txt
Case Name Status Exec Time Memory
0_00.txt AC 133 ms 9804 KiB
0_01.txt WA 132 ms 9556 KiB
0_02.txt AC 131 ms 9552 KiB
1_00.txt AC 131 ms 9556 KiB
1_01.txt WA 128 ms 9556 KiB
1_02.txt AC 132 ms 9556 KiB
1_03.txt AC 129 ms 9556 KiB
1_04.txt AC 129 ms 9556 KiB
1_05.txt AC 129 ms 9552 KiB
1_06.txt MLE 1982 ms 984512 KiB
1_07.txt MLE 1917 ms 993548 KiB
1_08.txt MLE 1990 ms 986928 KiB
1_09.txt MLE 1954 ms 1009000 KiB
1_10.txt MLE 1957 ms 985580 KiB
1_11.txt MLE 1891 ms 981556 KiB
1_12.txt MLE 1915 ms 1008752 KiB
1_13.txt MLE 1940 ms 983344 KiB
1_14.txt MLE 1973 ms 982760 KiB
1_15.txt MLE 1942 ms 983784 KiB
1_16.txt MLE 1951 ms 1008164 KiB
1_17.txt MLE 1898 ms 987528 KiB
1_18.txt MLE 1939 ms 985536 KiB
1_19.txt MLE 1890 ms 989936 KiB
1_20.txt MLE 1942 ms 991540 KiB
1_21.txt MLE 1920 ms 987500 KiB
1_22.txt MLE 1941 ms 988740 KiB
1_23.txt MLE 1876 ms 984452 KiB
1_24.txt MLE 1992 ms 1009148 KiB
1_25.txt MLE 1913 ms 988176 KiB
1_26.txt MLE 1895 ms 979020 KiB
1_27.txt MLE 1881 ms 976276 KiB
1_28.txt MLE 1957 ms 1009976 KiB
1_29.txt MLE 1921 ms 993040 KiB
1_30.txt MLE 1888 ms 982688 KiB
1_31.txt MLE 1960 ms 984004 KiB
1_32.txt MLE 1947 ms 994780 KiB
1_33.txt MLE 1882 ms 984192 KiB
1_34.txt MLE 1955 ms 981656 KiB
1_35.txt MLE 1962 ms 983876 KiB
1_36.txt MLE 2000 ms 1009500 KiB
1_37.txt MLE 1935 ms 982984 KiB
1_38.txt MLE 1955 ms 989740 KiB
1_39.txt MLE 1960 ms 983352 KiB
1_40.txt MLE 1899 ms 980688 KiB
1_41.txt MLE 1951 ms 984408 KiB
1_42.txt MLE 1908 ms 979988 KiB
1_43.txt MLE 1907 ms 985280 KiB
1_44.txt MLE 1911 ms 984628 KiB
1_45.txt MLE 1907 ms 984780 KiB