2011-10

Latest Entries

スポンサーサイト

上記の広告は1ヶ月以上更新のないブログに表示されています。
新しい記事を書く事で広告が消せます。

SRM 520 DIV 1

1000 → 250 → 500 と解いた.点数に余裕があったのでちゃんと読まず撃墜 1 ミスしてしまった.全部通って初の 1 位.

250: SRMCodingPhase


SRM に参加する.問題 i (0 <= i < 3) は t 分で解くと points[i] - 2^(i+1) t 点得られる.問題 i を skills[i] 分で解く能力がある.ポイントを luck 点持っていて,1 点につき 1 分解く時間を減らせる (ただし整数分であり,1 分以上はかかる).75 分以内に獲得しうる得点の最大値を求める.

解く問題の集合を決めれば,後ろの問題から順に luck を貪欲に使えばよい.

luck の割り振りを全部試しても間に合う.

500: SRMIntermissionPhase


SRM のスコアボードで,1 位から N 位まで順に各問を提出したかどうかが与えられる.問題 i (0 <= i < 3) は 1 点以上 points[i] 点以下になる.同点がいないものとして,スコアボードが何通りあるかを mod 1,000,000,007 で求める.
points[0] <= 30,000,points[1] <= 60,000,points[2] <= 110,000,N <= 20.

問題の集合に対して,合計 x 点とる方法が何通りかは DP で求まるので,それを利用して N 人分 DP を行えばよい.どちらの DP でも部分和をもっておけば遷移を O(1) で計算できる.

1000: SRMChallengePhase


SRM の撃墜の記録を考える.撃墜には成功か失敗かであり,2 つ以上の撃墜は同時には試みられない.N 人がいる.
・各人は高々 1 回撃墜を試みた.試みたか否かが与えられる.
・各人は高々 1 回撃墜成功された.成功されたか否かが与えられる.
・自分自身には撃墜を試みない.
・自分が撃墜成功された後は撃墜を試みない.
・撃墜失敗は自由に起こる.撃墜成功された後に起こることもある.
撃墜の時間順と成功・失敗の列が何通りあるかを mod 1,000,000,007 で求める.
N <= 2,500.

試みかつ成功された人たちを A,試みかつ成功されていない人たちを B,試みておらずかつ成功された人たちを C とする.撃墜を時間が後のものから順番に考えるとき,A の人が撃墜するときはそれ以前に撃墜されていなければならない.撃墜の対象は A の人かどうかのみが重要であり,A の人でない場合は C の人か失敗 (N - 1 通り) である.
よって,撃墜した人が A かどうか,撃墜された人が A かどうか,の順番を求めて適当な係数をかければよい.前者は DP で求まり,A を a 人,B を b 人既に使ったとき,A を使うならば撃墜されたタイミングが b 通りあるので b をかけて遷移させる.O(N^2).

スポンサーサイト

«  | ホーム |  »

プロフィール

hos.lyric

Author:hos.lyric

 

最新記事

最新コメント

 

最新トラックバック

 

月別アーカイブ

カテゴリ

検索フォーム

 

 

RSSリンクの表示

リンク

ブロとも申請フォーム

QRコード

 

QR

 

上記広告は1ヶ月以上更新のないブログに表示されています。新しい記事を書くことで広告を消せます。