Submission #654416
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( 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
Submission Time | |
---|---|
Task | D - コインの取り合い |
User | Cummin |
Language | Java (OpenJDK 1.7.0) |
Score | 0 |
Code Size | 5736 Byte |
Status | TLE |
Exec Time | 3067 ms |
Memory | 63984 KB |
Judge Result
Set Name | Sample | Subtask1 | Subtask2 | Subtask3 | ||||||||||||||
---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|
Score / Max Score | 0 / 0 | 0 / 10 | 0 / 80 | 0 / 90 | ||||||||||||||
Status |
|
|
|
|
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 | 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 | 3051 ms | 57780 KB |
subtask1_03.txt | TLE | 3052 ms | 53432 KB |
subtask1_04.txt | TLE | 3051 ms | 57632 KB |
subtask1_05.txt | TLE | 3053 ms | 57652 KB |
subtask1_06.txt | TLE | 3054 ms | 57484 KB |
subtask1_07.txt | TLE | 3048 ms | 57380 KB |
subtask2_01.txt | AC | 362 ms | 23696 KB |
subtask2_02.txt | TLE | 3050 ms | 55700 KB |
subtask2_03.txt | TLE | 3053 ms | 57480 KB |
subtask2_04.txt | TLE | 3051 ms | 63816 KB |
subtask2_05.txt | TLE | 3051 ms | 63756 KB |
subtask2_06.txt | TLE | 3051 ms | 61008 KB |
subtask2_07.txt | TLE | 3052 ms | 63756 KB |
subtask2_08.txt | TLE | 3051 ms | 57272 KB |
subtask2_09.txt | TLE | 3051 ms | 52424 KB |
subtask2_10.txt | TLE | 3051 ms | 63552 KB |
subtask2_11.txt | TLE | 3052 ms | 63716 KB |
subtask2_12.txt | TLE | 3053 ms | 63984 KB |
subtask3_01.txt | TLE | 3049 ms | 51328 KB |
subtask3_02.txt | TLE | 3050 ms | 63156 KB |
subtask3_03.txt | TLE | 3051 ms | 63032 KB |
subtask3_04.txt | TLE | 3056 ms | 63460 KB |
subtask3_05.txt | TLE | 3050 ms | 56536 KB |
subtask3_06.txt | TLE | 3062 ms | 62880 KB |
subtask3_07.txt | TLE | 3053 ms | 63188 KB |
subtask3_08.txt | TLE | 3052 ms | 62876 KB |
subtask3_09.txt | TLE | 3052 ms | 63136 KB |
subtask3_10.txt | TLE | 3053 ms | 63576 KB |
subtask3_11.txt | TLE | 3067 ms | 55644 KB |
subtask3_12.txt | TLE | 3055 ms | 63068 KB |
subtask3_13.txt | TLE | 3052 ms | 62904 KB |
subtask3_14.txt | TLE | 3052 ms | 63464 KB |