いろいろがんばりたいブログ

情報科学科の人がいろいろ書きます。

TCO 2014 R1

ほとんど時間をとってないので、適当なコードを投げていた。 ビーム幅3と書いてある時点でお察し

// compile in C++11. use -std=c++11.
#include <iostream>
#include <iomanip>
#include <vector>
#include <valarray>
#include <map>
#include <set>
#include <list>
#include <queue>
#include <stack>
#include <bitset>
#include <utility>
#include <numeric>
#include <algorithm>
#include <functional>
#include <complex>
#include <string>
#include <sstream>
#include <chrono>

#include <cstdio>
#include <cstdlib>
#include <cctype>
#include <cstring>

// this require C++11
#include <unordered_set>
#include <unordered_map>
#include <random>

using namespace std;

#define all(c) c.begin(),c.end()
#define repeat(i,n) for(int i=0;i<static_cast<int>(n);i++)
#define debug(x) #x << "=" << (x)
#define dump(x) cerr << debug(x) << " (L:" << __LINE__ << ")"<< endl

using ll = long long;
using vi = vector<int>;

ostream& operator<<(ostream& os,const vector<string>& vec){
    for(const auto& v : vec){
        os << v << endl;
    }
    return os;
}

template<typename T>
ostream& operator<<(ostream& os,const vector<T>& vec){
    os << "[";
    for(const auto& v : vec){
        os << v << ",";
    }
    os << "]";
    return os;
}


struct State{
    vector<string> board;
    double score;
    vector<int> proc;
    int cur;
    int a;


    State(vector<string> board_,double score_,vector<int> proc_,int cur_,int a_)
        : board(board_),score(score_),proc(proc_),cur(cur_),a(a_) {}
};

bool operator<(const State& left,const State& right){
    return left.score < right.score;
}
bool operator>(const State& left,const State& right){
    return left.score > right.score;
}

// color is in [4,6]
// N is in [8,16]
// startSeed is in [1,2147483647].
//  each value is uniformly random.
//  0 -- up, 1 -- right, 2 -- down, 3 -- left.
const array<int,4> dy = {-1,0,1,0};
const array<int,4> dx = {0,1,0,-1};

const array<int,8> ddy = {-1, 0, 1,
                         -1    , 1,
                         -1, 0, 1};
const array<int,8> ddx = {-1,-1,-1,
                          0    , 0,
                          1, 1, 1};

const int TURN = 10000;
struct SquareRemover{

    vector<int> playIt(int colors,vector<string> board,int startSeed){
        ios::sync_with_stdio(false);
        cin.tie(0);
        const int N = board.size();
        vector<State> cur;
        cur.push_back(State(board,make_score(board,0),vector<int>(),0,startSeed));

        // auto begin = std::chrono::system_clock::now();
        int ran_num = 15;
        const int beam_width = 4;
        repeat(beam,TURN){
            // if(beam == 1){
            //     begin = std::chrono::system_clock::now();
            // }
            // dump(beam);
            // priority_queue<State,vector<State>,less<State>> queue;
            priority_queue<State,vector<State>,greater<State>> queue;

            for(const State& st : cur){
                repeat(ran,ran_num){
                    // dump(ran);
                    // int row = row_col(mt);
                    // int col = row_col(mt);
                    // int d = dist_d(mt);
                    int row = xor128()%N;
                    int col = xor128()%N;
                    int d = xor128()%4;
                    if(d == 0 and row == 0) continue;
                    if(d == 2 and row == N-1) continue;
                    if(d == 1 and col == N-1) continue;
                    if(d == 3 and col == 0) continue;

                    vector<string> buf = st.board;
                    const int cr = row+dy[d];
                    const int cc = col+dx[d];

                    if(buf[row][col] == buf[cr][cc]) continue;
                    swap(buf[row][col],buf[cr][cc]);
                    vector<int> proc = st.proc;
                    proc.push_back(row);
                    proc.push_back(col);
                    proc.push_back(d);

                    int a = st.a;
                    int sc = st.cur;
                    while(true){
                        repeat(r,N-1){
                            repeat(c,N-1){
                                if(buf[r][c] == buf[r+1][c] and
                                   buf[r][c] == buf[r][c+1] and
                                   buf[r][c] == buf[r+1][c+1]){
                                    buf[r][c] = '0'+(a%colors);
                                    a = nextA(a);
                                    buf[r][c+1] = '0'+(a%colors);
                                    a = nextA(a);
                                    buf[r+1][c] = '0'+(a%colors);
                                    a = nextA(a);
                                    buf[r+1][c+1] = '0'+(a%colors);
                                    a = nextA(a);
                                    sc++;
                                    goto found;
                                }
                            }
                        }
                        break;
                    found:
                        continue;
                    }
                    const double curscore = make_score(buf,sc);
                    queue.push(State(buf,curscore,proc,sc,a));
                    if(queue.size() > beam_width) queue.pop();
                }
            }

            vector<State> next;
            while(not queue.empty()){
                next.push_back(queue.top());
                queue.pop();
            }

            cur = next;
        }
        // dump(cur.front().cur);
        return cur.front().proc;
    }
    inline int nextA(int prev){
        return (prev * 48271ll) % 2147483647;
    }
    inline unsigned long xor128(){
        static unsigned long x=123456789,y=362436069,z=521288629,w=88675123;
        unsigned long t;
        t=(x^(x<<11));x=y;y=z;z=w; return( w=(w^(w>>19))^(t^(t>>8)) );
    }
    inline double make_score(const vector<string>& sc,int cur){
        int N = sc.size();
        double ret = 0;
        repeat(row,N){
            repeat(col,N){
                repeat(i,8){
                    int cr = row+ddy[i];
                    int cc = col+ddx[i];
                    if(cr < 0 or cr >= N or cc < 0 or cc >= N) continue;
                    if(sc[row][col] == sc[cr][cc]){
                        ret += 1.0/10;
                    }
                }
            }
        }
        return ret+cur;
    }
};

int main(){
    ios::sync_with_stdio(false);
    cin.tie(0);
    auto const begin = std::chrono::system_clock::now();
    int colors;cin >> colors;
    int N;cin >> N;
    vector<string> board(N);
    repeat(i,N){
        cin >> board[i];
    }
    int startSeed;cin >> startSeed;
    SquareRemover sr;
    vector<int> ret = sr.playIt(colors,board,startSeed);
    auto const end = std::chrono::system_clock::now();

    cerr << std::chrono::duration_cast<std::chrono::milliseconds>(end - begin).count() << endl;
    for(int r : ret){
        cout << r << endl;
    }


    return 0;
}