Codeforces Round #790 (Div. 4)

　全完。やっぱり全完できるコンテストは楽しいですね。

コンテストへのリンク

コンテスト後のツイート

Codeforces Round #790 (Div. 4)
A 実装
B 各A[i]-min(A)
C 全探索
D 全マスに置いてみる
E 大きい順にソートして累積和取って二分探索
F Counter
G 木DP。大きいindexから順にやれる。（トポロジカルソートの逆になっているので）
H BITで。

— titia (@titia_til) May 10, 2022

　などと気楽に書いていたらFがHackされてしまった。

　一ヶ月くらい前に、「PythonのsetでHash衝突させることができる」ということがCodeforcesのブログに投稿されたようで、それを利用したものだった。（ツイッターでtomerunさんに教えてもらいました。ありがとうございます！）

　（このブログにも書いてあるように）C++のunordered_setのハッシュを衝突させる方法の作成方法は以前から知られていたが、それと同じ問題がPythonでも知られた、ということの模様。

　今のところ私は、setなどを使う場合は、randomな自然数xを一つ取り、aの代わりにa+xを使うという方法を考えている。（a^xと違い、これなら順序関係が崩れないため）

　これで大体安全だと思うが、どうだろう。