AtCoder Beginner Contest194に参加しました。
結果
A,B,C問題の3問正解でパフォーマンスが815でした。 C問題に少し悩み、D問題はあんまり解いたことがない期待値を求める問題で苦戦した。
A問題
問題文通り実装すればOK。 乳固形分がAとBの和という点に気をつけるぐらい。
B問題
問題文を読むとややこしそうな気がするけど、成約を見ると とNが小さいので2重ループで全通り確認しても間に合う。
仕事Aに従業員i、仕事Bに従業員jを割り当てるのを
の全パターン確認して時間の最小値を求めれば良い。
仕事が終わる時間は、i=jのときは
になって、
のときは
と
の大きい方になる。
C問題
成約を見るとなので2重ループで解こうとすると最大で
くらいになるのでTLEになる。
ダメ元で2重ループで解いて提出したら案の定TLEになった。
どうやって計算量減らそうかなと考えながら成約を見るとと高々400通りくらいしか種類がない。
つまり大体の
は別のものと値が被ってる。同じ計算を何度もする必要はないので計算を省略できる。
のどの値が何個あるのかを数えて、
の値の種類全通りで差の2乗を計算する。あとは各
が何個あるのかをもとに何組その計算をすることになるのか数えて2乗和にかけて積み上げていく。
D問題
解けそうで解けなかった。 問題文を読んで確率DPってやつかなと思って解いてけど、解説を読むとDPじゃなくてただの数学だったっぽい。
