2011-07

Latest Entries

スポンサーサイト

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

TCO11 Round 3

350 人中 150 人が Round 4 へ進出.
1000 → 250 の順で解いて,500 が時間切れ.撃墜 1 つ.
1000 が簡単だったが,不安で丁寧にテストした.提出後早めに切り上げれば 500 が間に合ったかもしれない.

250: ArtShift


'B', 'W' からなる長さ N の文字列 sequence に対して N 元の置換を繰り返し作用させるとき,生じる異なる文字列の個数の最大値を求める.
N <= 30.

巡回ごとに考えると,'B' が x 個,'W' が y 個含まれるとき x == 0 or y == 0 ならば 1 通り,そうでなければ x + y 通り生じる.全体では (x, y) たちに分割したときに x + y の lcm を最大化することになる.sequence 内の 'B' を X 個,'W' を Y 個とすると,N の min{X, Y} 個以下への分割でパーツの lcm を最大化すればよい.N の分割数が十分小さいので全探索でよい.

500: PrefixFreeSuperset


'0', '1' からなる文字列の prefix-free な集合 cur が与えられる.cur の superset であって大きさが k であるものの,元の長さの和の最小値を求める.この最小値が 10^18 を超えるならば代わりにそれを指摘.そのような集合が存在しなければ指摘.
|cur| <= 50,(cur の各元の長さ) <= 50,k <= 10^12.

まず木を考えて空いているノードを探す.これは,cur の各元 s と各 x に対して,s[0 .. x] と (s[x] の反転) を結合させたものを候補として,別の cur の元と prefix 関係になっていないものを set に入れてしまえばよい.
空いているノードの「根」はその長さをコストとして集合に追加できる.また,既に追加した長さ c の文字列はコスト 2(c + 1) - c により子 2 つに置き換えることができる (結果として集合のサイズを 1 増やせる).これらの 2 パターンをコストをキーとする priority queue あるいは map で管理すればよい.指数爆発するので見ることになる文字列の長さの個数は十分少なく間に合う上,答が 10^18 を超えることもない.

1000: RowOfColors


h 行 w 列のマス目を k 色で塗る.1 行目は k 色すべてを含まなければならず,各色のマスは連結でなければならない.あり得る 1 行目のパターンの個数として考えられるものの個数を mod 1,000,000,007 で求める.
1 <= h, w, k <= 300.

1 行目の色を順に見ていくときに,初出でスタックに push し,ある色が現れたらそれが top になければならないとし,最後の出現で pop する,と考えると,満たすべき条件はスタックの最大サイズが w 以下であること.どこまで見たかとスタックのサイズをキーにして DP すればよい.

スポンサーサイト

«  | ホーム |  »

プロフィール

hos.lyric

Author:hos.lyric

 

最新記事

最新コメント

 

最新トラックバック

 

月別アーカイブ

カテゴリ

検索フォーム

 

 

RSSリンクの表示

リンク

ブロとも申請フォーム

QRコード

 

QR

 

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