TopCoder部【SRM437感想】

EASY 196.97/250　→　Passed

1<= int n <=1,000,000と1<= int k <=10が与えられるので、nに対して「i桁目の数字とj桁目の数字を入れ替える（i≠j、この入れ替えによって最上位の桁に0が来てはいけない）」という操作をちょうどk回行ったとき、できうる数値のうち最大の値を返しなさい。ちょうどk回行えないときは-1を返しなさい。という問題でした。


なんかもう、迷わずdp[11][1,000,001]。計算量は10×100万×6C2に見えますが実質10×100万です。余裕。
それでもスコアが200を割っているのは自分がすろーこーだーたる所以でしょう。

MEDIUM 199.08/500　→　Failed

1<= long long n <=10^18と1<= int k <=10が与えられるので、「n以上の整数で、ちょうどk種類の数字を使って構成される数（最上位の桁に0が来るのはダメ）」を返しなさい（たとえば76573だったら4種類）。という問題でした。


たとえば、n=33550336、k=4、だったら、
・33550336がk=4を満たすかどうか見る。満たしたらreturn。
・3355033X（X>6）がk=4を満たすかどうか見る。Xに関してはforで小さい順に回して、満たすものがあったらreturn。
・335503XY（X>3）がk=4を満たすかどうか見る。Xは同様に回す。Xが決まれば、k=4を満たすようにYがとれるがどうかをみたり、実際に最小となるようにYを決めるのは容易い。leading zeroとか気にする必要もないし。
・33550XYY(X>3)がk=4を満たすかどうか見る。同様（2つのYには同じ値が入るとは限らない）。
・3355XYYY(X>0)が同様。
・（中略）
・XYYYYYYY(X>3)が同様。
・ここまでで無理なら桁を増やして、XYYY……YY(X>0)がk=4を満たすかどうか見る。


を組もうとしたものの、最後のステップで桁を増やすとき、max(k,nの桁数+1)桁に増やさないといけないところを、k桁と書いてしまい、n=9999999999999999、k=2、で、10を返してしまい撃沈しました。
無理しないで1桁ずつ増やしていけばよかったものを。あーあ。

HARD　手をつけていません

CHALLENGES　+50　-0

EASYで、
「nを構成する数字に、0以外の数字が1つ以下しか含まれていなかったら-1を返す」
「貪欲に、『次の数字が最も大きくなるように入れ替える』をk回繰り返す」
という間違いを犯している人がいそうだな〜、と読んで、
「n=10000,k=3」→正しくは10000だが、-1を返すはず
「n=1099,k=2」→正しくは9910だが、1099→9091→9901を返すはず
を用意したうえで挑み、前者のミスを1つ見つけたので落としておきました。後者もあったらしいのですが見逃しました。




R：1869→1939


めざせ赤こーだー。