Submission #8243369


Source Code Expand

#include <iostream>
#include <vector>
#include <map>
#include <unordered_map>
#include <queue>
#include <set>
#include <algorithm>
#include <string>
#include <math.h>
#include <limits.h>
#include <stack>
#include <complex>
#include <stdlib.h>
#include <stdio.h>
#include <functional>
#include <cfloat>
#include <math.h>
#include <numeric>
#include <string.h>
#include <sys/time.h>
#include <random>


#define fs first
#define sc second

using namespace std;

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


class Timer{
protected:
    double startTime;
    double limit;
    bool alreadyTimeup;
public:
    Timer(double timeLimit){
        set(timeLimit);
    }
    void set(double time_limit){
        limit = time_limit;
        startTime = now();
        alreadyTimeup = false;
    }
    bool timeup(){
        if(alreadyTimeup) return true;
        if(now() - startTime > limit){
            alreadyTimeup = true;
            return true;
        }else{
            return false;
        }
    }
    double elapse(){
        return now() - startTime;
    }
    double used(){
        return elapse() / limit;
    }
protected:
    double now(){
        timeval tv;
        gettimeofday(&tv, 0);
        return tv.tv_sec + tv.tv_usec * 1e-6;
    }
};



P operator + (const P & l,const P & r){
    return {l.fs + r.fs, l.sc + r.sc};
}


Timer timer(9.0);
mt19937 rand_gen(123123123);


class Board{
public:
    int a[32][32], h, w;
    P v[4] = {P(0, 1), P(1, 0), P(0, -1), P(-1, 0)};
    vector<T> sorted;
    bool state[32][32];
    int check[32][32];

    Board(int hh, int ww){
        h = hh; w = ww;
        for(int i = 0; i < 32; i++){
            for(int j = 0; j < 32; j++){
                a[i][j] = 0;
            }
        }
        for(int i = 0; i < 32; i++){
            for(int j = 0; j < 32; j++){
                check[i][j] = 0;
            }
        }
    }

    void prepare(){
        for(int i = 1; i <= h; i++){
            for(int j = 1; j <= w; j++){
                sorted.emplace_back(T(a[i][j], P(i, j)));
            }
        }
        sort(sorted.begin(), sorted.end());
        reverse(sorted.begin(), sorted.end());
    }

    void init(){
        for(int i = 0; i < 32; i++){
            for(int j = 0; j < 32; j++){
                state[i][j] = true;
            }
        }
        for(int i = 1; i <= h; i++){
            for(int j = 1; j <= w; j++){
                state[i][j] = false;
            }
        }
    }

    int getValue(P c){
        return a[c.fs][c.sc];
    }

    bool changeState(P x){
        state[x.fs][x.sc] = true;
    }

    bool reached(P x){
        return state[x.fs][x.sc];
    }

    P select(P c){
        P ret = P(-1, -1);
        int ma = 0;

        double r = rand_gen() / (1.0 + mt19937::max());
        vector<P> okList;
        for (auto dir: v) {
            P next = c + dir;
            if(!reached(next) && getValue(next) < getValue(c)){
                okList.emplace_back(next);
                if(getValue(next) > ma){
                    ret = next;
                    ma = getValue(next);
                }
            }
        }
        if(okList.empty()){
            return ret;
        }

        if(r <= 0.1){
            int x = rand_gen() % okList.size();
            ret = okList[x];
        }

        return ret;
    }

    vector<vector<P>> explore(){
        int su = 0;

        vector<vector<P>> res;
        vector<P> tmpPath;  tmpPath.push_back(sorted[0].sc);
        su++;

        changeState(sorted[0].sc);

        while(true) {
//            cerr << su << endl;
            if(su == h * w){
                res.push_back(tmpPath);
                break;
            }

            // 探索はすでに終了
            while(true) {
                auto itr = --(tmpPath.end());

                P next = select(*itr);
                if (next.fs == -1 && next.sc == -1) {
                    // 探索終了
                    tmpPath.emplace_back(P(-1, -1));
                    break;
                }

                tmpPath.emplace_back(next);
                su++;
                changeState(next);
            }
            res.push_back(tmpPath);

            // 新たなパスを追加
            for(int i = 1; i < h * w; i++){
                if(reached(sorted[i].sc)){
                    continue;
                }
                tmpPath.clear();
                tmpPath.emplace_back(sorted[i].sc);
                changeState(sorted[i].sc);
                su++;
                break;
            }
        }

        return res;
    }

    void solve(){
        int count = 0;
        vector<vector<P>> bestResult;
        int bestScore = INT32_MAX;
        while(true) {
            init();
            count++;
            double time_used = timer.used();

            if(time_used >= 1.0 - 1e-11){
                break;
            }
            vector<vector<P>> exploreResult = explore();
            int score = calcScore(exploreResult);
            if(score < bestScore){
                bestResult = exploreResult;
                bestScore = score;
                cerr << bestScore << endl;
            }
        }
        outputResult(bestResult);
        cerr << count << endl;
        checkResult();
    }

    int calcScore(vector<vector<P> > v){
        int res = 0;
        for(auto w: v){
            res += getValue(*w.begin());
        }
        return res;
    }

    void output(P x){
        check[x.fs][x.sc]++;
        if(x.fs != -1 && x.sc != -1) {
            cout << x.fs << " " << x.sc << endl;
        }
    }

    void outputResult(vector<vector<P>> res){
        for(auto w: res){
            vector<int> valueList;
            for(auto c: w){
                valueList.push_back(getValue(c));
            }
            while(true){
                if(valueList[0] == 0){
                    break;
                }
                valueList[0]--; output(w[0]);
                for(int i = 1; i < valueList.size(); i++){
                    if(valueList[i] == 0){
                        break;
                    }
                    if(valueList[i] == valueList[i-1]){
                        valueList[i]--;
                        output(w[i]);
                    }
                }
            }
        }
    }

    void checkResult(){
        for(int i = 1; i <= h; i++){
            for(int j = 1; j <= w; j++){
                if(check[i][j] != a[i][j]){
                    cout << "check " << i << " " << j << endl;
                }
            }
        }
    }
};


int main(){
    int h = 30, w = 30;
    Board board = Board(h, w);
    for(int i = 1; i <= h; i++){
        for(int j = 1; j <= w; j++){
            cin >> board.a[i][j];
        }
    }
    board.prepare();
    board.solve();


    return 0;
}

Submission Info

Submission Time
Task A - 高橋君の山崩しゲーム
User bomac1
Language C++14 (GCC 5.4.1)
Score 786144
Code Size 7132 Byte
Status AC
Exec Time 9078 ms
Memory 640 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 78717 / 100000 77991 / 100000 78787 / 100000 78071 / 100000 78260 / 100000 78863 / 100000 78891 / 100000 79047 / 100000 78863 / 100000 78654 / 100000
Status
AC × 1
AC × 1
AC × 1
AC × 1
AC × 1
AC × 1
AC × 1
AC × 1
AC × 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 9073 ms 640 KB
subtask_01_02.txt AC 9078 ms 640 KB
subtask_01_03.txt AC 9073 ms 640 KB
subtask_01_04.txt AC 9078 ms 640 KB
subtask_01_05.txt AC 9074 ms 640 KB
subtask_01_06.txt AC 9074 ms 640 KB
subtask_01_07.txt AC 9076 ms 640 KB
subtask_01_08.txt AC 9075 ms 640 KB
subtask_01_09.txt AC 9076 ms 640 KB
subtask_01_10.txt AC 9076 ms 640 KB