企業コンは苦手意識があるが...
ABCD4完、103:30で、257位でした。
経過
A, B
はい。
C
n-away, m-away状態の期待値をE_n,mとおくと、これらについて漸化式が立つ。しかしそのままDPしてもO(N^2)なので困る。
とりあえず小さい場合に計算してみると、p=A/(A+B), q=B/(A+B)とおいて、答えがpqの多項式になるっぽいと分かる。とりあえずN=4くらいまで計算する(たくさん時間がかかる)。するとラマヌジャンが降臨し、係数にカタラン数が出てきそうだと予想が立つ。
でも分からんのでいったんパス。時間を無駄にする。
D
maxを除いた和は作れ、「葉に最小のものを置き、つながる辺を消去する」をくり返すとできそう、となる。問題は実装だが、なんとなくpriority_queueがよさそうと気付けた。次数と頂点をペアにして突っ込み、順次更新するとよい。ダイクストラ法のライブラリを整理した経験が活きた。70分でAC.
C(続き)
とりあえずカタラン数の係数だと決めうちして実装。具体的に書き出し、計算がO(N)になるように直前の係数をうまく利用しながら、苦労して実装。途中ミスがあって答えが合わず焦るが、何とか修正。最後のサンプルが合致して勝ちを確信→AC(103分)
E
nがでかいと0になるけど、それ以上のことは分からず。諦めてこのブログを書き始める()
F
みてないよ
解き直しと感想
よくわかんないけど楽しかった(こなみ)
C
絶対もっと簡単に解けるはずなんだよな。
N勝i敗でどっちかが勝つ確率は普通に計算できますね...
引き分けは無視して後から定数倍できるのはそうなので、
指摘もあったが、「答えを閉じた式で出さなくてもよい」「計算できるシグマの形で表せさえすればよい」というのをもっと強くイメージすべきですね...
D
なんかふつうにDFSをするといいっぽい。あんまりよく分かってないけど...
(追記) 分かっていない理由が分かった。
c_1, ..., c_nは降順ソートしておく。「最大を除いた和c_2+...+c_n」が答えになる証明を考えると、c_1以上は0個以下、c_2以上は1個以下、c_3以上は2個、...とならざるを得ない。よってc_2+...+c_n以下しかない。しかもそれを実現するのはc_i以上がすべて連結することが必要十分。同じ数があっても問題ない。
要は考察が足りてなかった。ちゃんと証明を考えると完全な言い換えができ、実装も簡単になる(DFSで隣り合う頂点を訪れそのつど数字を置くとよい)。この辺のバランスは大事にしないと...(というかこういう思考を素早くしないといけない)
E
あ、dで割ったら階乗じゃーん、なんで思いつかなかったんだ、チクショー！
あとは階乗を累積で持てば終わりですね。悲しいなぁ...
これだから数学回は嫌い(数オリ勢とは思えない発言)
後は随時更新します。
結果
pf2037で、レートは1699→1744 (+45) :)
最高値更新だが、もっとやれた感。競プロ独特の思考をもっと身に付けたいですね。
