Submission #433022
Source Code Expand
import java.util.ArrayList; import java.util.Scanner; public class Main { public static void main(String[] args) { new Main().solve(); } int[][] b = new int[2][3]; int[][] c = new int[3][2]; Pair[] memo = new Pair[20000]; public void solve() { Scanner sc = new Scanner(System.in); for(int i=0;i<2;i++) { for(int j=0;j<3;j++) { b[i][j] = sc.nextInt(); } } for(int i=0;i<3;i++) { for(int j=0;j<2;j++) { c[i][j] = sc.nextInt(); } } Pair p = chokudai(0); System.out.println(p.dai); System.out.println(p.ko); } public Pair chokudai(int v) { if (memo[v] != null) { return memo[v]; } Pair max = new Pair(-1,-1); for(int bd:next(v, 1)) { Pair p = chokuko(bd); if (p.dai > max.dai) { max = p; } } return memo[v] = max; } public Pair chokuko(int v) { if (memo[v] != null) { return memo[v]; } Pair end = end(v); if (end != null) { return memo[v] = end; } Pair max = new Pair(-1,-1); for(int bd:next(v, 2)) { Pair p = chokudai(bd); if (p.ko > max.ko) { max = p; } } return memo[v] = max; } public Pair end(int v) { int[][] bd = new int[3][3]; for(int i=0;i<9;i++) { int bb = v % 3; if (bb == 0) { return null; } bd[i/3][i%3] = bb; v /= 3; } int dai = 0; int ko = 0; for(int i=0;i<2;i++) { for(int j=0;j<3;j++) { if (bd[i][j] == bd[i+1][j]) { dai += b[i][j]; }else{ ko += b[i][j]; } } } for(int i=0;i<3;i++) { for(int j=0;j<2;j++) { if (bd[i][j] == bd[i][j+1]) { dai += c[i][j]; }else{ ko += c[i][j]; } } } return new Pair(dai,ko); } public ArrayList<Integer> next(int v,int t) { ArrayList<Integer> al = new ArrayList<>(); int[] a = new int[9]; for(int i=0;i<9;i++) { a[i] = v % 3; v /= 3; } for(int i=0;i<9;i++) { if (a[i] == 0) { a[i] = t; int u = 0; for(int j=0;j<9;j++) { u = u * 3 + a[8-j]; } al.add(u); a[i] = 0; } } return al; } static class Pair { int dai,ko; public Pair(int dai,int ko) { this.dai = dai; this.ko = ko; } public String toString() { return dai + "," + ko; } } public static void debug(int v) { for(int i=0;i<3;i++) { for(int j=0;j<3;j++) { System.out.print(v%3==0 ? ' ' : v%3==1 ? 'o' : 'x'); v /= 3; } System.out.println(); } } }
Submission Info
Submission Time | |
---|---|
Task | C - 双子と○×ゲーム |
User | piroz95 |
Language | Java8 (OpenJDK 1.8.0) |
Score | 100 |
Code Size | 2503 Byte |
Status | AC |
Exec Time | 378 ms |
Memory | 32240 KB |
Judge Result
Set Name | Sample | All | ||||
---|---|---|---|---|---|---|
Score / Max Score | 0 / 0 | 100 / 100 | ||||
Status |
|
|
Set Name | Test Cases |
---|---|
Sample | sample-01.txt, sample-02.txt |
All | test-01.txt, test-02.txt, test-03.txt, test-04.txt, test-05.txt, test-06.txt, test-07.txt, test-08.txt, test-09.txt, test-10.txt, test-11.txt, test-12.txt, test-13.txt, test-14.txt, test-15.txt, test-16.txt, test-17.txt, test-18.txt, test-19.txt, test-20.txt, sample-01.txt, sample-02.txt |
Case Name | Status | Exec Time | Memory |
---|---|---|---|
sample-01.txt | AC | 375 ms | 32224 KB |
sample-02.txt | AC | 371 ms | 31984 KB |
test-01.txt | AC | 373 ms | 31944 KB |
test-02.txt | AC | 363 ms | 32048 KB |
test-03.txt | AC | 366 ms | 32104 KB |
test-04.txt | AC | 368 ms | 32240 KB |
test-05.txt | AC | 378 ms | 32124 KB |
test-06.txt | AC | 373 ms | 32008 KB |
test-07.txt | AC | 373 ms | 32164 KB |
test-08.txt | AC | 369 ms | 32068 KB |
test-09.txt | AC | 366 ms | 32048 KB |
test-10.txt | AC | 365 ms | 31796 KB |
test-11.txt | AC | 366 ms | 32028 KB |
test-12.txt | AC | 366 ms | 31964 KB |
test-13.txt | AC | 369 ms | 31924 KB |
test-14.txt | AC | 369 ms | 31936 KB |
test-15.txt | AC | 371 ms | 32000 KB |
test-16.txt | AC | 365 ms | 32096 KB |
test-17.txt | AC | 368 ms | 32028 KB |
test-18.txt | AC | 366 ms | 31972 KB |
test-19.txt | AC | 366 ms | 31948 KB |
test-20.txt | AC | 371 ms | 31844 KB |