計算量を落とそうとしたらTLEした話
ABC265-Eにて、無理やり計算量を落とそうとしたら、TLEしたので、注意喚起も含め、記事にします。
↓問題
やろうとしたこと
まずはコードをご覧ください。(75行目からmain関数)
だめだったコード(TLE)
うまくいったコード(AC)
はい。やりたかったことは、障害物のある部分を$${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するからよかったよね。(反省)
以上、無駄に計算量を落とそうとしてTLEした話でした。
ちなみに、無駄に落とそうとしていなければ(最初からset<pair<int,int>>でやっていれば)、初回提出時に水上位～青パフォ取れていました。
悲しいね。