計算量を落とそうとしたらTLEした話

ABC265-Eにて、無理やり計算量を落とそうとしたら、TLEしたので、注意喚起も含め、記事にします。
↓問題

E - Warp

やろうとしたこと

まずはコードをご覧ください。(75行目からmain関数)

だめだったコード(TLE)

Submission #34235712 - AtCoder Beginner Contest 265

うまくいったコード(AC)

Submission #34248779 - AtCoder Beginner Contest 265

はい。やりたかったことは、障害物のある部分を$${O(1)}$$で判定することです。

具体的には、

// TLE
unordered_map<int,unordered_map<int,bool>> ng;

のようにすることで、$${ng[x][y]}$$でフラグ管理をし、存在するかを$${O(1)}$$で取得できると考えました。

実際はこんな高速化は必要なく set<pair<int,int>> で十分だったので、非常に無駄な時間を費やしたわけです。

なぜこのようにしたか

unordered_set/map はhash関数が定められている型のみをキーとして利用できます。つまり、

unordered_set<pair<int,int>> ng;// Compilation Error

はpair型のhash関数が定義されていないため、使えません。
なのでネストしちゃえ！となりました。

敗因

$${ng[x][y]}$$で取得する際に、その要素が存在しなくても生成されてしまいます。
その結果、毎回のループで$${ng[x][y]}$$が存在しない場合に要素が生成され続け、致命的に遅くなってしまったのです。

結論

unordered_mapを配列のようにフラグ管理に使うのはやめよう。
どうしても使うとするならば、.count()を使うことで要素が生成されないようにしよう。

でもそれをやるなら

unordered_map<int,unordered_set<int>> ng;

にして突っ込んでいけばcountするからよかったよね。(反省)

Submission #34253170 - AtCoder Beginner Contest 265

以上、無駄に計算量を落とそうとしてTLEした話でした。

ちなみに、無駄に落とそうとしていなければ(最初からset<pair<int,int>>でやっていれば)、初回提出時に水上位～青パフォ取れていました。
悲しいね。