2011-07

Latest Entries

スポンサーサイト

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

Yandex.Algorithm 2011 Finals

Onsite と同時に参加.B → C → A で手を付けたが B は解けなかった.A と C は通った.

A: Domino


28 種の標準的なドミノのセットを並べた形状が与えられる (目のみが隠される).これを 2x2 の正方形 7 個に区切ったとき各正方形内では目の数が 4 つ揃っているようなドミノの配置が何通りあり得るか答え,さらにそのうち 1 通りを出力する.
(幅), (高さ) <= 30,解が 1 つ以上存在.

正方形への区切り方は左上から貪欲でよい.正方形への数の割り当て方は 14! / (2!)^7 通りで,最初の出現を順に 0, 1, ..., 7 としてして後で 7! 倍すれば間に合うサイズになるので,あとは探索.

B: Superset


平面上の n 個の格子点が与えられるので,それらを含む m 個の格子点 (m <= 200,000) であって,その中の任意の異なる 2 点 A, B に対して以下のいずれかを満たすようなものを 1 つ求める.
・直線 AB が x 軸または y 軸に平行.
・A と B の bounding box 上 (境界を含む) に A, B 以外の点が存在.
n <= 10,000.

分割統治.中央の縦線を引いて,現れる y 座標の箇所すべてに点を打ってしまえば残りは左右それぞれで満たされればよい.O(n log n) となり足りる.点は set に入れて管理.

定数がゆるい O(n) だろうと思って誤答を投げ続けてしまった.

C: Winning Strategy


ある大学から ICPC finals に無限回参加する.選手は無限に供給されるが,同じ選手は 2 回までしか参加できない.チームは n 人からなる.このうちの i 人が過去参加経験がある場合にメダルを得る確率を p[i] とするとき,派遣戦略を動かしてメダル獲得確率の平均値の最大値を求める.
3 <= n <= 100,0 <= p[0] <= p[1] <= ... <= p[n] <= 1.

平均を考えるので初年度まわりは無視してよく,さらに派遣戦略は周期的になるとしてよい (たぶん).各年度で (過去参加経験あり) - (過去参加経験なし) を足していくことを考えると,この値に対応する -n, ..., -1, 0, 1, ..., n を頂点として x から x + i - (n - i) への重み p[i] の辺があるグラフで最大平均長閉路を求めればよい.O(n^3).

右に行く辺と左に行く辺を選べば閉路が作れることから,i として 2 通り試せば解けることもわかる.

«  | ホーム |  »

プロフィール

hos.lyric

Author:hos.lyric

 

最新記事

最新コメント

 

最新トラックバック

 

月別アーカイブ

カテゴリ

検索フォーム

 

 

RSSリンクの表示

リンク

ブロとも申請フォーム

QRコード

 

QR

 

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