これ本当に(条件内で)どんな入力でもTLEしないのかな…。
https://yukicoder.me/problems/no/775
問題
1~99の間であるN個の整数が与えられる。
これらを並べ替えて連結して生成できる数値のうち、大きな順にK個を出力せよ。
ある数値が複数の並べ方で生成できても、それは1回しかカウントしない。
解法
指定通り、大きい順に作っていくことを考える。
ただDFSを行うと探索空間が広すぎるので、BFS風に徐々に探索していこう。
さて、並びはどうでも最終的な桁数は一致するので、途中まで並べた時点でprefixが大きな数値は最終的に大きくなる。
よって頭から順に数値を決めていき、(確定したprefix, 残された利用できる数値の集合)を状態としてpriority_queueを使い、探索していく。
同じ状態は複数回探索しないことで計算時間を削減していく。
その際、prefixとして0-9を反転した文字列を使い、かつ比較関数にlessではなくgreaterを使うとpriority_queueで数値を大きい順に取り出せる。
アルゴリズムとしてはこれでも解けるが、まだTLEする。
1桁の値とそのぞろ目について、並べ方が何通りもあるのでそこは枝刈りしよう。
1桁の値またはゾロ目を計2ケタ以上並べるときは、あとの自由度を考えるとゾロ目を先に使っておくのがよい。
直前で1桁の数値を使った場合、その直後に同じ数字のぞろ目を使わないようにしておこう。
int N,K; string S[101]; set<pair<string,vector<int>>> memo; void solve() { int i,j,k,l,r,x,y; string s; FOR(i,100) { S[i]=to_string(i); FORR(c,S[i]) c=(9-(c-'0'))+'0'; } cin>>N>>K; vector<int> L(100); int ML=0; FOR(i,N) { cin>>x; L[x]++; ML+=S[x].size(); } priority_queue<tuple<string,vector<int>,int>,vector<tuple<string,vector<int>,int>>,greater<tuple<string,vector<int>,int>>> PQ; PQ.push({"",L,-1}); while(K) { string cur=get<0>(PQ.top()); vector<int> V=get<1>(PQ.top()); int pre=get<2>(PQ.top()); PQ.pop(); if(cur.size()==ML) { FORR(c,cur) c=(9-(c-'0'))+'0'; cout<<cur<<endl; K--; continue; } for(i=10;i<100;i++) { if(i%11==0 && V[i/11]) { string cur2=cur; if(i==pre*11) continue; for(x=1;x<=V[i]*2+V[i/11];x++) { int p1=V[i],p11=V[i/11]; cur2+=S[i/11]; r=min(V[i],x/2); V[i]-=r; V[i/11]-=(x-r*2); if(memo.count({cur2,V})==0) { PQ.push({cur2,V,i/11}); memo.insert({cur2,V}); } V[i]=p1; V[i/11]=p11; } } else if(V[i]) { V[i]--; if(memo.count({cur+S[i],V})==0) { PQ.push({cur+S[i],V,i}); memo.insert({cur+S[i],V}); } V[i]++; } } } }
まとめ
シンプルな設定ながら状態の持ち方が難しい。