Pythonのdict()が特定の入力に対し非常に遅い件について - Qiita

初めに これは競技プログラミングのために書かれた記事です。あくまでも特定の恣意的な入力に対し起こることであり、現実世界のデータを扱う際にこの事象が問題になることはほとんどないと思います。 この記事は、Codeforces Round #790 (Div. 4) の F 問題 で Python / PyPy による提出のほとんどすべてが Hack されたのをきっかけとして書かれました。 間違い等あれば気軽にコメントしていただけると助かります。 前提知識 Python の dict について Python の dict は、以下のようなコンテナ（データを収納するための構造）です。 整数や文字列、タプル等の hashable なオブジェクトを key として、それぞれに value を割り当てることができる。（value は key と異なり任意のオブジェクトが格納可能。例えば配列を value