Submission #654344


Source Code Expand

import java.util.*;

/**
 *
 * @author Jeera
 */
public class Main {

    /**
     * 問題文  http://dwango2015-honsen.contest.atcoder.jp/tasks/dwango2015_finals_4
     */
    
        /**/
        static int coin_max  ;
        static int coin[] ;
        static int value[]  ;
        static int Q_max ;
        static int Q[][]  ;
        /**/
        static int H = 0 ; // head:表 = Niwango
        static int T = 1 ; // tail:裏 = Nikomoba
        static int score_Niwango = 0 ;
        static int score_Nikomoba = 0 ;
        
        static int memo[][] ;

    public static void main(String[] args)  {
        // 
        // データの読み込み for Dowango
        Scanner sc = new Scanner(System.in);
        // 整数の入力
        coin_max = sc.nextInt();

        coin  = new int[coin_max] ;
        value = new int[coin_max] ;
        
        for (int i = 0 ; i < coin_max; i++) {
            value[i] = sc.nextInt();
        }
        
        Q_max = sc.nextInt();
        Q = new int[Q_max][2] ;
        
        for (int i = 0 ; i < Q_max; i++) {
            Q[i][0] = sc.nextInt();
            Q[i][1] = sc.nextInt();
        }
                
        // Original game
        play_onegame() ;
        //   
        
        for (int j=0 ; j < Q_max; j++) {
            int Qi = Q[j][0] - 1; // Qiは、n番目なので補正が必要
            int Di = Q[j][1] ;
//            System.out.printf("Qi= %d, Di= %d \n",Qi+1,Di) ;
            value[Qi] = value[Qi] - Di ;
            //
            play_onegame() ;
            //   
            //value[Qi] = value[Qi] + Di ;  // これが問題として分かりにくい
        }
        
//        System.out.printf("*** END *** \n") ;
        
    }
    static void play_onegame() {
            //
            score_Niwango = 0 ;
            score_Nikomoba = 0 ;
            for (int i = 0 ; i < coin_max ; i++) {
                coin[i] = i % 2 ;
            }
/*            
            memo =  new int[2][coin_max] ;
            for (int k = 0 ; k < coin_max; k++) {
                memo[H][k] = -1 ;
                memo[T][k] = -1 ;                     
            }
*/            
            score_Niwango = search(coin, 0 ) ;
            // 
            System.out.printf("%d\n", score_Niwango) ;
            //System.out.printf("Niwango's score is = %d \n\n", score_Niwango) ;
            //   
        
    }
    
    static int search(int[] coin0, int n ) {
        int Hand ;
        int Aite ;
        int coin1[] = new int[coin_max] ;
        
        Hand = n % 2;
        Aite = (n + 1) % 2;

        if (memo[coin0[n]][n]>0) return memo[coin0[n]][n] ;
        
        System.arraycopy(coin0, 0, coin1, 0, coin_max);
        
        
        int score0, score1, score2 ; // 何もしない、Nを裏返す、N+1を裏返す
        
        if ((n + 2) == coin_max) {
            //  自、他(終) =>  自、自  
            if ((coin1[n] == Hand) & (coin1[n + 1] == Aite)) {
                coin1[n + 1] = Hand;
                if (Hand == H) {
                    return (value[n] + value[n + 1]);
                } else {
                    return 0;
                }
            }
            //  他、自(終) =>  自、自  
            if ((coin1[n] == Aite) & (coin1[n + 1] == Hand)) {
                coin1[n] = Hand;
                if (Hand == H) {
                    return (value[n] + value[n + 1]);
                } else {
                    return 0;
                }
            }
            // 自、自のケースは何もしない
            //  他、他のケース
            if ((coin1[n] == Aite) & (coin1[n + 1] == Aite)) {
                //  他、他(終) => (大きい方) 
                if (value[n] > value[n + 1]) {
                    coin1[n] = Hand;
                    if (Hand == H) {
                        return value[n];
                    } else {
                        return value[n + 1];
                    }
                } else {
                    coin1[n + 1] = Hand;
                    if (Hand == H) {
                        return value[n + 1];
                    } else {
                        return value[n];
                    }
                }
            }
        }
        
        // 何もしない場合 (自、他)
        int score = search(coin1, n+1) ;
        if (coin1[n]==H) score0 = score + value[n] ; else score0 = score ;
        // Nを裏返す場合 (coin[n]==Aite --> Hand)
        if (Hand == H) score1 = score + value[n] ; else score1 = score ;
        // N+1を裏返す場合 (coin[n+1]は常にAite --> Hand)
            coin1[n+1]=Hand;// Nを裏返す
            score2 = search(coin1, n+1) ;
            if (coin1[n] == H) score2 = value[n] + score2 ;
            coin1[n+1]=Aite; // Nを裏返す(元に戻す)
    /**/    
        int max_value  ;
        int min_value  ;
        max_value = max(score0, score1, score2) ;
        min_value = min(score0, score1, score2) ;
/*        
        if (Hand == H) {
            if (memo[H][n]== -1) memo[H][n] = max_value ;
            if (memo[H][n] < max_value) memo[H][n] = max_value ;
        } else {
            if (memo[T][n]== -1) memo[T][n] = min_value ;
            if (memo[T][n] > min_value) memo[T][n] = min_value ;           
        }
*/        
        if (Hand == H) return max_value ;
        else return min_value ;
    
    }
    static int max(int a, int b, int c) {
        if ((a>b) & (a>c)) return a ;
        if ((b>a) & (b>c)) return b ;
        else return c ;
    }
    static int min(int a, int b, int c) {
        if ((a<b) & (a<c)) return a ;
        if ((b<a) & (b<c)) return b ;
        else return c ;
    }
    
}

Submission Info

Submission Time
Task D - コインの取り合い
User Cummin
Language Java (OpenJDK 1.7.0)
Score 0
Code Size 5909 Byte
Status RE
Exec Time 2492 ms
Memory 45496 KB

Judge Result

Set Name Sample Subtask1 Subtask2 Subtask3
Score / Max Score 0 / 0 0 / 10 0 / 80 0 / 90
Status
RE × 2
RE × 7
RE × 14
RE × 33
Set Name Test Cases
Sample sample_01.txt, sample_02.txt
Subtask1 subtask1_01.txt, subtask1_02.txt, subtask1_03.txt, subtask1_04.txt, subtask1_05.txt, subtask1_06.txt, subtask1_07.txt
Subtask2 sample_01.txt, sample_02.txt, subtask2_01.txt, subtask2_02.txt, subtask2_03.txt, subtask2_04.txt, subtask2_05.txt, subtask2_06.txt, subtask2_07.txt, subtask2_08.txt, subtask2_09.txt, subtask2_10.txt, subtask2_11.txt, subtask2_12.txt
Subtask3 subtask1_01.txt, subtask1_02.txt, subtask1_03.txt, subtask1_04.txt, subtask1_05.txt, subtask1_06.txt, subtask1_07.txt, subtask2_01.txt, subtask2_02.txt, subtask2_03.txt, subtask2_04.txt, subtask2_05.txt, subtask2_06.txt, subtask2_07.txt, subtask2_08.txt, subtask2_09.txt, subtask2_10.txt, subtask2_11.txt, subtask2_12.txt, subtask3_01.txt, subtask3_02.txt, subtask3_03.txt, subtask3_04.txt, subtask3_05.txt, subtask3_06.txt, subtask3_07.txt, subtask3_08.txt, subtask3_09.txt, subtask3_10.txt, subtask3_11.txt, subtask3_12.txt, subtask3_13.txt, subtask3_14.txt
Case Name Status Exec Time Memory
sample_01.txt RE 521 ms 23272 KB
sample_02.txt RE 360 ms 23344 KB
subtask1_01.txt RE 364 ms 23456 KB
subtask1_02.txt RE 1014 ms 38780 KB
subtask1_03.txt RE 907 ms 38712 KB
subtask1_04.txt RE 979 ms 38776 KB
subtask1_05.txt RE 1002 ms 38176 KB
subtask1_06.txt RE 876 ms 38948 KB
subtask1_07.txt RE 996 ms 39260 KB
subtask2_01.txt RE 361 ms 23328 KB
subtask2_02.txt RE 1205 ms 44228 KB
subtask2_03.txt RE 880 ms 39068 KB
subtask2_04.txt RE 1308 ms 45360 KB
subtask2_05.txt RE 1343 ms 45352 KB
subtask2_06.txt RE 1173 ms 42324 KB
subtask2_07.txt RE 1326 ms 44816 KB
subtask2_08.txt RE 863 ms 39152 KB
subtask2_09.txt RE 1179 ms 43684 KB
subtask2_10.txt RE 1304 ms 45176 KB
subtask2_11.txt RE 1292 ms 45416 KB
subtask2_12.txt RE 1310 ms 45496 KB
subtask3_01.txt RE 1321 ms 43844 KB
subtask3_02.txt RE 1570 ms 44284 KB
subtask3_03.txt RE 1551 ms 44332 KB
subtask3_04.txt RE 1602 ms 44944 KB
subtask3_05.txt RE 872 ms 38504 KB
subtask3_06.txt RE 2492 ms 44632 KB
subtask3_07.txt RE 1495 ms 43892 KB
subtask3_08.txt RE 1487 ms 44344 KB
subtask3_09.txt RE 1491 ms 44684 KB
subtask3_10.txt RE 1388 ms 45308 KB
subtask3_11.txt RE 1342 ms 44044 KB
subtask3_12.txt RE 1472 ms 44348 KB
subtask3_13.txt RE 1464 ms 44428 KB
subtask3_14.txt RE 1469 ms 44924 KB