2017-07

Latest Entries

スポンサーサイト

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

TCO11 Round 1

2000 人中 850 人が Round 2 へ進出.
1000 → 500 → 250 の順に解いた.3 完と challenge 4 成功で 2 位.

250: TripleStrings


3 つの文字列 A, B, C に操作をして,(A, B, C) を (init, "", "") から (goal, "", "") にしたい.init と goal は同じ長さで 'o' と 'x' からなる.操作は,
・A の先頭の文字を B または C の末尾に付ける
・B または C の先頭の文字を A の末尾に付ける
のいずれか.操作の最小回数を求める.
解の存在を,「init と goal の 'o' の個数は等しい」として保証.

init から何文字か削って goal の prefix にならないといけないので,(それにかかる文字数) * 2 はかかる.一方削ったものは 'o' を B に 'x' を C に配れば適切な順番で拾えるのでこれが最小回数.

全部削るケースに注意.非自明だが,最小は長さ 4 で "ooxx", "oxox" など.

500: MuddyRoad


N マスからなる道があり,各マスには雨が降る確率が与えられる.一歩で 1 マスあるいは 2 マス進めるとして,雨が降ったマスに止まる回数を最小化を考える.この回数の期待値を求める.

(i, (マス i に来るための雨マスに止まる最小回数), (マス i + 1 に来るための雨マスに止まる最小回数)) を状態にとって DP した.O(N^3) で書いたが,実際にとり得る状態数は O(N^2) しかない.

1000: IPv444


N 人がいて,整数の 4 つ組を求めている.4 つのうち一部の成分を指定しており,それを満たすものをあげると一定の金額を支払う.各人には任意個あげてよい.[0, 999]^4 のそれぞれを 1 人以下に配り,もらえるお金を最大化.
N <= 50.

配るもののパターンは,各成分について,現れる数あるいはワイルドカードなので,高々 (N+1)^4 種類について考えればよい.マッチしている人の中から最大の金額の人を探す.全体で O(N^5) で,完全に N^5 回すと間に合わないが,「異なる成分を発見したら break」という自然な break と,「最初に金額でソートしておきマッチする人を見つけたら break」という枝刈りを入れることで,全成分全員ばらばら,が最悪ケースとなり (たぶん),測って OK だった.

50^5 なので微妙だがとりあえず組んだ.簡単すぎる気がしてゆっくりめにテストした.
最初の 3 成分について回して,マッチしているものに対して 4 成分目を拾ってくればそう複雑でなく O(N^4) にできる (たぶん).

コメント

コメントの投稿


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

トラックバック

http://hos0lyric.blog89.fc2.com/tb.php/26-a952e1d5

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

«  | ホーム |  »

プロフィール

hos.lyric

Author:hos.lyric

 

最新記事

最新コメント

 

最新トラックバック

 

月別アーカイブ

カテゴリ

検索フォーム

 

 

RSSリンクの表示

リンク

ブロとも申請フォーム

QRコード

 

QR

 

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