2017-05

Latest Entries

スポンサーサイト

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

SRM 512 DIV 1

1024 → 256 → 512 と解いて撃墜なし.512 を落とした.

256: MysteriousRestaurant


レストランが N 日間開かれる.M 種類の料理があり,日付と種類により価格が与えられる.初日から連続して毎日 1 つずつ料理を食べるが,i 日目と i + 7 日目の料理は同じでなければならない.与えられる予算内で最大何日続けられるか求める.
N <= 50,M <= 50.

日数を決め打てば,各曜日について最安価な料理を選べばよく,可能かどうか判定できる.それを用いて日数をすべて試すか二分探索.

512: SubFibonacci


Fibonacci 数列とは正の整数の列であって,3 項目以降が前 2 項の和であるもの.長さ 0 以上 2 以下の場合も含める.整数の集合 S があり,
・S から元をいくつかの取り出しある Fibonacci 数列の部分列 (連続でなくてもよい) A を作る
・S の残りの元をいくつか取り出しある Fibonacci 数列の部分列 B を作る
・A ~ B は昇順に並んでいなければならない
という操作によって得られる A ~ B の長さの最大値を求める.
|S| <= 50,(S の元) <= 100,000,000.

S を昇順ソートして区切る場所を N + 1 通り考え,小さい方から A を,大きい方から B を作るとしてよいので問題を分割できる.Fibonacci 数列の部分列について,先頭の項は含まれると考えてよい.そこで,先頭の項と途中の項,途中の項が Fibonacci 数列の何番目にあたるか,をすべて調べる.これらを決めれば Fibonacci 数列は復元できる (標準的な Fibonacci 数は前計算).復元された数列で,先頭の項以上の値がいくつ集合に含まれるかをカウントすればよい.

A として [ 3, 1, 4, 5 ] を許してしまった.[ 3, 4, 5 ] が許されるので間違えやすい.また最初「昇順」を見落としていたのもミスに繋がった.

1024: PickAndDelete


長さ N の正の整数の列 S が与えられるので,適切に並べ替えると各 i で x[i] <= S[i] を満たすような長さ N の正の整数の列 x の個数を mod 1,000,000,007 で求める.
|S| <= 200,(S の元) <= 1,000,000,000.

数えるのは昇順に並べ替えたときに x[i] <= S[i] を満たすもの.S[0] = 0 として N 個の区間 (S[i - 1], S[i]] に分けて考えることができ,このうちの j 番目までで j 個以上選ぶことが条件となる.これで O(N^3) の DP で求まる.

i <= n まで x[i] <= S[i] を満たす長さ n の数列の個数を DP で O(N^2 log N) で求められる.x[i] > S[i] となる最小の i に注目して引いていけばよい.

コメント

コメントの投稿


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

トラックバック

http://hos0lyric.blog89.fc2.com/tb.php/43-e3da859f

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

«  | ホーム |  »

プロフィール

hos.lyric

Author:hos.lyric

 

最新記事

最新コメント

 

最新トラックバック

 

月別アーカイブ

カテゴリ

検索フォーム

 

 

RSSリンクの表示

リンク

ブロとも申請フォーム

QRコード

 

QR

 

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