第一回 アルゴリズム実技検定

• アーカイブ
• 提出

リアルタイム受験した。3時間58分で全完。普段のABCよりさらに典型寄りという感じがした。

F

ソートするだけなのだが、計算量がすぐにはわからなかった。例えば単語が$k$個あるとしてヒープソートすると、新しい単語$w_i$をヒープに挿入するたびに最悪${O}(\log k)$回の単語比較が必要で、比較にかかる時間は自身の長さで抑えられるから全体で${O}((|w_1| + ... + |w_k|)\log k) \subseteq {O}(N\log N)$とわかる。最悪計算量が${O}(N \log N)$であるような比較ソート一般でもそうなるとは思うけど、よくわからない。

H

平衡二分木でシミュレーションできるのでコンテスト中はそうした。

コンテストが終わったあと考えていたが、奇数番目カードの最小値、全体の最小値、奇数番目カードのオフセット、全体のオフセットの4つを保持すれば配列だけでシミュレーションできる。

I

ABC 142 - Eとだいたい同じ問題。ゼータ変換から部分集合に関するDP(${O}(3^N+M)$)をやろうとして、これは普通のbitDP (${O}(2^NM)$)で解けることを思い出した。

J

任意の始点から与えられた3点に向かう最小費用流を求めるイメージが浮かんだが、それはなさそう。→そもそも、フローが流れる辺が重複した時にコストが2回数えられるのはまずいのでは→いや、その時は別の始点から重複なしで流したのと同じ形になっているので、最小値には影響しないはず→だったら各点から3点への最短距離を求めれば十分では？→全点からダイクストラ。

よく考えると、全点からダイクストラの代わりに3点からダイクストラで十分だった。

N

各$l, r$について、$[l-C, l]$あるいは$[r, r+C]$を空ける場合のコストを求めて比較すればよい。累積和でできるけど、これも遅延伝搬付き平衡二分木で楽をした。

O

$f(x) :=$目$x$を出したあとの操作回数の期待値、として漸化式を書き出したあと、どう更新するか迷った。$x$が最大のとき$f(x) = 0$で、$x$が小さくなるにつれて有効な項が単調に増えていくので、降順に更新していくのがよさそう。特にデータ構造は必要ないのだが、なぜかBITが必要だと思ってしまった。

---

問題が公開されたのでもう一回解きなおしたら、全体的にかなり手間取った。当日は運がよかっただけかもしれない。