天下一Game Battle Contest 2020 rickytheta解(C++のみ)

gbc2020.cpp

// 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));
    }
  }
}