yukicoder contest 235

　遅解きの五完でした。五問目でC++を使ったのが遅くなった原因ですね……。慣れない言語を使うと、そんなに上手くいかなくても達成感があります。良いのか悪いか。

コンテストへのリンク

No.975 ミスターマックスバリュ

　MaxValuは知っていたけど、ミスターマックスは聞いたことなかった。そんな店があるんですね。

No.976 2 の 128 乗と M

　Pythonだとpow(2,128,M)と書けるので楽。

　多倍長を扱える（し、128乗ならたいして大きくない）ので、$2^{128}$を実際に計算することもできます。

No.977 アリス仕掛けの摩天楼

　全体が連結な場合、Bobが必勝なことは分かったけど、それ以外の条件を探すのに苦労した。まあ、こういう問題は試行錯誤するしかなさそう。

No.978 Fibonacci Convolution Easy

　数列aの値を求めておき、累積和をとりつつ和を求めていく。

No.979 Longest Divisor Sequence

　DP[a]で、最後にaを使ったときの、Divisor Sequenceの最長の長さ、として、iを一つずつ更新していった。毎回約数列挙が必要になるけど、各$A_i$の値が小さいので、$O(N*\sqrt{A_i})$で収まる。

　Aが小さいのでこの方針でやりましたが、解説のようにDP[index]とした方が普通だったかも……。

　なお、コンテスト中はPyPyで通すことができず、C++を使って通しました。

　が、予め、エラトステネスの篩の要領で$3*10^5$までの約数を列挙を列挙しておくとPyPyで通せた模様。勉強になりました。

No.980 Fibonacci Convolution Hard

　主にけんちょんさんのブログの記事を参考に解説AC。kmjpさんの記事やmaspyさんの解説も参考になりました。

　形式的ベキ級数や母関数を理解したとは言い難いですが、少し使い方が分かったのは良かった。勉強になりました。