Submission #661235

---

Source Code Expand

// package dowango_2015_d_problem;

import java.util.*;

/**
 *
 * @author Jeera
 */
//public class Dowango_2015_D_problem1 {
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(coin_max) ;
        //   
        
        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(Qi) ;
            //   
            //value[Qi] = value[Qi] + Di ;  // これが問題として分かりにくい
        }
        
//        System.out.printf("*** END *** \n") ;
        
    }
    static void play_onegame(int Q) {
            //
            score_Niwango = 0 ;
            score_Nikomoba = 0 ;
            
            if (Q == coin_max) {
                for (int i = 0; i < coin_max; i++) {
                    coin[i] = i % 2;
                }
                memo = new int[2][coin_max];
            }
            for (int k = 0 ; k < Q; k++) {
                memo[H][k] = -1 ;
                memo[T][k] = -1 ;                     
            }
            
            score_Niwango = search( 0 ) ;
            // 
            System.out.printf("%d\n", score_Niwango) ;
            //System.out.printf("Niwango's score is = %d \n\n", score_Niwango) ;
            //   
        
    }
    
    static int search(int n ) {
        int Hand ;
        int Aite ;
       
        Hand = n % 2;
        Aite = (n + 1) % 2;

        if (memo[coin[n]][n]>0) return memo[coin[n]][n] ;

        int score0, score1, score2 ; // 何もしない、Nを裏返す、N+1を裏返す
        
        if ((n + 2) == coin_max) {
            //  自、他(終) =>  自、自　　
            if ((coin[n] == Hand) & (coin[n + 1] == Aite)) {
                // coin[n + 1] = Hand;
                if (Hand == H) {
                    return (value[n] + value[n + 1]);
                } else {
                    return 0;
                }
            }
            //  他、自(終) =>  自、自　　
            if ((coin[n] == Aite) & (coin[n + 1] == Hand)) {
                // coin[n] = Hand;
                if (Hand == H) {
                    return (value[n] + value[n + 1]);
                } else {
                    return 0;
                }
            }
            // 自、自のケースは何もしない
            //  他、他のケース
            if ((coin[n] == Aite) & (coin[n + 1] == Aite)) {
                //  他、他(終) => (大きい方) 
                if (value[n] > value[n + 1]) {
                    // coin[n] = Hand;
                    if (Hand == H) {
                        return value[n];
                    } else {
                        return value[n + 1];
                    }
                } else {
                    // coin[n + 1] = Hand;
                    if (Hand == H) {
                        return value[n + 1];
                    } else {
                        return value[n];
                    }
                }
            }
        }
        
        // 何もしない場合 (自、他)
        int score = search( n+1) ;
        if (coin[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)
            coin[n+1]=Hand;// Nを裏返す
            score2 = search( n+1) ;
            if (coin[n] == H) score2 = value[n] + score2 ;
            coin[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

Judge Result