Marathon Match 78 の記録
最終的なアルゴリズム
左上(0,0)を出発点として、盤面上に一本の線を引いていく。
１マス進むことを一手として１０手探索してはもっとも高い点数が
得られるものを最終的な解に追加していく。このとき輪っかができなくなるものは除外する。
探索と解の追加を繰り返して出発点に戻ってきたら終了する。
経過
１：左上を始点として点数が最大になる輪っかを作るようなビーム探索を書く。
（当時は自分が書いているものがビーム探索であるとは知らなかった。）
※ビーム探索とは幅優先探索において評価の高い解のみを残すような探索のこと。
２：うーん、遅すぎる。
３：だんだん保持する解の個数を減らす。
４：あーもうこれは保持する解を一つにしてもいいんじゃない。
５：保持する解を一つにする。
６：１０手づつ深さ優先探索して暫定解に付け足していって輪っかができたら終了するアルゴリズムに変更する。
結果
１０５人中５７位。
初めてのマラソンマッチにしては健闘したと見るか、
修行が足りないと見るかは判断が分かれるところ。（僕の頭の中では）
反省点
大量のテストを簡単に実行できる環境を早めに構築するべきだった。
（最終的にはコマンド一つで１００個のテストケースを試すようにした。）
更に、テストから得られた結果を簡単に判断できるようにするべきだった。
良かった点
公式のビジュアライザを改造して、サイズやfillRatioをコマンド引数で変更できるようにし、
更に正しくない（輪っかになっていない）解も目で見れるようにしたのは良かった。
最終提出コード
#include <iostream> #include <cstdio> #include <cstdlib> #include <cmath> #include <string> #include <vector> #include <queue> #include <map> #include <set> #include <algorithm> #include <functional> #include <cstring> #include <sstream> #define FOR(i,k,n) for (int i=(k); i<(int)(n); ++i) #define REP(i,n) FOR(i,0,n) #define FORIT(i,c) for(__typeof((c).begin())i=(c).begin();i!=(c).end();++i) #define SZ(i) ((int)i.size()) #define pb push_back #define mp make_pair #define ALL(X) (X).begin(),(X).end() typedef long long LL; // #define DFS_DEPTH 11 #define MAX_ANS_LENGTH 20200 #define INF 100000000 using namespace std; int dfsDepth=10; int mv[4][2]={{-1,0},{1,0},{0,-1},{0,1}}; int c2m(char c){if(c=='U')return 0;if(c=='D')return 1;if(c=='L')return 2;if(c=='R')return 3;return INF;} int iabs(int n){if(0<=n)return n;else return -n;} vector<string> dia; int H,W; int isVisited[110][110]; int nVisit[110][110]; int nTouch[110][110]; int bfs[110][110]; string udlr="UDLR"; string snake; int point; pair<pair<int,int>,string> ans; int ystart,xstart,yhead,xhead,ygoal,xgoal; class BIT{ public: int bit[MAX_ANS_LENGTH+10]; int sum(int i){ i++; int s=0; while(0<i){ s+=bit[i]; i-=i&-i; } return s; } void add(int i,int x){ i++; while(i<=MAX_ANS_LENGTH+5){ bit[i]+=x; i+=i&-i; } } }; BIT turnCount; int rorlturn(char s,char t){//left turn = 1 right turn = -1 if(s=='U'){if(t=='L')return 1;if(t=='R')return -1;} if(s=='L'){if(t=='D')return 1;if(t=='U')return -1;} if(s=='D'){if(t=='R')return 1;if(t=='L')return -1;} if(s=='R'){if(t=='U')return 1;if(t=='D')return -1;} return 0; } bool isInLoop(const int w,const int v,const char n,const int y,const int x,const char m,const int nv){ if(y==0||y==H||x==0||x==W)return false; //右回りのループを検出 int yy=y,xx=x; if(m=='U')xx--; if(m=='D')xx++; if(m=='L')yy++; if(m=='R')yy--; if(0<isVisited[yy][xx]&&turnCount.sum(nv)-turnCount.sum(nVisit[yy][xx]+1)<=-3) return true; //左回りのループを検出 yy=y,xx=x; if(m=='U')xx++; if(m=='D')xx--; if(m=='L')yy--; if(m=='R')yy++; if(0<isVisited[yy][xx]&&turnCount.sum(nv)-turnCount.sum(nVisit[yy][xx]+1)>=3) return true; int yf=w+mv[c2m(n)][0],xf=v+mv[c2m(n)][1]; if(yf==0||yf==H||xf==0||xf==W)return false; //右回りのループを検出 yy=yf,xx=xf; if(n=='U')xx--; if(n=='D')xx++; if(n=='L')yy++; if(n=='R')yy--; if(0<isVisited[yy][xx]&&turnCount.sum(nv-1)-turnCount.sum(nVisit[yy][xx]+1)<=-3&&rorlturn(n,m)==-1) return true; //左回りのループを検出 yy=yf,xx=xf; if(n=='U')xx++; if(n=='D')xx--; if(n=='L')yy--; if(n=='R')yy++; if(0<isVisited[yy][xx]&&turnCount.sum(nv-1)-turnCount.sum(nVisit[yy][xx]+1)>=3&&rorlturn(n,m)==1) return true; return false; } pair<pair<int,int>,string> DFS(const int y,const int x,const string s,const int p,const char l){ if(dfsDepth==SZ(s)){ return make_pair(make_pair(p,iabs(ygoal-y)+iabs(xgoal-x)),s); }else{ vector<pair<pair<int,int>,string> > res; for(int i=0;i<4;i++){ int yy=y+mv[i][0]; int xx=x+mv[i][1]; if(yy<0||H<yy||xx<0||W<xx) continue; if(ygoal==H&&xgoal==W&&yy<xx) continue; if(ygoal==H&&xgoal==W&&yy==xx&&i==0) continue; if(ygoal==H&&xgoal==W&&y==x+1&&i==2) continue; vector<int> tpos; string ss=s+udlr[i]; char ll=udlr[i]; if(i==0){ if(0<x) tpos.push_back((y-1)*1000+x-1); if(x<W) tpos.push_back((y-1)*1000+x); }else if(i==1){ if(0<x) tpos.push_back(y*1000+x-1); if(x<W) tpos.push_back(y*1000+x); }else if(i==2){ if(0<y) tpos.push_back((y-1)*1000+x-1); if(y<H) tpos.push_back(y*1000+x-1); }else{ if(0<y) tpos.push_back((y-1)*1000+x); if(y<H) tpos.push_back(y*1000+x); } int pp=p; for(int j=0;j<SZ(tpos);j++){ int yyy=tpos[j]/1000,xxx=tpos[j]%1000; if(nTouch[yyy][xxx]==dia[yyy][xxx]-'0') pp--; if(nTouch[yyy][xxx]+1==dia[yyy][xxx]-'0') pp++; nTouch[yyy][xxx]++; } isVisited[yy][xx]++; int oldnVisit=nVisit[yy][xx]; nVisit[yy][xx]=SZ(snake)+SZ(ss); turnCount.add(SZ(snake)+SZ(ss),rorlturn(l,ll)); if((x==0&&i==0)||(y==H&&i==2)||(x==W&&i==1)||(y==0&&i==3)){ ; }else if(ygoal==yy&&xgoal==xx){ if(2<snake.size()+ss.size()&&ans.first.first<point+pp) ans=make_pair(make_pair(point+pp,iabs(ygoal-yy)+iabs(xgoal-xx)),snake+ss); }else if(1<isVisited[yy][xx]){ ; }else{ if(!isInLoop(y,x,l,yy,xx,udlr[i],SZ(snake)+SZ(ss))){ res.push_back(DFS(yy,xx,ss,pp,ll)); } } for(int j=0;j<SZ(tpos);j++){ int yyy=tpos[j]/1000,xxx=tpos[j]%1000; nTouch[yyy][xxx]--; } isVisited[yy][xx]--; nVisit[yy][xx]=oldnVisit; turnCount.add(SZ(snake)+SZ(ss),-1*rorlturn(l,ll)); } if(SZ(res)==0) return make_pair(make_pair(-INF,iabs(ygoal-y)+iabs(xgoal-x)),""); else{ sort(res.begin(),res.end()); return res.back(); } } } string solve(void){ memset(turnCount.bit,0,sizeof(turnCount)); turnCount.add(100,1); if(H<=20){ dfsDepth=12; }else if(H<=30){ dfsDepth=11; }else if(H<=40){ dfsDepth=10; }else if(H<=50){ dfsDepth=10; }else if(H<=60){ dfsDepth=9; }else if(H<=70){ dfsDepth=9; }else if(H<=80){ dfsDepth=9; }else if(H<=90){ dfsDepth=8; }else if(H<=100){ dfsDepth=8; } point=0; FOR(i,0,H)FOR(j,0,W)if(dia[i][j]=='0')point++; memset(isVisited,0,sizeof(isVisited)); memset(nVisit,-1,sizeof(nVisit)); memset(nTouch,0,sizeof(nTouch)); ystart=0;xstart=0;isVisited[0][0]=1;nVisit[0][0]=0; yhead=1;xhead=0;isVisited[1][0]=1;nVisit[1][0]=1; ygoal=H;xgoal=W; snake="D"; ans=make_pair(make_pair(-INF,iabs(ygoal-yhead)+iabs(xgoal-xhead)),""); nTouch[0][0]=1; if(dia[0][0]=='0')point--; if(dia[0][0]=='1')point++; for(int time=0;time<MAX_ANS_LENGTH/dfsDepth/2;time++){ pair<pair<int,int>,string> res=DFS(yhead,xhead,"",0,snake[SZ(snake)-1]); if(res.first.first==-INF)break; point+=res.first.first; snake+=res.second; FOR(i,0,SZ(res.second)){ char ch=res.second[i]; if(ch=='U')yhead--; if(ch=='D')yhead++; if(ch=='L')xhead--; if(ch=='R')xhead++; isVisited[yhead][xhead]++; nVisit[yhead][xhead]=SZ(snake)-SZ(res.second)+i+1; turnCount.add(SZ(snake)-SZ(res.second)+i,rorlturn(snake[SZ(snake)-SZ(res.second)+i-1],snake[SZ(snake)-SZ(res.second)+i])); } } fprintf(stderr,"ans.first.first=%d ans.second=\"%s\"\n",ans.first.first,ans.second.c_str()); if(ans.first.first==-INF){ stringstream tss; tss<<0<<" "<<0<<" "<<snake<<endl; return tss.str(); } pair<pair<int,int>,string> fans=ans; memset(isVisited,0,sizeof(isVisited)); memset(nTouch,0,sizeof(nTouch)); memset(nVisit,-1,sizeof(nVisit)); memset(turnCount.bit,0,sizeof(turnCount.bit)); yhead=0,xhead=0; isVisited[yhead][xhead]++; nVisit[yhead][xhead]=0; FOR(i,0,SZ(fans.second)){ char ch=fans.second[i]; if(ch=='U')yhead--; if(ch=='D')yhead++; if(ch=='L')xhead--; if(ch=='R')xhead++; isVisited[yhead][xhead]++; nVisit[yhead][xhead]=i+1; if(0<i) turnCount.add(i,rorlturn(fans.second[i-1],fans.second[i])); } point=0; for(int y=0;y<H;y++) for(int x=0;x<W;x++){ nTouch[y][x]+=(isVisited[y][x]&&isVisited[y+1][x]); nTouch[y][x]+=(isVisited[y+1][x]&&isVisited[y+1][x+1]); nTouch[y][x]+=(isVisited[y+1][x+1]&&isVisited[y][x+1]); nTouch[y][x]+=(isVisited[y][x+1]&&isVisited[y+1][x]); point+=(nTouch[y][x]==dia[y][x]-'0'); } snake=fans.second+"U"; ystart=H;xstart=W;isVisited[H][W]=1; turnCount.add(SZ(snake)-1,rorlturn('R','U')); yhead=H-1;xhead=W;isVisited[H-1][W]=1;nVisit[H-1][W]=snake.size(); ygoal=0;xgoal=0; ans=make_pair(make_pair(-INF,iabs(ygoal-yhead)+iabs(xgoal-xhead)),""); for(int time=0;time<MAX_ANS_LENGTH/dfsDepth/2;time++){ pair<pair<int,int>,string> res=DFS(yhead,xhead,"",0,snake[SZ(snake)-1]); if(res.first.first==-INF)break; point+=res.first.first; snake+=res.second; FOR(i,0,SZ(res.second)){ char ch=res.second[i]; if(ch=='U')yhead--; if(ch=='D')yhead++; if(ch=='L')xhead--; if(ch=='R')xhead++; isVisited[yhead][xhead]++; nVisit[yhead][xhead]=SZ(snake)-SZ(res.second)+i+1; turnCount.add(SZ(snake)-SZ(res.second)+i,rorlturn(snake[SZ(snake)-SZ(res.second)+i-1],snake[SZ(snake)-SZ(res.second)+i])); } } fprintf(stderr,"ans.first.first=%d ans.second=\"%s\"\n",ans.first.first,ans.second.c_str()); fprintf(stderr,"snake=\"%s\"\n",snake.c_str()); if(ans.first.first==-INF){ stringstream tss; tss<<0<<" "<<0<<" "<<snake<<endl; return tss.str(); } stringstream ss; ss<<0<<" "<<0<<" "<<ans.second; return ss.str(); } class FixTheFence{ public: string findLoop(const vector<string>& __diagram){ dia=__diagram; H=SZ(dia); W=SZ(dia[0]); return solve(); } };
