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
AC × 2
AC × 22
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