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