No.3040 Aoiスコア
自力AC。
DPを考えていたがうまくいかず、三頂点のpathなら列挙できると気付きAC。
結構苦戦した。眠りに落ちる前に一度解けたと思ったが、そのときはDPを考えており、それではダメだった。
No.3041 非対称じゃんけん
解説AC。
bitsetの利用は考えたけれど、bit_countの部分が速くならないためダメだと思ってしまった。その部分も1/64になるんでしょうか？
PyPyではTLEだったけれどPythonだとAC。
No.3042 拡大コピー
自力AC。
こういう問題で重心を考えるのは定石ですね。
No.3043 括弧列の数え上げ
苦労したが自力でAC。
括弧列の個数がカタラン数であることは分かっているので、calc(x):長さxの括弧列Sのf(S)の総和を、最初の(と何番目のindexが対応するかで場合分けして計算した。
一番外側で"("と")"が対応している長さxの括弧列Sたちのf(S)の総和は、長さx-2の括弧列たちの総和に、その個数*(x-2)/2（閉じカッコの数）だけ足したものとなることを利用した。
難しかったし、解説の方法も簡単ではない気がするのだが、AC人数を見ると解けなくてはいけない問題だったのか。
No.3044 よくあるカエルさん
自力AC……と言っていいのかな。
「すごろくであるマスに止まる確率」と検索したら、DPで求められるということが出てきて、それなら行列累乗で求められると気付いた。
検索しないとDPと気付かなかったのは良くない。
No.3045 反復重み付き累積和
解説AC。
解説を参考にしたけど、行列ベースで考えていた。
長さ4の数列A（1*4の行列として見ている）に対して、重みkの累積和を一回取る操作は、
1 k k^2 k^3
0 1 k k^2
0 0 1 k
0 0 0 1
という行列を右からかけることに対応している。
このx乗がどうなるかというと、実験すると、これらのk^nなどのところに、Combi(n+x-1,x)という二項係数を掛け合わせたものになる。
のだが、これだと三乗になってTLE。
解説を見ると、この行列計算はFFTで計算できるらしい。
それを見てAC。
行列計算のうち、どのようなものが形式的ベキ級数的に表せるのかを知っていると良いのかもしれない。
0 件のコメント:
コメントを投稿