みんなのプロコン 2018 決勝 : B - 経路が色々

こういう構築ゲーは苦手。
https://beta.atcoder.jp/contests/yahoo-procon2018-final-open/tasks/yahoo_procon2018_final_b

問題

正整数Kが与えられる。
100*100以下の２次元グリッドのうち、白黒で塗り分けた際、左上マスから右下マスまで右または下の白マスだけを辿っていく経路がK通りとなるものを構築せよ。

解法

こういう問題では、同じ構造を鎖状につなげて２の累乗通りを表せるようにするのが定石である。
ただ、Editorialに従うと、この問題では３の累乗を連結させる手段が取れる。

以下の基本構造を考えると、左上から左下に移動する経路は１通りで、右下に移動する経路は３通りである。

...
...
.#.

よってこの構造を右下方向に連結すると３の累乗通りは容易に構築できる。

...
...
.#...
  ...
  .#...
    ...
    .#.

そこで、まずこの構造を40個ほどつなげると、最大3^40までの組み合わせが構築でき、Kの上限をカバーできるようになる。
あとはKを３進数表記し、各桁で1,2になるケースでは左下から右下に直結するバイパスを作ろう。
(その桁が2なら、バイパスの途中で1回分岐を作り2倍させる)

ll K;
string S[101];


void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>K;
	FOR(y,100) S[y]=string(100,'#');
	FOR(i,40) {
		if(K%3>=1) for(j=i*2;j<100;j++) S[i*2][j]='.';
		if(K%3>=2) for(j=i*2;j<100;j++) S[j][i*2]='.';
		S[i*2][i*2]=S[i*2][i*2+1]=S[i*2][i*2+2]='.';
		S[i*2+1][i*2]=S[i*2+1][i*2+1]=S[i*2+1][i*2+2]='.';
		S[i*2+2][i*2]=S[i*2+2][i*2+2]='.';
		K/=3;
	}
	
	FOR(x,100) S[99][x]=S[x][99]='.';
	
	cout<<"100 100"<<endl;
	FOR(y,100) cout<<S[y]<<endl;
	
}

まとめ

本番とっさに思いつく気がしない…。