AtCoder Beginner Contest 150

　Dで混乱してEにいったらどちらも解けずに終了という散々な出来。Unratedで助かった。

コンテストへのリンク

D - Semi Common Multiple

・（入力例1の）6と10の場合を考えると、LCM+2*LCMかな？　と思う

・だが、6と8の場合を考えると答えが存在しない。2で割ったときの偶奇か、2ベキが関係するかも？

　……と、コンテスト中に考えて、どっちか分からず止まった。立式したらさらに混乱して、「拡張ユークリッドの互除法」を使うの？　などと思ってしまった。

　実際は、「2ベキが一致するとき」を考えるのが正解で、2で割っていくことで2を一つしか因数に含まない場合に帰着していけば良いのだけど、ちょっと思いつきにくい気がする……。

E - Change a Little Bit

・とりあえずソート

→Sの種類が多いので、各Sについて考えるのは無理。Cの各数が何回使われるか、もしくは使われる確率を求めよう！

→今回は、Sを[0, 0, 0](0がN個)として考えても一般性を失わないので考えやすい。

　たとえば、Nが三個のとき、
$S=[0, 0, 0]$ に対して、$T=[0, 0, 0], [0, 0, 1], [0, 1, 0], [0, 1, 1], [1, 0, 0], [1, 0, 1], [1, 1, 0], [1, 1, 1]$
　の八つ。コストが小さい数を後に使う方が良いのは明らかなので、

・index 2 の重みが何回使われるか考えると、SとTでindex 2 が異なるときの4回

・index 1 の重みが何回使われるか考えると、SとTでindex 1 が異なる四つ$[0, 1, 0], [0, 1, 1], [1, 1, 0], [1, 1, 1]$のうち、

-index 2が同じ場合$[0, 1, 0], [1, 1, 0]$は一回ずつ,
-index 2が異なる場合$[0, 1, 1], [1, 1, 1]$は二回ずつ
の計6回

・index 0 の重みが何回使われるか考えると、SとTでindex 0 が異なる四つ$[1, 0, 0], [1, 0, 1], [1, 1, 0], [1, 1, 1]$のうち、

-index 1,2が共に同じ場合$[1, 0, 0]$は一回
-index 1,2のうち一つが異なる場合$[1, 0, 1], [1, 1, 0]$は二回ずつ
-index 1,2が共に異なる場合$[1, 1, 1]$は三回
で計$1+2*2+3=8$回、のようになる

　ここで、「index 1, ... , N-1のうちi個が異なる場合」というのは二項係数を用いて表せる。
　たとえば、「index 1,2のうち一つが異なる場合」というのは、Combi(2,1)

　これを用いてまとめると、
・index 0の重みがk回使われるのは、Combi(2,k)回と書ける。

　同じようなことが一般のNやindexについて言えることが分かるので、
$(*)1*Combi(x, 0) + 2*Combi(x, 1) + 3*Combi(x, 2) + ... + (x+1) * Combi(x, x)$
　のようなものが高速で計算できれば良いと分かる。

　……と、ここまではコンテスト中に考えていて、ここからどうすれば良いかが分からず解けなかった。考えられる方針としては、

・式変形でどうにかする（OEISを使うことも視野に入れる）

・DP的な方法。$(*)$式で、x-1を利用してxを求める。

　などがあると思うけど、どういうわけかコンテスト中は二番目の方針ばかり考えてしまった。

　式変形でいけるとさえ分かれば、$Combi(x, k)=Combi(x, x-k)$なので、$(*)$式の左側からk番目と右からk番目のCombiは同じなので、まとめられる。そうすると、係数の和が同じ式になるので、

・$Combi(x, 0)+ Combi(x, 1)+ ... + Combi(x, x) =2^x$

　の公式を使って解決できる。

　式変形できないのかな？　と真面目に一分くらい考えていればいけそうだと気付いたはずなので、

・式変形できないか試す！

　のが重要なのかなぁ。

　「方針が立っていたけど解けなかったとき」が一番悔しいんだけど、そういうとき何を反省すべきかも難しい。

　なお、youtubeの公式解説では、二項係数の計算をしていないけど、それはそれで難しい気がする。

F - Xor Shift

　自力では分からず、解説を読んでACしました。

・隣り合った二項のxorを考えると、文字列アルゴリズムに帰着できる

　がポイントですね。

　色々な式変形ができるのに、あえて隣り合った二項のxorを考えるためには、文字列アルゴリズムで何ができるかが頭に入っていることが大切そう。

　公式の解説動画を見てMP法を理解しました。うーん、原理は理解できても、0から実装しろと言われたらきついアルゴリズムですね。