結構苦戦したけど、終わってみれば解法はシンプルだし高速きたまさ方よりはだいぶラク。
http://yukicoder.me/problems/536
問題
１辺の長さ１の正三角形を組み合わせて作った、１辺の長さNの正三角形を考える。
これらの辺で構成される単純多角形の閉路の数を求めよ。
解法
まず前提として、この問題は最大でもN=12までしかないため手元で計算して埋め込みで通す。
Writer解で2分、自分のコードで4分なので埋め込みでちょうどいい時間。
Editorialの記載はシンプルすぎて理解するのにちょっときついので、writer解のコードを自分なりに解釈して書き直したものを説明する。
点(r,c)は下からr段目、左からc列目の点とする。(左下が(0,0)、右下が(0,N)、上が(N,N)となる)
まずこれらに左下から始まり右方向に連番をふる。
(0,0)→0、(0,1)→1、(0,N)→N、(1,0)→N+1…(r,c)=c+r*(N+1)-r*(r-1)/2とする。
この連番の順でメモ化再帰をしていき、どこの隣接点と連結させるかを決めていく。
左下から順に決めていくので、(r,c)以降をどこと連結させるかを決める際は、同じ段の左側( (r,0)-(r,c-1))及び一つ下の段の右側( (r-1,c)-(r,N-r))しか影響を受けない。
それ以前の頂点は、すでに確定済みの頂点としか隣接せずこれ以上連結状態は変化しないので、メモ化再帰の際状態として持つ必要はない。
まとめると、(r,c)の連結状態を定めるメモ化再帰では、( (r,0)-(r,c-1)及び(r-1,c)-(r-1,N-r+1))の連結状態を元に処理を進める。
(Writer解の「前 N+1 頂点ぐらいがどのように連結しているかを状態にして」の記載はここに相当する)
閉路が完成したら処理は終了するので、途中の過程ではいくつか閉じていないパスが存在することになる。
( (r,0)-(r,c-1)及び(r-1,c)-(r-1,N-r+1))が持つべき状態は、以下の何れかである。
- この頂点はどのパスにも含まれない。
- この頂点はどれかのパスの途中である。この頂点はこれ以上他頂点と連結できない。
- どこかのパスの両端の片方である。その場合パスを一意に示す番号を持つ。この頂点は他頂点と連結して、パスの終端を延長するか、もしくは閉路を形成できる。
メモ化再帰の過程で、(r,c)は処理済みの隣接頂点(左・左下・右下)のうち最大2箇所まで連結を試みることができる。
よって連結の仕方を６通り総当たりしよう。
(r,c)と連結対象の頂点(y,x)は、それぞれ状態に対して以下のように遷移する。
- どちらかがパスの途中である場合、それ以上連結できないので連結失敗。
- どちらもパスに含まれない場合、その２点を両端とする新たなパスを作る。
- どちらか片方がパスの終端である場合、パスの終端を延長する(元終端だった頂点はパスの途中になる)
- どちらもパスの終端だった場合：
- 両終端が同じパスの終端だった場合、そこを結ぶと閉路が成立する。ほかに残ったパスが無ければ、問題文の条件を満たす閉路が成立する。
- 両終端が異なるパスの終端だった場合、そこを結ぶと２つのパスが連結する。よってUnion-Findの要領でそれらのパスを同一のものと見なす。
連結失敗及び閉路成立が成されなければ、続けて(r,c+1)のメモ化再帰をしていく。
なお、(r,c+1)のメモ化再帰を行う際は上述の通り(r-1,c)の状態は忘れて良い。
ただし(r-1,c)がどこかのパスの終端である場合、以後永遠にその終端は閉じることはなくなるのでメモ化再帰は失敗させなければならない。
この問題は64bit値を超える場合がある。
Writer解は多倍長整数型を準備して解いているが、自分は10^9前後の4種類の素数における剰余環の中で解を求め、あとでPythonを使って中国人剰余定理で解を求めている。
/* int N; ll momo[4]={1000000007,1000000009,1000000021,1000000033}; typedef pair<pair<ll,ll>,pair<ll,ll> > pllll; map<ll,pllll> memo[200]; int id(int x,int y) { return x+y*(N+1)-(y-1)*y/2;} ll calchash(deque<int> v) { ll h=0; FORR(r,v) h=h*9+(r+2); return h; } int conn(deque<int>& pre,int id) { // ２点を連結 if(pre[0]==-2 || pre[id]==-2) return 0; // 既に２点連結済み if(pre[0]==-1 && pre[id]==-1) { pre[0]=pre[id]=N+1; // 相互連結、新規パス生成 return 1; } else if(pre[0]==-1) { // 0をidに連結 pre[0]=pre[id]; pre[id]=-2; return 1; } else if(pre[id]==-1) { // idを0に連結 pre[id]=pre[0]; pre[0]=-2; return 1; } else if(pre[0]==pre[id]) { //同じグループの終端 // 他グループの終端があるか？ pre[0]=pre[id]=-2; FORR(r,pre) if(r>=0) return 0; return 2; // 閉路完成 } // 異なるパスの終端同士連結 int tid=pre[id]; FORR(r,pre) if(r==tid) r=pre[0]; pre[0]=pre[id]=-2; return 1; } void regroup(deque<int>& pre) { // 残ったパスを0からまた連番にする int x=0; map<int,int> m; FORR(r,pre) if(r>=0) { if(!m.count(r)) m[r]=x++; r=m[r]; } } pllll gogo(int y,int x,deque<int> pre) { pllll ret={{0,0},{0,0}}; if(x>N-y) y++,x=0; if(y>N) return ret; while(y&&pre.size()>(N+2-y)) { if(pre.back()>=0) return ret; pre.pop_back(); } int myid = id(x,y); ll h=calchash(pre); if(memo[myid].count(h)) return memo[myid][h]; int i,j,pat,res; pre.push_front(-1); FOR(pat,7) { // 3方向連結はないので0-6まで deque<int> cur=pre; int fin=0; if(pat&1) { // 左連結 if(x==0) continue; res = conn(cur,myid-id(x-1,y)); if(res==0) continue; if(res==2) fin=1; regroup(cur); } if(pat&2) { // 左下連結 if(y==0) continue; res = conn(cur,myid-id(x,y-1)); if(res==0) continue; if(res==2) fin=1; regroup(cur); } if(pat&4) { // 右下連結 if(y==0) continue; res = conn(cur,myid-id(x+1,y-1)); if(res==0) continue; if(res==2) fin=1; regroup(cur); } if(fin) { // 閉路完成 ret.first.first++; ret.first.second++; ret.second.first++; ret.second.second++; } else { // 次の頂点へ auto r = gogo(y,x+1,cur); ret.first.first +=r.first.first ; ret.first.second +=r.first.second ; ret.second.first +=r.second.first ; ret.second.second+=r.second.second; } } pre.pop_front(); ret.first.first %=momo[0]; ret.first.second %=momo[1]; ret.second.first %=momo[2]; ret.second.second%=momo[3]; return memo[myid][h]=ret; } */ void solve() { int i,j,k,l,r,x,y; string s; /* for(i=1;i<=12;i++) { N=i; _P("%d :",i); FOR(x,200) memo[x].clear(); auto r = gogo(0,0,deque<int>()); _P(" %lld %lld %lld %lld\n",r.first.first,r.first.second,r.second.first,r.second.second); } */ /* 上記コメントアウト欄のコードを実行すると下記の出力が得られる。 1 : 1 1 1 1 2 : 11 11 11 11 3 : 110 110 110 110 4 : 2402 2402 2402 2402 5 : 128967 128967 128967 128967 6 : 16767653 16767653 16767653 16767653 7 : 436906633 436906623 436906563 436906503 8 : 952701106 952692294 952639422 952586550 9 : 657618983 639979715 534144107 428308499 10 : 622300340 963605721 11445252 59297272 11 : 509031918 989378757 959195292 79415546 12 : 650337412 967055801 137335159 913160201 CRTで上記解から多倍長整数値を求めるpythonコード 上の処理で出てきた4つの数字A～Dを以下のように並べて食わせる A 1000000007 B 1000000009 C 1000000021 D 1000000033 def ext_gcd(p,q): # px+qy=gcd if q==0: return (p,1,0) (g,y,x) = ext_gcd(q, p%q) return (g,x,y - (p//q)*x) def crt(a1,mo1,a2,mo2): # return (x,y) y=lcm(a1,a2),x%mo1=a1,x%mo2=a2 g,x,y=ext_gcd(mo1,mo2) a1%=mo1 a2%=mo2 if a1%g != a2%g: return (-1,0) lcm=mo1*(mo2/g) return ((a1+((a2-a1)%lcm)*x%lcm*(mo1/g)) % lcm,lcm) import sys x=0 y=1 for line in iter(sys.stdin.readline, ""): A,B=map(int,line.split(" ")) (x,y)=crt(x,y,A,B) print x,y */ string rets[12]={ "1", "11", "110", "2402", "128967", "16767653", "5436906668", "4406952731948", "8819634719356421", "43329348004927734247", "522235268182347360718818", "15436131339319739257518081878", }; cin>>x; cout<<rets[x-1]<<endl; return; }
まとめ
ちょっとWriter解説が不親切すぎる気もしますが、コードから読み解けということですかね…。
