dwangoプログラミングコンテスト

Submission #654416

Source codeソースコード

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( 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

Task問題 D - コインの取り合い
User nameユーザ名 Cummin
Created time投稿日時
Language言語 Java (OpenJDK 1.7.0)
Status状態 TLE
Score得点 0
Source lengthソースコード長 5736 Byte
File nameファイル名
Exec time実行時間 ms
Memory usageメモリ使用量 -

Test case

Set

Set name Score得点 / Max score Cases
Sample - sample_01.txt,sample_02.txt
Subtask1 0 / 10 subtask1_01.txt,subtask1_02.txt,subtask1_03.txt,subtask1_04.txt,subtask1_05.txt,subtask1_06.txt,subtask1_07.txt
Subtask2 0 / 80 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 0 / 90 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

Test case

Case name Status状態 Exec time実行時間 Memory usageメモリ使用量
sample_01.txt AC 367 ms 23604 KB
sample_02.txt AC 376 ms 23668 KB
subtask1_01.txt AC 356 ms 23600 KB
subtask1_02.txt TLE
subtask1_03.txt TLE
subtask1_04.txt TLE
subtask1_05.txt TLE
subtask1_06.txt TLE
subtask1_07.txt TLE
subtask2_01.txt AC 362 ms 23696 KB
subtask2_02.txt TLE
subtask2_03.txt TLE
subtask2_04.txt TLE
subtask2_05.txt TLE
subtask2_06.txt TLE
subtask2_07.txt TLE
subtask2_08.txt TLE
subtask2_09.txt TLE
subtask2_10.txt TLE
subtask2_11.txt TLE
subtask2_12.txt TLE
subtask3_01.txt TLE
subtask3_02.txt TLE
subtask3_03.txt TLE
subtask3_04.txt TLE
subtask3_05.txt TLE
subtask3_06.txt TLE
subtask3_07.txt TLE
subtask3_08.txt TLE
subtask3_09.txt TLE
subtask3_10.txt TLE
subtask3_11.txt TLE
subtask3_12.txt TLE
subtask3_13.txt TLE
subtask3_14.txt TLE