2017-07

Latest Entries

スポンサーサイト

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

SRM 511 DIV 1

1000 から開き,バグが取れず残り 10 分になりとりあえず 250 を片づけ,1000 に戻ったがあと少しのところで間に合わず.撃墜は 1 成功.

250: Zoo


うさぎとねこがあわせて N 匹いて,全員の身長は異なる.N 匹それぞれに対して,「同じ種類で自分より高いのは何匹か」という情報がある.どの動物がうさぎでどの動物がねこか,のパターンが何通りあるか求める.
N <= 40.

うさぎが x 匹,ねこが y 匹であれば (0, 1, ..., x - 1; 0, 1, ..., y - 1) となるのでこれをソートして入力の vector と比較.一致したとき答に 2^min{x, y} を足せばよい.

500: FiveHundredEleven


511 以下の非負整数が書かれたカードが N 枚あり,2 人でゲームを行う.最初場の数は 0 で,交互に 1 枚ずつカードを使う.カードを使うと場の数に bit の or で足される.カードがなくなるか,511 を作った方が負け.先手勝ちか後手勝ちか答える.
N <= 50.

場の数と,場の数を変えないカードが何枚残っているか,を状態にして DP.場の数を変えるカードはすべて使っていないことからこれで状態が表せることがわかる.計算量は 512 * N * N^2.

場の数を変えないカードを使う,という場合を実装し忘れて WA を出した.

1000: GameOfLifeDivOne


ライフゲームの変種.0, 1 が 1 次元円形上に N 個並ぶ.時間が 1 経つと,各セルはそれと隣の 3 セルのうちの多数派になる.'0', '1', '?' からなる文字列が与えられるので,時間 T が経ったときに少なくとも K 個の 1 があるような '?' の埋め方は何通りあるか求める.
N <= 50,T <= 1,000.

同じものが隣接していれば変わらない.00 と 00 に挟まれた部分は 1 が 1 つずつ減り,11 と 11 に挟まれた部分は 1 が 1 つずつ増え,00 と 11 あるいは 11 と 00 に挟まれた部分は 1 の個数は変わらない.2 個以上同じものが隣接する場所をどこにするかを決めればよい.
円形なのでどこかできる.全体で 0, 1 が交互のケースは特別処理し,2 個以上同じものが隣接しているブロックのうち左端が最も左にあるものの位置と 0/1 で場合分け.それぞれのケースは,最後に作ったブロックの位置と 0/1,時間 T の後の個数,を状態にして DP すればよい.
元から書かれている 0, 1 については,0000..., 1111..., 0101..., 1010... のそれぞれに一致しない箇所の部分和をもっておけば適合するか判定できる.2N くらいまで作っておく.
全体で O(N^5).

コメント

コメントの投稿


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

トラックバック

http://hos0lyric.blog89.fc2.com/tb.php/36-390f695c

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

«  | ホーム |  »

プロフィール

hos.lyric

Author:hos.lyric

 

最新記事

最新コメント

 

最新トラックバック

 

月別アーカイブ

カテゴリ

検索フォーム

 

 

RSSリンクの表示

リンク

ブロとも申請フォーム

QRコード

 

QR

 

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