AtCoder Beginner Contest 230

　Fまで六完。

コンテストへのリンク

コンテスト後のツイート

AtCoder Beginner Contest 230 Fまで六完。
D 区間スケジューリング
E ルートNで分ける
F 累積和Sを計算。和が0の区間があれば前の方を採用したい。たとえばS[3]=S[6]なら、DP[2]はDP[6]には加えない。もらうDPにしてセグ木で高速化。

— titia (@titia_til) December 3, 2021

G - GCD Permutation

　解説放送を見てAC。

　gcdが0でないということは、何かの倍数になっているということ。なので、2の倍数の項たち、3の倍数の項たち、4の倍数の項たち、5の倍数の項たち、6の倍数の項たち、……それぞれについて答えを求めることを考える。

　この際、4の倍数の項たちは2の倍数の項たちを計算するときに既に足されているし、6の倍数の項たちは、2の倍数の項たち及び、3の倍数の項たちを計算するときに既に足されている。

　なので、答えを求めた後、適切な係数を掛ける必要がある。

　これは、エラトステネスの篩風にやれば求めることができる（なお、この係数をメビウス関数と呼ぶらしい）

　次に、Pの方を見よう。2の倍数の項たちP[2], P[4], ...について、gcdが0でないものが何組あるか数えたい。

　これも同じ方法を使えばできる。

　……と書くと、まあそうか、という感じなのだが、コンテスト中はこの二回目も同じ方法が使えるということが思いつかなかった。

　前半パートと後半パートで同じ方法を使う自然な問題なんだけど、なぜか逆に盲点になってしまった。

　約数を扱う問題で斬新な手法を問われることはあまりなくて、いかに高速化（特に、エラトステネスの篩を使うことが多い）できるかが重要、というのが最近感じている印象です。