2017-09

Latest Entries

スポンサーサイト

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

TCO11 Round 2

850 人中 350 人が Round 3 へ進出.
1000 → 250 の順で解いて 500 が時間切れ.Challenge は何もせず.
1000 が落ちたが 250 の速度があってなんとか通過.

250: GuessTheNumberGame


ある整数が 1 から n で割りきれるか否かを 'Y'/'N' の列で表した長さ n の文字列は何通りあるか,mod 1,000,000,007 で求める.
1 <= n <= 10^6.

素因数で決まる.p^e <= n < p^(e+1) ならば,p の肩が 0, 1, ..., e-1 あるいは e 以上,の e + 1 通りに区別されるので,それらの積.

500: STable


s ~ t の文字がすべて異なる文字列 s, t に対して,
・table[i][0] = s[i - 1]
・table[0][j] = t[j - 1]
・table[i][j] = min(table[i - 1][j], table[i][j - 1]) ~ max(table[i - 1][j], table[i][j - 1])
により table を求める.table[|s|][|t|] の位置 pos から 50 文字 (あるいは末尾まで) を求める.
1 <= |s|, |t| <= 30.

table[i - 1][j] と table[i][j - 1] のどちらが小さいかをすべて知れば,(i, j) = (|s|, |t|) から辿って復元できる.
比較結果をメモ化することで,(a, c), (a, d), (b, c), (b, d) の大小を知ったうえで a ~ b と c ~ d を比較したい.ここで,table の異なる場所は文字の集合として異なるので,等しくなければ一方が他方の prefix になることはない.よって (a, b) と (c, d) を pair として比較すればよい.
メモ化されるのは斜めに揃ったところの比較なので,3 乗オーダ.

本番中は table に sort, unique をかけたものとして比較すればよいだろう,と思ってやったが誤りのようだった.

1000: CircuitDesign


二部グラフを平面に描きたい.辺は交差せず,外側を通らないようにする.上下の n 頂点ずつの並べ方が何通りあるか,mod 1,000,000,007 で求める.
n <= 50,(辺数) <= 50.

caterpillar tree (caterpillar forest) の問題.細かい条件をいろいろ処理する.
サイクルがあれば不可能.u の隣接点 v で deg(v) >= 2 なるものの個数を deg'(u) とする.deg'(u) >= 3 ならば不可能.
孤立点は後で任意の位置に挿入できる (場合の数も求まる) ので無視しておく.連結成分は左右を分離するので,各連結成分での場合の数をかけあわせて,並び順を考えればよい.
各連結成分については,基本的には葉の順序に対応する (deg(u) - deg'(u))! の積.さらに,連結成分内に葉でない頂点 (deg(u) >= 2) が 2 個以上あれば,左右の反転で異なるものができるので 2 倍する.

ミスした点は 2 倍できるかどうかの判定.deg' を使ってしまい混乱し,3 頂点の木を反転できるとしてしまった.

コメント

コメントの投稿


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

トラックバック

http://hos0lyric.blog89.fc2.com/tb.php/32-4fbd830d

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

«  | ホーム |  »

プロフィール

hos.lyric

Author:hos.lyric

 

最新記事

最新コメント

 

最新トラックバック

 

月別アーカイブ

カテゴリ

検索フォーム

 

 

RSSリンクの表示

リンク

ブロとも申請フォーム

QRコード

 

QR

 

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