SRM479 Div1 Medium

500

safety の値を2分探索しながらダイクストラする。
ところどころ signed int に収まらないことに注意。

問題文が長いし、どこか見落としそう。
UVaみたいな問題だから好きになれない。

SRM477 Div1 Medium

500

2部マッチングするだけ。
入力の仕様に殺意を覚えた。1時間も悩んだ。

SRM466 Div1 Medium

500

5箇所を選ぶパターン数を数える。
DP[何列目まで決めた][残り何箇所][勝利状態かどうか] = パターン数

dp[N][0][true] / (dp[N][0][true] + dp[N][0][false])
で確率が出る。

SRM473 Div1 Medium

500

円の中心を通るような直線を含む三角形は直角三角形になる。

a = 0, b = 0 のときが問題で、愚直にやると O(N^2) かかる。
気のきいた方法を取るべし。

通した後で気付いたけど、set.lower_bount でいいのでは。

SRM463 Div1 Medium

500

加算の方が大きくなるのは 2 以下だった気がするので、下限が 1.5 だとある数字の加算が 1 度しか行われないことになる。
また、乗算はそれぞれの数字の差が小さい方が結果が大きくなる。
小さい方から、ある範囲をそれと隣接する範囲へ逆順に加算し、総乗する。

SRM462 Div1 Medium

450

ある組みのスワップが起こる確率は 2.0 * (c / (n * c)) * (c / (n * c - 1.0))
ある交換で変化する期待値の差分は score[i] - score[j]
各箱に入っているキャンディーの数は言うまでもなく C

あとは、数値を S ターンだけ更新する。

こういう、"スワップした後"と"期待値"が出てくる問題の類はひどく苦手。

SRM451 Div1 Medium

500

dp[どれを最後に拾った][最後に足したK] = 最大
i 番目の次に j 番目を拾おうとする場合、最小でも、
k + (k + 1) + (k + 2) + ... (k + (j - k)) = (j - k) * k + ((k + 1) * k / 2)
だけは足す必要がある。それ以上であれば、移動可能ということになる。
あとはいつもどおり DP する。

SRM450 Div1 Medium

500

10^12 とか 10^6 程度でどうこうできるだろうと見切り発車して後悔。意外と難敵。

ある工場か従業員を雇うなら可能な限り多く一度に増やすべき。
増やせない場合は、増やせるターンまで飛ばす。
それとは別に、これ以上増やさずにいったとして何ターンかかるかも計算しておく。

オーバーフローとか怖い。
もっと綺麗に実装できそう。

SRM575 Div1 Easy

250
2の累乗の場合は指数の遇奇。
それがいは単なる遇奇。

実験ゲーらしい。
本番中に解けなかった。ツラい。

SRM557 Div1 Medium

550
DAGの最小パス被覆。Dilworthの定理。
サイクルに含まれるような頂点は無視する。

SRM557 Div1 Easy

250
貪欲に近い方へ移動する。
その後、その移動が正しいか確かめる。