2017-08

Latest Entries

スポンサーサイト

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

SRM 508 DIV 1

1000 → 250 → 500 の順に解いた.
3 完して 2 位.
1000 の実装中にマウスが効かなくなり電池切れが判明.こういうどうでもいいタイムロスはなくそう.
撃墜は同じ人に 1 失敗 1 成功.失敗原因は写して実行させたとき初期化を忘れたこと.

250: DivideAndShift


m mod n を (m + 1) mod n か (m - 1) mod n か m mod n/p (p は n の素因数) にする操作ができる.
M mod N を 1 mod (何か) にするための最小の操作回数を求める.
1 <= M <= N <= 1,000,000.

±1 をするのは最後だけでよい.
メモ化再帰で (N の約数) くらい呼ばれる.

±1 する必要をもう少し感じてしまったので無駄なコードが紛れた.

500: YetAnotherORProblem


長さ N の数列 R が与えられるので,
0 <= a[i] <= R[i] かつ a[0] + ... + a[N-1] = a[0] | ... | a[N-1]
なる数列 a が何通りあるか,mod 1,000,000,009 で求める.
2 <= N <= 10,1 <= R[i] <= 10^18.

言い換えれば,各ビットについて立っているのが高々 1 つ.
上の桁から作る DP.
状態として,自由に立たせられるか R[i] の制約が生きているかを覚えればいいので 2^N.
R[i] のビットが 1 かつビットを立てなかった,というときに自由化.

1000: BarbarianInvasion2


凸 M 角形の周上に等間隔に 1,000,000! 人がいる.内部に街が N 個.
人を N 個のサイズが等しいグループに分け,向かう街を 1 つずつ指定.
人と向かう街の距離の最大値を最小化する.
M <= 50,N <= 5.

1,000,000! は無限としてよい.
答を決め打って二分探索.
R を決めたとき,周上で各街から距離 R 以下な部分かどうかは,
円と直線の交点たちで区切った領域では等しい (ので判定時に適当に中点をとってよい).
周長の 1/N がちゃんと送れるかは最大流で求まる.
頂点は O(2^N) 個にまとめることもできるが,それをしなくても通った.

コメント

コメントの投稿


管理者にだけ表示を許可する

トラックバック

http://hos0lyric.blog89.fc2.com/tb.php/3-d820ab56

この記事にトラックバックする(FC2ブログユーザー)

«  | ホーム |  »

プロフィール

hos.lyric

Author:hos.lyric

 

最新記事

最新コメント

 

最新トラックバック

 

月別アーカイブ

カテゴリ

検索フォーム

 

 

RSSリンクの表示

リンク

ブロとも申請フォーム

QRコード

 

QR

 

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