TLEの時は最適化しろ
自分、最近は競技プログラミング（AtCoder）に参加しているのです。
昨日ABCに参加して、C問題で詰まったのでメモ。
問題はこんな感じ。
あなたは、joisinoお姉ちゃんと以下のようなゲームをしています。
- 最初、何も書いていない紙がある。
- joisinoお姉ちゃんが一つの数字を言うので、その数字が紙に書いてあれば紙からその数字を消し、書いていなければその数字を紙に書く。これを 回繰り返す。
- その後、紙に書かれている数字がいくつあるかを答える。
joisinoお姉ちゃんが言った数字が、言った順番に として与えられるので、ゲーム終了後に紙に書かれている数字がいくつあるか答えてください。
で、私が考えたプログラムは以下の通り（言語は全てjava）。
１．０から９億９９９９万９９９９までの数字に対応したboolean型の配列を用意し、
数字が読み込まれるたびに論理値を切り替える。
結果：Runtime Error
ちょっと考えれば至極当たり前の話。こんなアルゴリズムではメモリがいくらあっても足らない。
２．ArrayListのインスタンスを用意し、数字が読み込んだ時リスト内に数字があればそれを消去し、なければリストにその数字を追加する。
結果：Time Limit Exceeded
なかなかいい案だと思ったが、テストケースの最後の２個がTLEとなってしまった。
ここからすごく時間をかけた。forループを減らしたりアルゴリズムを変えたりしたがどうしてもTLEが解消されない。
数十分考えた後に考えた結果、「ArrayListをもっと高速化できないか？」ということだった。
「ArrayList 高速化」ググってみると・・・トップにこんなブログが見つかった。
要するにArrayListよりHashSet使った方が処理がとても早くなるよ、ということだった。なので早速プログラムに組み込むことにした。ArrayListの宣言をHashSetに変えるだけでOK。メソッドの変更も不要だった。
そしてプログラムを提出すると・・・あっさりとAcceptedになった。
TLEの時はアルゴリズム自体は正しいんだから、処理に時間がかかってる部分を見つけて修正するとか、検索してより高速なクラスを使用するといったことが必要だと学んだ。
TLEの時に下手にアルゴリズムを変更してもあまりいい結果にはならないということだ。
