Submission #654273

---

Source Code Expand

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;

/**
 *
 * @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) throws IOException {
        // 
        // データの読み込み
        String str = "";
        BufferedReader r = new BufferedReader(new InputStreamReader(System.in));
        
        str = r.readLine() ; //入力した文字列をstrに代入
        if (str == null) return; // ideoneの入力エラー対策
        if (str.length() <= 0)  return;
        
        String str1[] = str.split(" ");
        coin_max = Integer.parseInt(str1[0]);
        
        coin  = new int[coin_max] ;
        value = new int[coin_max] ;
        Q = new int[2][coin_max] ;
        
        str = r.readLine(); //入力した文字列をstrに代入
        if (str == null) return; // ideoneの入力エラー対策
        if (str.length() <= 0)  return;
        str1 = str.split(" ");
        for (int i = 0 ; i < coin_max; i++) {
            value[i] = Integer.parseInt(str1[i]) ;
        }
        
        str = r.readLine(); //入力した文字列をstrに代入
        if (str == null) return; // ideoneの入力エラー対策
        if (str.length() <= 0)  return;
        str1 = str.split(" ");
        Q_max = Integer.parseInt(str1[0]);
        
        for (int i = 0 ; i < coin_max; i++) {
            str = r.readLine(); //入力した文字列をstrに代入
            if (str == null) return; // ideoneの入力エラー対策
            if (str.length() <= 0)  return;
            str1 = str.split(" ");
            Q[i][0] = Integer.parseInt(str1[0]);
            Q[i][1] = Integer.parseInt(str1[1]) ;
        }
                
        // 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

Judge Result