Codeforces #309 Div.2 <失敗談>

今回はレートが回復したのでよしとする。(1291->1411)

A.

考えるのがめんどくさかったので無思考でsetを使って通した。計算量的に足りるので問題なし。O(s.size()*26*log(s.size()*26))?

B.

一つの列を掃除するとすべての行に影響してしまう。ここから結局全く同じ配置の行がどれくらいあるかに帰着される。実装も簡単。思考タイプの問題。O(n^3)

C.

本番では解けなかった。DPを使うのだろうと見当はついていたが後ろの方から決定していくという最初のアイデアに固執してしまっていた。(回答は1,2,...,kと順に決めている。)

昇順に考えると、次におくボールは一番後ろに必ず1個おいて、あとは自由となるので

(c_1+c_2+...+c_i -1)C(c_i -1)通りとなる。これをかけていけばいい。

(よく考えると高校レベルの組み合わせな気がして泣けてくる)

D.E.はいつかやる。

D.

そもそも問題文を理解できてなかったので詰み。コンテスト後読み返し、理解すると、抜き出して法則性を探していくタイプ。やってくとフィボナッチとなっているのがわかるので、フィボナッチ進数みたいなことをやる。