TCO14MRound1
注意
思った通りにうごきません!!!
やりたかったこと
スコアが変化するまでを1ステップとして、適当にビームサーチ。
セルの隣接記録を持っておくと、離れた場所のセルを交換できる。(昔に戻って入れ替えてくる) この性質を何とか使う。
やったこと(厳密にはやってない)
ランダムで2*2の四角と色を選ぶ。その色をかき集めてくる。(ここのアルゴリズムに問題あり) ランダムをたくさんやればいい奴見つかりそう。
コード
#include <vector>
#include <list>
#include <queue>
#include <complex>
#include <string>
#include <iostream>
#include <random>
#include <tuple>
#include <functional>
#include <algorithm>
#include <climits>
#include <fstream>
using namespace std;
std::ofstream ofs("log.txt");
auto m=mt19937();
auto rnd=[&](int x) {return uniform_int_distribution<>(0, x-1)(m); };
template <class T>
void print(vector<T> arr) {
for(int i=0; i<arr.size(); i++)cerr<<arr[i]<<" ";
cerr<<endl;
}
template<class T>
struct withKey
{
public:
int key;
T value;
bool operator<(const withKey& a)const {
return key<a.key;
}
};
template<class T>
withKey<T> make_withKey(int key, T value) {
return withKey<T>{key, value};
}
template <class T>
void appendvector(vector<T>& arr1,const vector<T>& arr2) {
arr1.reserve(arr1.size()+arr2.size());
for(auto e:arr2)arr1.push_back(e);
}
class LackofTheColor { public: int tilesize; };
class SquareRemover
{
public:
//utilities
int INF=INT_MAX;
using point=complex<int>;
inline int getX(point a) {
return real(a);
}
inline int getY(point a) {
return imag(a);
}
inline int x_distance(point a, point b) {
return abs(getX(a)-getX(b));
}
inline int y_distance(point a, point b) {
return abs(getY(a)-getY(b));
}
inline int distance(point a, point b) {
return abs(real(a)-real(b))+abs(imag(a)-imag(b));
}
auto nearer(point p)->function<auto(point, point)->bool> { return [&](point x, point y) {return distance(x, p)<distance(y, p); }; }
auto farther(point p)->function<auto(point, point)->bool> { return [&](point x, point y) {return distance(x, p)>distance(y, p); }; }
using square=complex<int>;//the smaller
bool valid(square s) {
return 0<=getX(s)&&getX(s)<N-1
&& 0<=getY(s)&&getY(s)<N-1;
}
vector<point> area(square s) {
vector<point> ret={ s, s+right, s+down, s+right+down };
return ret;
}
function<auto(int)->square> rndsq=[&](int N) {return square(rnd(N-1), rnd(N-1)); };
using vs=vector<square>;
function<auto(int)->vs>allsquare=[&](int N) {
vector<square> ans;
for(int i=0; i<N-1; i++)
for(int j=0; j<N-1; j++){
ans.push_back(square(i, j));
}
return ans;
};
vector<square> squarearound(point p) {
vector<square> op={ p, p+left, p+up, p+left+up };
vector<square> ret;
for(square s : op){
if(valid(s))ret.push_back(s);
}
return ret;
};
using direction=complex<int>;
const direction left= direction(0, -1);//-y
const direction right=direction(0, 1);//y
const direction up= direction(-1, 0);//-x
const direction down= direction(1, 0);//x
template <class T>
using field=vector<vector<T>>;
using board_t=vector<string>;
using color=int;
using vc=vector<color>;
function<auto (int)->vc> allcolor=[&](int colors) {
vector<color> ans;
for(int i=0; i<colors; i++)
ans.push_back(i);
return ans;
};
using swapping=tuple<point, point>;
template <class T>
vector<T>&& randomPartialPermutation(vector<T>&& arr) {
const int& N=arr.size();
for(int i=1; i<N; i++)
swap(arr[N-i], arr[rnd(N)]);
return move(arr);
}
void squarecheck_full(board_t& f, int& seed) {
for(square s : allsquare(N)){
for(color c : allcolor(colors)){
auto ar=area(s);
if(any_of(ar.begin(), ar.end(), [&](point p) {return f[getX(p)][getY(p)]==c; })){
for(int i=0; i<4; i++){
point& p=ar[i];
f[getX(p)][getY(p)]=seed;
seed = (seed * 48271) % 2147483647;
}
return squarecheck_full(f, seed);
}
}
}
return;
}
void apply(vector<swapping> opes, board_t& f, int seed) {
for(auto ope:opes){
squarecheck_full(f, seed);
int ax=getX(get<0>(ope));
int ay=getY(get<0>(ope));
int bx=getX(get<1>(ope));
int by=getY(get<1>(ope));
swap(f[ax][ay], f[bx][by]);
}
return;
}
//parameters
int colors;
vector<string> board;
int boardsize;
int& N=boardsize;
int startSeed;
point bettersearch(board_t& board, square s, color c, point target) {
point ans;
int mindis=INF;
auto ar=area(s);
for(int x=0; x<N; x++)
for(int y=0; y<N; y++)
if(board[x][y]-'0'==c
&&(find(ar.begin(), ar.end(), point(x, y))==ar.end()
|| target==point(x, y)
))
{
int d=INF;
for(point p : area(s))
d=min(d, distance(p, point(x, y)));
if(mindis>d){ans=point(x,y);mindis=d;}
}
return ans;
}
//(-d,(x,y))
priority_queue<withKey<point>> search4(board_t& board, square s, color c) {
priority_queue<withKey<point>> options;
for(int x=0; x<N; x++)
for(int y=0; y<N; y++)
if(board[x][y]-'0'==c)
{
int d=INF;
for(point p : area(s))
d=min(d, distance(p, point(x, y)));
options.push(make_withKey(-d, point(x, y)));
}
if(options.size()<4)throw LackofTheColor{ options.size() };
return options;
}
//a->b
vector<swapping> randomPathShift(point a, point b) {
direction xdir, ydir;
if(getX(b)-getX(a)>0)xdir=down;
else xdir=up;
if(getY(b)-getY(a)>0)ydir=right;
else ydir=left;
vector<point> di(distance(a, b), ydir);
for(int i=0; i<x_distance(a, b); i++)
di[i]=xdir;
auto randomed_di=randomPartialPermutation(move(di));
vector<swapping> ans;
point cur=a;
for(int i=0; i<randomed_di.size(); i++){
point nextpoint=cur+randomed_di[i];
ans.push_back(swapping(cur, nextpoint));
cur=nextpoint;
}
return ans;//OK
}
vector<swapping> gather4Path(board_t& board, square s, color c) {
auto que=search4(board, s, c);
vector<point> options;
while(options.size()<4){
auto pick=que.top();
que.pop();
options.push_back(pick.value);
while(que.top().key==pick.key){
options.push_back(que.top().value);
que.pop();
}
}
vector<swapping> ans;
for(auto p:area(s)){
auto nearest=min_element(options.begin(), options.end(), nearer(p));
appendvector(ans, randomPathShift(*nearest, p));
options.erase(nearest);
}
return ans;//OK
}
vector<swapping> bettergather4Path(board_t& board, square s, color c) {
board_t b_copy(board);
vector<swapping> ans;
for(auto p:area(s)){
auto nearest=bettersearch(b_copy,s,c,p);
appendvector(ans, randomPathShift(nearest, p));
}
return ans;
}
vector<int> playIt_randomAns(int colors, board_t board, int startSeed) {
//init
this->colors=colors;
this->board=board;
this->startSeed=startSeed;
this->boardsize=board.size();
vector<int> ans;
auto push=[&](int&& x, int&& y, int&& dir) {
ans.push_back(x);
ans.push_back(y);
ans.push_back(dir);
};
auto randomans=[&]() {
if(rnd(2)==0)
push(rnd(N-1)+1, rnd(N), 0);
else
push(rnd(N), rnd(N-1), 1);
};
for(int i=0; i<10000; i++)
randomans();
return ans;
}
vector<swapping> playIt_hoge(int colors, board_t board, int startSeed) {
//init
this->colors=colors;
this->board=board;
this->startSeed=startSeed;
this->boardsize=board.size();
vector<swapping> ans;
auto addans=[&]() {
appendvector(ans,randomPathShift(point(0,0),point(N-1,N-1)));
};
while(ans.size()<=10000)addans();
while(ans.size()>10000)ans.pop_back();
return ans;;
}
vector<swapping> playIt_randomgreedy(int colors, board_t board, int startSeed) {
//init
this->colors=colors;
this->board=board;
this->startSeed=startSeed;
this->boardsize=board.size();
vector<swapping> ans;
auto addans=[&]() {
vector<swapping> ops;
square curs;
color curc;
back:
try{
ops=bettergather4Path(this->board, rndsq(N), rnd(colors));
for(int i=0; i<10; i++){
square shoge;color choge;
auto m=bettergather4Path(this->board, shoge=rndsq(N), choge=rnd(colors));
if(ops.size()>m.size()){
ops=m;
curs=shoge;
curc=choge;
}
}
} catch(...){
goto back;
}
apply(ops, this->board, this->startSeed);
appendvector(ans, ops);
ofs<<"sq:"<<curs<<curc<<endl;
};
while(ans.size()<=10000)addans();
while(ans.size()>10000)ans.pop_back();
return ans;
}
vector<int> playIt(int colors, board_t board, int startSeed) {
auto toanstype=[&](vector<swapping> vs) {
vector<int> ans;
for(int i=0; i<vs.size(); i++){
swapping& s=vs[i];
auto a=get<0>(s);
auto b=get<1>(s);
ans.push_back(getX(a));
ans.push_back(getY(a));
for(int i=0; i<4; i++){
direction dir=vector<direction>{up, right, down, left}[i];
if(b-a==dir){
ans.push_back(i);
}
}
}
return ans;
};
auto ret=playIt_randomgreedy(colors, board, startSeed);
/*for(int i=0; i<ret.size(); i++)
ofs<<get<0>(ret[i])<<"\t"<<get<1>(ret[i])<<endl;*/
return toanstype(ret);
}
};
//***************************
int main() {
int colors;
int N;
cin>>colors>>N;
vector<string> board(N);
for(int i=0; i<N; i++)
cin>>board[i];
int startSeed;
cin>>startSeed;
ofs<<"input:"<<endl;
ofs<<colors<<endl;
ofs<<N<<endl;
for(int i=0; i<N; i++)
ofs<<board[i]<<endl;
ofs<<startSeed<<endl;
ofs<<"output:"<<endl;
auto ret=SquareRemover().playIt(colors, board, startSeed);
for(int i=0; i<10000; i++)
ofs<<ret[3*i]<<"\t"<<ret[3*i+1]<<"\t"<<ret[3*i+2]<<endl;
for(int i=0; i<30000; i++)
cout<<ret[i]<<endl;
return 0;
}