#1187914 (C++23) No.3740 Troublesome Congestion

• 問題: No.3740 Troublesome Congestion
• ユーザー: uruzunyaa
• 提出日時: 2026-09-19 07:38:33
• 言語: C++23 (gcc 15.3.0 + boost 1.92.0 + ACL)
• 結果: AC
• 実行時間: 4 ms / 2,000 ms
• コード長: 2,364 bytes
• コンパイル時間: 2,242 ms
• コンパイル使用メモリ: 355,564 KB
• 実行使用メモリ: 9,996 KB
• 最終ジャッジ日時: 2026-09-19 13:28:44
• 合計ジャッジ時間: 4,114 ms
• ジャッジサーバーID （参考情報）: judge6_0 / judge1_0

サブタスク	配点	結果
部分点1	20 %	AC * 7
部分点2	30 %	AC * 12
満点	50 %	AC * 26
合計	4 * 100% = 400 点

ソースコード

//#pragma GCC optimize("O3")
#include<bits/stdc++.h>
using namespace std;

#define ll long long
#define rep(i,n) for (ll i=0;i<(ll)(n);i++)
#define rrep(i,n) for (ll i=(ll)(n)-1;i>=0;i--)
#define loop(i,m,n) for(ll i=(m);i<=(ll)(n);i++)

void solve(){
	ll M;
	cin>>M;

	const ll N=40;
	vector<string> ans(N,string(N,'#'));

	// 本線
	// -2 <= i-j <= 3 の斜め帯を作る。
	// 右下では合流路と干渉しないように途中で切る。
	rep(i,N){
		rep(j,N){
			if(-2<=i-j && i-j<=3 && i+j<=72){
				ans[i][j]='.';
			}
		}
	}

	// 本線内で、(0,0) から各マスまでの最短経路数を求める。
	vector<vector<ll>> dp(N,vector<ll>(N,0));
	dp[0][0]=1;

	rep(i,N){
		rep(j,N){
			if(i==0 && j==0)continue;
			if(ans[i][j]=='#')continue;

			if(i>0)dp[i][j]+=dp[i-1][j];
			if(j>0)dp[i][j]+=dp[i][j-1];
		}
	}

	// {その出口を使ったときに増える経路数, 出口座標}
	vector<pair<ll,pair<ll,ll>>> exits;

	// 上側の出口候補
	// 本線境界 (i,i+2) の右隣 (i,i+3)
	rep(i,36){
		exits.push_back({
			dp[i][i+2],
			{i,i+3}
		});
	}

	// 下側の出口候補
	// 本線境界 (j+3,j) の下隣 (j+4,j)
	rep(j,35){
		exits.push_back({
			dp[j+3][j],
			{j+4,j}
		});
	}

	sort(exits.begin(),exits.end());

	// 各重みまでの部分和で、隙間なく全整数が作れることを確認。
	ll sum=0;
	for(auto [v,p]:exits){
		assert(v<=sum+1);
		sum+=v;
	}

	assert(sum==1406601707949008441LL);
	assert(M<=sum);

	// 上側出口からゴールへ向かう合流路
	//
	// (i,i+3) が出口。
	// (i,i+4) -> (i,i+5) -> (i+1,i+5) -> ...
	rep(i,36){
		ans[i][i+4]='.';
	}
	rep(i,35){
		ans[i][i+5]='.';
	}

	// 右端へ接続
	loop(i,35,39){
		ans[i][39]='.';
	}

	// 下側出口からゴールへ向かう合流路
	rep(j,35){
		ans[j+5][j]='.';
	}
	rep(j,34){
		ans[j+6][j]='.';
	}

	// 下端へ接続
	loop(j,34,39){
		ans[39][j]='.';
	}

	// M を出口の重みの部分和として表す。
	// v_k <= 1 + sum_{i<k} v_i なので、大きい順の貪欲でよい。
	rrep(i,exits.size()){
		ll v=exits[i].first;

		if(v<=M){
			M-=v;

			ll x=exits[i].second.first;
			ll y=exits[i].second.second;

			ans[x][y]='P';
		}
	}

	assert(M==0);

	cout<<N<<endl;
	rep(i,N){
		cout<<ans[i]<<endl;
	}
}

int main(){
	ios::sync_with_stdio(false);
	cin.tie(nullptr);

	ll T;
	cin>>T;

	rep(_,T){
		solve();
	}
}