Submission #1604873


Source Code Expand

//#define __USE_MINGW_ANSI_STDIO 0
#include <bits/stdc++.h>

using namespace std;
typedef long long ll;
typedef vector<int> VI;
typedef vector<VI> VVI;
typedef vector<ll> VL;
typedef vector<VL> VVL;
typedef pair<int, int> PII;

#define FOR(i, a, n) for (ll i = (ll)a; i < (ll)n; ++i)
#define REP(i, n) FOR(i, 0, n)
#define ALL(x) x.begin(), x.end()
#define IN(a, b, x) (a<=x&&x<b)
#define MP make_pair
#define PB push_back
const int INF = (1LL<<30);
const ll LLINF = (1LL<<60);
const double PI = 3.14159265359;
const double EPS = 1e-12;
const int MOD = 1000000007;
//#define int ll

template <typename T> T &chmin(T &a, const T &b) { return a = min(a, b); }
template <typename T> T &chmax(T &a, const T &b) { return a = max(a, b); }

int dx[] = {0, 1, 0, -1}, dy[] = {1, 0, -1, 0};

#define MAIN

const int h = 30, w = 30;
int board[30][30], bo[30][30];
bool used[30][30];
int sum, retsum;

double eval(vector<PII> v) {
  // 連続列vから評価値を求める
  // 評価が高いものほど評価値を高くする
  if(v.size() == 0) return INF;
  VI vec;
  int szlim = INF;
  REP(i, v.size()) {
    vec.PB(board[v[i].first][v[i].second]);
    chmin(szlim, (int)i+vec[i]);
    if(i!=v.size()-1 && v[i] == v[v.size()-1]) return INF;
  }
  //連続列の長さ制限をする
  if(szlim < (int)vec.size()) return INF;

  int mi = INF;
  REP(i, vec.size()) chmin(mi, vec[i]-((int)vec.size()-1-(int)i));
  sum = 0, retsum = 0;
  REP(i, vec.size()) sum += vec[i] - (mi + vec.size()-1-i), retsum += vec[i];
  sum += mi + vec.size()-1;
  return (double)sum/retsum;
}

vector<PII> func(int sx, int sy) {
  vector<PII> ret;
  ret.PB({sy, sx});
  // ビーム幅k
  int k = 5;
  double retval = INF;
  queue<vector<PII>> que;
  que.push({{sy, sx}});
  while(que.size()) {
    // 連続列とその評価値
    priority_queue<pair<vector<PII>, double>> pq;
    while(que.size()) {
      vector<PII> v = que.front(); que.pop();
      int x = v[v.size()-1].second, y = v[v.size()-1].first;
      REP(i, 4) {
        int nx = x + dx[i], ny = y + dy[i];
        if(!IN(0, w, nx) || !IN(0, h, ny)) continue;
        // vにnx, nyを付け加えてその連続列について評価
        vector<PII> tmp = v;
        tmp.PB(MP(ny, nx));
        double val = eval(tmp);
        if(val == INF) continue;
        if(val < retval) {
          ret = tmp, retval = val;
        }
        pq.push(MP(tmp, val));
      }
    }
    // cout << retval << " ";
    // if(pq.size()) cout << pq.top().second << endl;
    // else cout << endl;
    int cnt = 0;
    while(pq.size()) {
      que.push(pq.top().first);
      pq.pop();
      cnt++;
      if(cnt >= k) break;
    }
  }

  return ret;
}

signed main(void)
{
  REP(i, h) REP(j, w) cin >> board[i][j];

  vector<PII> ans;
  int score = 0, prev = 0;

  int cnt = 0;
  int size = 0, times = 0;
  bool update = true;
  while(update) {
    // 長さが大きいものを優先的に選ぶ
    // 最初の方に使う
    int ma = 0;
    REP(i, h) REP(j, w) chmax(ma, board[i][j]);
    if(!ma) break;

    vector<PII> v;
    double vval = eval(v);
    REP(i, h) REP(j, w) {
      // cout << "i:" << i << " j:" << j << " " << vval << " " << v.size() << endl;
      vector<PII> tmp = func(j, i);
      if(eval(tmp) < vval) {
        v = tmp, vval = eval(v);
      }
    }
    times++, size += v.size();
    eval(v);
    // cout << "val:" << vval << " sum:" << sum << " retsum:" << retsum << endl;
    // for(PII i: v) cout << i.first << "," << i.second << " "; cout << endl;
    // for(PII i: v) cout << board[i.first][i.second] << " "; cout << endl;
    // cout << size << " " << v.size() << " ";

    // vを追っていって連続列をつくる
    FOR(i, 1, v.size()) {
      while(board[v[i].first][v[i].second] > 0
        && board[v[i].first][v[i].second] > board[v[i-1].first][v[i-1].second]-1) {
        board[v[i].first][v[i].second]--;
        ans.PB({v[i].first, v[i].second});
        score++;
      }
    }
    for(int i=v.size()-1; i>=0; --i) {
      if(board[v[i].first][v[i].second] == 0) v.pop_back();
      else break;
    }

    if(v.size() == 1) {
      while(board[v[0].first][v[0].second]) {
        board[v[0].first][v[0].second]--;
        ans.PB({v[0].first, v[0].second});
        score++;
      }
      // cout << score << " " << score-prev << endl;
      prev = score;
      continue;
    }
    bool endf = false;
    while(1) {
      // (sy, sx)からはじめて条件を満たすところまで1手番で操作する
      int len = 0;
      REP(i, v.size()-1) {
        board[v[i].first][v[i].second]--;
        ans.PB({v[i].first, v[i].second});
        if(board[v[i+1].first][v[i+1].second] == 0
          || board[v[i].first][v[i].second] != board[v[i+1].first][v[i+1].second]) {
          len = i;
          break;
        }
      }
      if(len == 0 && v.size() >= 2
        && board[v[v.size()-2].first][v[v.size()-2].second]
          == board[v[v.size()-1].first][v[v.size()-1].second]
        && board[v[v.size()-1].first][v[v.size()-1].second]) {
        //v.size()-1にも操作できる
        board[v[v.size()-1].first][v[v.size()-1].second]--;
        ans.PB({v[v.size()-1].first, v[v.size()-1].second});
        len = v.size()-1;
      }
      if(endf && len == 0) break;
      if(len != 0) endf = true;
      score++;
    }
    // cout << score << " " << score-prev << " " << (score-prev)/v.size() << endl;
    prev = score;
    cnt++;

    // cout << "----------------------" << endl;
    // REP(i, h) {
    //   REP(j, w) {
    //     cout << board[i][j] << " ";
    //   }
    //   cout << endl;
    // }
  }

  // cout << "end" << endl;
  REP(i, h) {
    REP(j, w) {
      while(board[i][j]) board[i][j]--, ans.PB({i, j}), score++;
    }
  }


#ifdef MAIN
  for(PII i: ans) cout << i.first+1 << " " << i.second+1 << endl;
#else
  // for(int i: vv) cout << i << " "; cout << endl;
  cout << "score:" << 100000 - score << " " << ans.size() << endl;
  cout << size << " " << times << " " << size/times << endl;
#endif

  return 0;
}

Submission Info

Submission Time
Task A - 高橋君の山崩しゲーム
User ferin_tech
Language C++14 (GCC 5.4.1)
Score 556069
Code Size 6231 Byte
Status TLE
Exec Time 10503 ms
Memory 1016 KB

Judge Result

Set Name test_01 test_02 test_03 test_04 test_05 test_06 test_07 test_08 test_09 test_10
Score / Max Score 79402 / 100000 78903 / 100000 79882 / 100000 0 / 100000 0 / 100000 79324 / 100000 79777 / 100000 79492 / 100000 0 / 100000 79289 / 100000
Status
AC × 1
AC × 1
AC × 1
TLE × 1
TLE × 1
AC × 1
AC × 1
AC × 1
TLE × 1
AC × 1
Set Name Test Cases
test_01 subtask_01_01.txt
test_02 subtask_01_02.txt
test_03 subtask_01_03.txt
test_04 subtask_01_04.txt
test_05 subtask_01_05.txt
test_06 subtask_01_06.txt
test_07 subtask_01_07.txt
test_08 subtask_01_08.txt
test_09 subtask_01_09.txt
test_10 subtask_01_10.txt
Case Name Status Exec Time Memory
subtask_01_01.txt AC 9175 ms 1016 KB
subtask_01_02.txt AC 8623 ms 1016 KB
subtask_01_03.txt AC 9881 ms 1016 KB
subtask_01_04.txt TLE 10455 ms 1016 KB
subtask_01_05.txt TLE 10503 ms 640 KB
subtask_01_06.txt AC 9353 ms 1016 KB
subtask_01_07.txt AC 9606 ms 1016 KB
subtask_01_08.txt AC 9838 ms 1016 KB
subtask_01_09.txt TLE 10503 ms 892 KB
subtask_01_10.txt AC 8517 ms 1016 KB