Good Bye 2023 : D. Mathematical Problem

ついに2023年が終わる…。
https://codeforces.com/contest/1916/problem/D

問題

奇数Nが与えられる。
以下を満たす整数N個を答えよ。

• いずれもN桁である。
• いずれも平方数である。
• 各桁の数字のmultisetが一致する

解法

自分は以下のように解いた。

• Nが11以下の場合
  • 11桁以下の平方数を列挙しておき、N桁の平方数のうちmultisetが一致するN個を選ぶ。
• Nが12以上15以下の場合
  • 31*31=961、13*13=169、14*14=196なので、これらにあと0を加えてできる値をN個作る。
• Nが16以上
  • 1000100100のように1が3か所ある整数の平方数を取ると、1が3つ、2が3つ登場する。

int T;
ll N;

map<string,vector<ll>> S[17];

void solve() {
	int i,j,k,l,r,x,y; string s;
	
	for(ll a=1;a<=400000;a++) {
		ll b=a*a;
		string V=to_string(b);
		sort(ALL(V));
		S[V.size()][V].push_back(b);
	}
	
	
	cin>>T;
	while(T--) {
		cin>>N;
		
		if(N<=11) {
			FORR2(a,b,S[N]) if(b.size()>=N) {
				FOR(i,N) cout<<b[i]<<endl;
				break;
			}
		}
		else if(N<=15){
			int lef=N;
			for(x=N-1;x>0;x-=2) if(lef) {
				string S=string(N,'0');
				S[0]='1';
				S[x]='9';
				S[x/2]='6';
				lef--;
				cout<<S<<endl;
			}
			string S="196"+string(N-3,'0');
			lef--;
			cout<<S<<endl;
			for(x=N-1;x>0;x-=2) if(lef) {
				string S=string(N,'0');
				S[0]='9';
				S[x]='1';
				S[x/2]='6';
				lef--;
				cout<<S<<endl;
			}
			assert(lef==0);
		}
		else {
			int lef=N;
			for(x=2;x<=N-2;x+=2) for(y=x+2;y<=N-2;y+=2) {
				if(lef==0) break;
				if(x*2==y) continue;
				string S=string(N,'0');
				S[0]=S[x]=S[y]='1';
				S[x/2]=S[y/2]=S[(x+y)/2]='2';
				cout<<S<<endl;
				lef--;
			}
			assert(lef==0);
		}
		
		
		
		
	}
}

まとめ

色々解法がありそう。