C - 321-like Searcher Editorial
by
physics0523
重要な観察として、 321-like Number の各桁に同じ数字が \(2\) 回以上現れることはありません。
このことから、 以下のような方針の探索ができそうなことが分かります。
- \(0\) をひとつ使うか使わないか
- \(1\) をひとつ使うか使わないか
- \(\vdots\)
- \(9\) をひとつ使うか使わないか
さらに、この選択を行った後は数字を降順に並べた場合しか考えなくてよいことも分かります。
例えば、 \(1,3,7,8\) だけを使うことにした場合、これらを降順に並べた \(8731\) しか考えなくてよいです。
また、 321-like Number は正整数なので、「何も使わない」「 \(0\) しか使わない」は禁じられ、残りの \(2^{10}-2 = 1022\) 通りの選び方に対しては 321-like Number が一意に存在します。
最初にこの \(1022\) 通りを全て試し、得ることができた 321-like Number を昇順に並べ、その \(K\) 番目を取り出して答えとすればこの問題に正解できます。
この探索は bit 全探索を使うと楽に行うことができる(実装例がその方針です)他、様々な方針で行うことができます。
但し、この問題には重大なコーナーケースが存在します。
\(9\) 桁以内の 321-like Number は \(32\) bit 符号付き整数型に収まりますが、 \(K=1022\) である場合の \(9876543210\) だけは \(32\)bit 符号付き整数型に収まりません。なので、 \(9876543210\) が収まるような整数型を使うか、場合分けによってこのケースを処理するかする必要があります。
実装例 (C++):
#include<bits/stdc++.h>
using namespace std;
int main(){
vector<long long> ans;
for(int i=2;i<(1<<10);i++){
long long x=0;
for(int j=9;j>=0;j--){
if(i&(1<<j)){
x*=10;
x+=j;
}
}
ans.push_back(x);
}
sort(ans.begin(),ans.end());
int k;
cin >> k;
cout << ans[k-1] << "\n";
return 0;
}
posted:
last update: