TopCoder SRM 571 Div1 Easy FoxAndMp3

ああ、またやらかしてしまった。
Easyをしょうもないミスで落としたうえ、Challengeをミスってスコアマイナス。
自分はミスが多いのかTopCoder向いてないな…。AtCoderやCodeForcesの方が気が楽。
http://community.topcoder.com/stat?c=problem_statement&pm=12436

問題

数値Nが与えられる。
1.mp3、2.mp3、…N.mp3というファイル名を生成した場合、辞書順で先頭50個を答える。

解法

Nは大きいので、全部を生成するのはメモリ量的に無理。
ただ、３桁以上についてはどうせ先頭の50個しか候補にならないので、３桁以上では各桁先頭50個のうちN以下のものだけ配列に追加し、ソートすればよい。

なお、Div2 Mediumも似た問題だけど、あちらはN<=1000なので全部生成してしまえばよい。

class FoxAndMp3 {
	public:
	vector <string> playList(int n) {
		int i,j,nn=0;
		char tmp[100];
		vector<string> str,str2;
		
		for(i=1;i<=99;i++) {
			if(i<=n) {
				sprintf(tmp,"%d.mp3",i);
				str.push_back(string(tmp));
			}
		}
		
		for(j=100;j<=n;j*=10) {
			for(i=0;i<=50;i++) {
				if(j+i<=n) {
					sprintf(tmp,"%d.mp3",j+i);
					str.push_back(string(tmp));
				}
			}
		}
		
		sort(str.begin(),str.end());
		FOR(i,min(n,50)) str2.push_back(str[i]);
		return str2;
	}
};

まとめ

本番では、すぐに解法が思いついたのに実装の過程で２個もバグを作りこんでしまった。
とかくEasyでもったいないミスが多い…。