AtCoder Beginner Contest 025

Submission #3980782

Source codeソースコード

#include <bits/stdc++.h>
#define rep(i,n) for(int i=0;i<(n);++i)
#define ALL(A) A.begin(), A.end()
#define INF (1<<28)

using namespace std;

typedef long long ll;
typedef pair<int, int> P;

int b[2][3];
int c[3][2];

map<string,int> memo;

void dispGrid(string grid){
	rep (i, 3){
		rep (j, 3){
			cerr << grid[i * 3 + j];
		} // end rep
		cerr << endl;
	} // end rep
}

int dfs(string grid, int depth){
	if (memo.count(grid)){
		return memo[grid];
	} // end if

	if (depth == 9){
		int sum = 0;
		rep (i, 3){
			rep (j, 3){
				if (i + 1 < 3){
					sum += (grid[i * 3 + j] == grid[(i+1) * 3 + j] ? b[i][j] : 0);
				} // end if
				if (j + 1 < 3){
					sum += (grid[i * 3 + j] == grid[i * 3 + (j+1)] ? c[i][j] : 0);
				} // end if
			} // end rep
		} // end rep				
		return sum;
	} // end if


	int maxScore = -1, minScore = INF;
	rep (pos, 9){
		if (grid[pos] == '.'){
			if (depth % 2 == 0){	// 直大くんの手番なら score の最大化をねらう
				grid[pos] = 'o';
				maxScore = max(maxScore, dfs(grid, depth + 1));
			}else{ // if (depth % 2 != 0) 直子さんの手番なら score の最小化をねらう
				grid[pos] = 'x';
				minScore = min(minScore, dfs(grid, depth + 1));
			} // end if
			grid[pos] = '.';
		} // end if		
	} // end rep

	return memo[grid] = (depth % 2 == 0 ? maxScore : minScore);
}						

int main()
{
	memo.clear();
	string grid = string(9, '.');
	ios_base::sync_with_stdio(0);
	cin.tie(0);

	int total = 0;
	rep (i, 2) rep (j, 3) cin >> b[i][j], total += b[i][j];
	rep (i, 3) rep (j, 2) cin >> c[i][j], total += c[i][j];
	
	int score = dfs(grid, 0);
	cout << score << endl;
	cout << total - score << endl;

	return 0;
}

Submission

Task問題 C - 双子と○×ゲーム
User nameユーザ名 ty70
Created time投稿日時
Language言語 C++14 (GCC 5.4.1)
Status状態 AC
Score得点 100
Source lengthソースコード長 1744 Byte
File nameファイル名
Exec time実行時間 13 ms
Memory usageメモリ使用量 896 KB

Test case

Set

Set name Score得点 / Max score Cases
Sample - sample-01.txt,sample-02.txt
All 100 / 100 sample-01.txt,sample-02.txt,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

Test case

Case name Status状態 Exec time実行時間 Memory usageメモリ使用量
sample-01.txt AC 11 ms 896 KB
sample-02.txt AC 11 ms 896 KB
test-01.txt AC 11 ms 896 KB
test-02.txt AC 11 ms 896 KB
test-03.txt AC 11 ms 896 KB
test-04.txt AC 11 ms 896 KB
test-05.txt AC 11 ms 896 KB
test-06.txt AC 11 ms 896 KB
test-07.txt AC 11 ms 896 KB
test-08.txt AC 11 ms 896 KB
test-09.txt AC 11 ms 896 KB
test-10.txt AC 11 ms 896 KB
test-11.txt AC 11 ms 896 KB
test-12.txt AC 11 ms 896 KB
test-13.txt AC 11 ms 896 KB
test-14.txt AC 11 ms 896 KB
test-15.txt AC 11 ms 896 KB
test-16.txt AC 11 ms 896 KB
test-17.txt AC 11 ms 896 KB
test-18.txt AC 13 ms 896 KB
test-19.txt AC 11 ms 896 KB
test-20.txt AC 11 ms 896 KB