SRM503 Div1 Medium

500

村ごとに計算する。1番近い村が選ばれる確率、2番目に近い村が選ばれる確率、... を計算する。
これを間違わずに実装できる気がしないけれど、本番での正答率はそれなり。
ツラい。

SRM502 Div1 Medium

500

貪欲 & DP
DPか貪欲だろうとは雰囲気で察することができた。
が、具体的な解法が思いつかない。試しに問題からでなく上限から解法を考えてみる。

入力の上限から、( 時間 * 問題数 ) くらいの計算はできそうなので、それを足がかりに DP を考える。
DP[どの問題まで][経過時間] ならできそう。

こうなると、解く順番が問題。
解く問題が決まるということは、ポイントの総和が決まるということ。
なら、解く順番は減少が少なくなるように決めるはず。

( 減少 / 消費時間 ) でソートして試す。サンプル合う。通る。

SRM499 Div1 Medium

550

DPを疑った後で諦めて貪欲へ。

小さいケースとサンプルを手で試す限りでは DELETE 無しでも答えが合う。
SPACE と相殺するから？

**
****
******
#####
###
#
作る順番に制約がないので、* 側を作る途中で RETURN して # 側を作っても構わないはず。

*******
*****
***
**
*****
*******
こう凹みがあったとしても、凹んだ部分で分割すれば山になる。

増加にだけ着目してしまえば良さそう。300 とか 450 くらいの問題にも思える。
どうやら、DP 解がちゃんとあるらしい。

SRM498 Div1 Medium

450

マークのある地点までの距離をが等しい箇所を数えてしまって良い。
同じ地点が F 箇所ある場合、ただの並び替えなので F 階乗パターン。

SRM496 Div1 Medium

500

2部マッチングの個数にしかみえなくて絶望。

経過した秒数 D の数はたかが知れている。
D を決め打ちしたとすれば、2部グラフが作れる。

+D 秒後と -D 秒後の 2 つしかマッチさせる候補がないので
あるマッチングの連結成分の右側と左側の頂点の個数は
R == L
R + 1 == L
R == L + 1
の3パターンしかない。

R == L のマッチングの個数は 1 通り
R + 1 == L はどこの入次数を 2 にするかで L 通り
R == L + 1 は成り立たない。

後は、連結成分ごとのパターン数の積を計算する。

SRM486 Div1 Medium

450

実際にソートしながら試す。

SRM481 Div1 Medium

500

ます、同じ人のタスクは連続して処理されるべき。
混ぜると、同じ時間の消費でも互いの終了時刻が後ろにずれてしまう。

どれから最初に処理すべきかというと、時間の総和が小さい順。
逆だと、同じ時間の消費でも終了時刻が後ろにずれてしまう。

同じ時間同士の場合は、1/2して期待値に足す。
どちらが先に行われるかは等確率なので、それより前の場合と後の場合になる。

同じ人のタスクの中での期待値も同様の理由から、1/2にして期待値に足す。

SRM578 Div1 Easy

250

マンハッタン距離が dist 以下の点同士をまとめておく。
"選ぶ" or "選ばない"の2択で偶数になる場合を数え上げる。
DP[どこまで見た][総和の遇奇]=パターン