1. 問題
 年齢 (1~99) を表すデータが与えられて、それらを昇順でソートしろ。
 なお、データ数は2000000まで。利用できるメモリ上限は2MBまで。

2. 考え方
 問題自身は簡単だが、使用できるメモリは2MBしかないので、サイズ100の(int型)配列だけを用意し、入力データのそれぞれの度数をそこに入れておく(足していく)。
 配列に記録されているそれぞれのindexを、配列の先頭からprintf()すればOKになるはず。

3. 例
 たとえば、入力

に対して、各データの度数を表す配列は
 a[1]=0, a[2]=0, a[3]=2, a[4]=1, a[5]=2, a[6]...a[99]=0
になり、配列の先頭から、3, 3, 4, 5, 5 とそれぞれの存在している要素のindexだけを表示する。

4. 感想
 1回目の提出では実行時間が1.020秒。入出力にscanf()、printf()を使ったせいだと思う。それらをgetchar(), putchar()に直して、2回目に提出して、0.450秒になった。1位との差はまだまだだが、一応これでおしまい。もっと早くするには、fread(), fwrite()を使うようだが、めんどくさい。

スピードをそれほど望まなければ、難しい問題ではないが、メモリ上限に気を配るべきだろう。

Comments are closed.

Post Navigation