487-3279(3)

大きな値は回避できる

65535を超える解があるとき、それを保持する変数はint型が一つだけあれば良い。なぜならインプットの最大数が100000個なのだから。
すなわち、int型の変数を事前に一つだけ用意しておき、重複する番号をカウントする時に一つ条件分岐を入れる。―たとえば、カウントが50000を超えたらインクリメントする変数を切り替えるような仕組みだ。これでメモリ制限は容易に回避することが出来る。しかしその分コードの長さを犠牲にしなければならない。

・・・unsigned shortではなく、signed short, unsigned char, signed char...この辺りは使えないのか？目標は最短コードだ。私は迷わずchar型を選んだ。最大127。100000個のインプットで、128個以上重複する可能性は十分考えられるのだが、前回書いたように乱数でデータを作るのであれば、確率的に*1難しいのではないか、そう思ったのだ。確率的に難しいから、あえて偏った(65536以上の)データを作るのだ!

うだうだ考えてるよりやってみよう、とコードを書いてSubmitすると、通ったT-T
うっひょ〜!!!

つづく。

*1:実際には確率的というより、私の直感。ちゃんと計算してないし^^;