Created
August 29, 2020 09:30
-
-
Save n-ari/80cc2cb6bc4c88d6d43d07340c6e766d to your computer and use it in GitHub Desktop.
天下一Game Battle Contest 2020 rickytheta解(C++のみ)
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
// main関数内以外は全てサンプルコードのままです | |
#include <iostream> | |
#include <vector> | |
#include <string> | |
#include <random> | |
#include <thread> | |
#include <chrono> | |
using namespace std; | |
pair<int, int> get_game() { | |
cout << "game" << endl; | |
int game_id, remaining_time; | |
cin >> game_id >> remaining_time; | |
return {game_id, remaining_time}; | |
} | |
vector<vector<int>> get_stage(int game_id) { | |
cout << "stage " << game_id << endl; | |
int n; | |
cin >> n; | |
if (n != 20) throw 1; | |
vector<vector<int>> a(20, vector<int>(20)); | |
for (auto& b : a) for (auto& x : b) cin >> x; | |
return a; | |
} | |
pair<bool, pair<vector<vector<int>>, vector<vector<int>>>> get_areas(int game_id) { | |
cout << "areas " << game_id << endl; | |
string status; | |
cin >> status; | |
if (status == "ok") { | |
vector<vector<int>> a1(20, vector<int>(20)); | |
vector<vector<int>> a2(20, vector<int>(20)); | |
for (auto& b : a1) for (auto& x : b) cin >> x; | |
for (auto& b : a2) for (auto& x : b) cin >> x; | |
return {true, {a1, a2}}; | |
} else if (status == "too_many_request") { | |
return {false, {{}, {}}}; | |
} else { | |
throw 1; | |
} | |
} | |
bool claim(int game_id, int r, int c, int m) { | |
cout << "claim " << game_id << " " << r << "-" << c << "-" << m << endl; | |
string status; | |
cin >> status; | |
if (status == "ok") { | |
return true; | |
} else if (status == "game_finished") { | |
return false; | |
} else { | |
throw 1; | |
} | |
} | |
struct CalcScore { | |
const vector<vector<int>>& stage; | |
const vector<vector<int>>& num_claim; | |
const vector<vector<int>>& my_claim; | |
vector<vector<bool>> visited; | |
CalcScore(const vector<vector<int>>& stage, const vector<vector<int>>& num_claim, const vector<vector<int>>& my_claim) | |
: stage(stage), num_claim(num_claim), my_claim(my_claim), visited(20, vector<bool>(20)) {} | |
pair<double, int> f(int r, int c) { | |
if (r < 0 || r >= 20 || c < 0 || c >= 20 || my_claim[r][c] == 0 || visited[r][c]) { | |
return {1e+300, 0}; | |
} | |
visited[r][c] = true; | |
double r1 = (double)stage[r][c] / num_claim[r][c]; | |
int r2 = 1; | |
for (auto p : {f(r+1, c), f(r-1, c), f(r, c+1), f(r, c-1)}) { | |
r1 = min(r1, p.first); | |
r2 += p.second; | |
} | |
return {r1, r2}; | |
} | |
double calc() { | |
double score = 0; | |
for (int i = 0; i < 20; ++ i) { | |
for (int j = 0; j < 20; ++ j) { | |
auto p = f(i, j); | |
score += p.first * p.second; | |
} | |
} | |
return score; | |
} | |
}; | |
int main() { | |
random_device rd; | |
mt19937 mt(rd()); | |
for (;;) { | |
auto game = get_game(); // <game_id, remaining_time> | |
auto game_id = game.first; | |
auto stage = get_stage(game_id); // vector<vi>, 20x20, value[i][j] | |
for (int cnt = 0; ; ++cnt) { | |
// get data | |
auto remaining_time = get_game().second; | |
auto areas = get_areas(game_id); // <valid, <20x20(acq), 20x20(mine)> | |
if (!areas.first) { | |
cerr << "too_many_request" << endl; | |
this_thread::sleep_for(chrono::milliseconds(500)); | |
continue; | |
} | |
auto& num_claim = areas.second.first; | |
auto& my_claim = areas.second.second; | |
auto score = CalcScore(stage, num_claim, my_claim).calc(); | |
cerr << "game_id: " << game_id << " score: " << score << " remain: " << remaining_time << " ms" << endl; | |
// pattern | |
if(false){ | |
int pat[400] = { | |
4,4,4,4,0,4,4,4,4,0,4,4,4,4,0,4,4,4,4,0, | |
4,4,4,4,0,4,4,4,4,0,4,4,4,4,0,4,4,4,4,0, | |
4,4,4,4,0,4,4,4,4,0,4,4,4,4,0,4,4,4,4,0, | |
4,4,4,4,0,4,4,4,4,0,4,4,4,4,0,4,4,4,4,0, | |
0,0,0,0,1,0,0,0,0,1,0,0,0,0,1,0,0,0,0,1, | |
4,4,4,4,0,4,4,4,4,0,4,4,4,4,0,4,4,4,4,0, | |
4,4,4,4,0,4,4,4,4,0,4,4,4,4,0,4,4,4,4,0, | |
4,4,4,4,0,4,4,4,4,0,4,4,4,4,0,4,4,4,4,0, | |
4,4,4,4,0,4,4,4,4,0,4,4,4,4,0,4,4,4,4,0, | |
0,0,0,0,1,0,0,0,0,1,0,0,0,0,1,0,0,0,0,1, | |
4,4,4,4,0,4,4,4,4,0,4,4,4,4,0,4,4,4,4,0, | |
4,4,4,4,0,4,4,4,4,0,4,4,4,4,0,4,4,4,4,0, | |
4,4,4,4,0,4,4,4,4,0,4,4,4,4,0,4,4,4,4,0, | |
4,4,4,4,0,4,4,4,4,0,4,4,4,4,0,4,4,4,4,0, | |
0,0,0,0,1,0,0,0,0,1,0,0,0,0,1,0,0,0,0,1, | |
4,4,4,4,0,4,4,4,4,0,4,4,4,4,0,4,4,4,4,0, | |
4,4,4,4,0,4,4,4,4,0,4,4,4,4,0,4,4,4,4,0, | |
4,4,4,4,0,4,4,4,4,0,4,4,4,4,0,4,4,4,4,0, | |
4,4,4,4,0,4,4,4,4,0,4,4,4,4,0,4,4,4,4,0, | |
0,0,0,0,1,0,0,0,0,1,0,0,0,0,1,0,0,0,0,1, | |
}; | |
} | |
// ichimatsu | |
if(false){ | |
int ci = 0, cj = 0; | |
int csize = 2; | |
while (true) { | |
if (my_claim[ci][cj] == 0) break; | |
cj += 4; | |
if (cj >= 20) { | |
ci += 2; | |
cj = (cj + 2) % 4; | |
} | |
} | |
if (ci >= 20 || cj >= 20) { | |
ci = cj = 0; | |
} | |
if (!claim(game_id, ci, cj, csize)) { | |
break; | |
} | |
} | |
// best 2x2 or 1x1 claim | |
if(true){ | |
int ci = 0, cj = 0; | |
int csize = 1; | |
double cval = 0.0; | |
// int szmin = remaining_time <= 40000 ? 1 : 2; | |
const int szmin = 1; | |
int szmax = remaining_time <= 4000 ? 1 : | |
remaining_time <= 40000 ? 2 : 3; | |
// const int szmax = 2; | |
double cscore = CalcScore(stage, num_claim, my_claim).calc(); | |
for (int size = szmin; size <= szmax; ++ size) { | |
for (int i = 0; i < 20 - size + 1; ++ i) { | |
for (int j = 0; j < 20 - size + 1; ++ j) { | |
bool all_got = true; | |
bool bad = false; | |
for (int y=0; y<size; y++){ | |
for(int x=0; x<size; x++){ | |
if (my_claim[i+y][j+x] == 0) { | |
all_got = false; | |
} | |
if (stage[i+y][j+x] <= 100) { | |
bad = true; | |
} | |
} | |
} | |
if (all_got || bad) { | |
continue; | |
} | |
for (int y=0; y<size; y++){ | |
for(int x=0; x<size; x++){ | |
num_claim[i+y][j+x] ++; | |
my_claim[i+y][j+x] ++; | |
} | |
} | |
double val = CalcScore(stage, num_claim, my_claim).calc() - cscore; | |
if (remaining_time <= 30000) val = val / (size+1) / (size+1); | |
if (val > cval) { | |
cval = val; | |
ci = i; | |
cj = j; | |
csize = size; | |
} | |
for (int y=0; y<size; y++){ | |
for(int x=0; x<size; x++){ | |
num_claim[i+y][j+x] --; | |
my_claim[i+y][j+x] --; | |
} | |
} | |
} | |
} | |
} | |
if (!claim(game_id, ci, cj, csize)) { | |
break; | |
} | |
} | |
} | |
while (get_game().first == game_id) { | |
this_thread::sleep_for(chrono::milliseconds(500)); | |
} | |
} | |
} |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment