HHKBプログラミングコンテスト2022 Winter(AtCoder Beginner Contest 282)

 　Fまで六完。

コンテストへのリンク

コンテスト後のツイート

HHKBプログラミングコンテスト2022 Winter(AtCoder Beginner Contest 282) Fまで。Gは解説と同じDPを考えていたはずなのだが答えが合わなかったし計算量削減もできなかった。
D 連結部分をUnion-findで結んで、DFSで01に塗りわけ。同じ連結成分で同じ色ならダメ。
E 最大全域木
F スライド最小値

— titia (@titia_til) December 17, 2022

　ツイートの「スライド最小値」は「Sparse table」の間違いです。

G - Similar Permutation

　解説AC。

　コンテスト中に、この問題の解説を見直し、同じようなDPをするしかないな、と思い、それを累積和か何かで高速化するんだろう、とは思った。

　ただ、高速化の方針が分からず、とりあえず計算量を無視して書いてみたが答えが合わず終了。

　答えが合わなかったのは添え字のミスで、自分のコードを見れば二次元累積和を使えることは分かった。考えていたときは、それでも計算量五乗になってしまい間に合わないと思っていたが、（解説および）自分のコードを見たら四乗にできることが分かった。

　正しい方針を思い付いているのだから、解き切らないと。

Ex - Min + Sum

　解説放送を見てAC。

　Cartesian Treeという単語は知らなかったけれど自然な解法ですね。計算量解析の部分はちょっと難しいですが。

　ただ、Cartesian Treeを使って分割統治する方針だと自分の実装だと通らず、

import pypyjit

pypyjit.set_param('max_unroll_recursion=-1')

　というおまじないを書いて通りました。この高速化を書いたの初めてです。