2017-06

Latest Entries

スポンサーサイト

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

IPSC 2011

5 時間で 13 問.
M 問題はペナルティを減らすクイズ大会.6 回目で外した.
変わった問題が多いが,変わった問題というよりは難しい問題という印象の方が強い.全然解けなかった.全問解説が上がっているので後で読みたい.
A1, A2, B1, C1, D1, F1, G1, G2, H1, I1, K1, K2 を通して 30 位,個人の部 4 位.
主に D 言語を使った (H や I は問題文で与えられる言語の処理系を D で書いた).

A: Against a rock play Spock


手が 5 種類あるしりとり (2 人ゲーム) を行う.相手の手たちが見えるので毎回勝つように答える.
A2 では,前に使った手をは異なるものを出さなければならない.

勝敗関係が mod 5 できれいに書けるようになっているので書く.勝ち手は常に 2 つなので未来を気にする必要はなし.

G: Grid surveillance


4096 * 4096 のグリッドがあるので,以下のクエリを処理する.
・1 つのセルに与えられた数値を加える.
・長方形領域の和を求める.ただし,必ずしも現在のグリッドに対する処理ではなく,加算クエリが何個与えられた時点,のような形で問われる.
クエリは前のクエリの結果などを用いて xor などで生成され,オンライン性が求められている.
(クエリ数) <= 2,000,000.

加算クエリの位置を時刻,行,列の組として捉えれば,3 次元の領域探索になる.G1 は入力を見るとクエリ数が 5,000 なのでこれの 2 乗でよい.
テーブルではメモリがとれないので,動的に領域探索木を作成する.
kd 木のようなもの (?) を初めて組んだ.再帰時に担当領域も引数で与える形で実装したが,座標をサイクリックに回していけばよい.ただし区切っていって 1 になるまでの回数が方向によって異なるので注意が必要.

実行には 48 分 30 秒かかった.

K: Keep clicking, keep flipping


n 頂点の無向グラフが与えられる.各頂点は白と黒の状態がある.以下の操作を繰り返して,すべての頂点の白かつ辺が 0 本にできるか判定し,可能なら手順を 1 つ出力する.
・1 つの黒い頂点 u を選ぶ.
・u および u の隣接点の集合を X とする.
・X に属するすべての頂点の色を変更する.
・X で誘導される部分グラフをその補グラフで置き換える.
K1 では n <= 50.
K2 では n <= 2,000.

操作後で u は白くて孤立するので変更されない.よって操作は n 回以下.
いろいろ実験すると,黒い頂点がいる限り大丈夫ではないかと予想できる.より正確には,2 頂点以上の各連結成分に黒い頂点が存在することと,可能であることが同値.細かく検証しなかったが正しそう.
そこで,判定するメソッドを書き,毎回黒い頂点を消す頂点としてすべて試す.O(n^3).

実行には 18 分 10 秒かかった.定数倍の高速化はできるだろうけれどこの程度が十分想定されているようである.

(追記)
と思っていたが,O(n) ステップで候補 O(n) 個で判定 O(n^2) なので O(n^4) だった.実際には黒い頂点は減っていくし,黒い頂点であって選んではいけない頂点はそうそうない (たぶん) のでかなり早く回るのだろう.コンテスト中は,100 ステップ分の時間を目安に大丈夫だろうと判断していた.想定は O(n^3) らしいので解説読もう.

コメント

コメントの投稿


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

トラックバック

http://hos0lyric.blog89.fc2.com/tb.php/8-27ec61fc

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

«  | ホーム |  »

プロフィール

hos.lyric

Author:hos.lyric

 

最新記事

最新コメント

 

最新トラックバック

 

月別アーカイブ

カテゴリ

検索フォーム

 

 

RSSリンクの表示

リンク

ブロとも申請フォーム

QRコード

 

QR

 

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