2017-09

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) らしいので解説読もう.
スポンサーサイト

IPSC 2011 Practice Session

IPSC (Internet Problem Solving Contest) のプラクティス.
24 時間参加可能.
簡単ではなかった.

予約投稿を用いてみる.

P: Pancakes!


材料が与えられるので,作れるパンケーキの個数の最大値を求める問題.
パンケーキの基礎として,8/16 個の foo と 8/16 個の bar と 4/16 個の baz と 1/16 個の qux と 9/16 個の quux が要る.
さらに飾り付けとして,各パンケーキに対し,以下のいずれかが要る.
・1 個の A
・30 個の B
・25 個の C
・10 個の D
・3/4 個の A と 10 個の C
・7 個の D と 10 個の C
・1/3 個の A と 3 個の D と 5 個の B と 5 個の C
ただし P1 では最後の 3 種類は作らない.
各材料の個数は 0 以上 10^6 以下の整数.

D 言語で.
とりあえず分数を消した.
ケーキの基礎と P1 は割り算.
P2 は,最後の 3 種類の飾りを使う個数を y, z, x とでもおけば,
3 変数の「だいたい」線形計画なので,制約された領域の角をみればよい.
3 変数は面倒なので x についてループを回した.
0 <= y <= (y の制約),0 <= z <= (z の制約),y + z <= (y + z の制約),から 2 本の不等式を選んで作れる 8 個の交点に対して,まわり ±2 をみて,制約をみたいていればよりよい解かチェック,とした.

Q: Quality of Service


問題文が一部の文字しか与えられず,空白だらけ.
ときどき (1 分程度?) リロードすると表示される文字の集合が変わる.

最初は同じ文字を線で結んで図がでてくるのかと思ったら全然違った.
リロードして変わったので気づいた.
拾ってきたものを合わせるコードを C++ で書き,たまに手作業で問題文の一部を拾ってくるが重要そうな部分が全然埋まらない…
問題文の前半で wget が推奨されているっぽかったので自動化した.
徐々に埋まり,以下の問題が明らかになった:

数当てをする.相手の予想した数 (1 以上 10^9 以下の整数) はなぜかわかってしまう (入力でもらえる) が,
わざと外したい.ただし,
・1 以上 10^9 以下
・相手の数との差が 1 以上 100 以下
でなければならない.さらに Q2 では,
・奇数番目には偶数を予想し,偶数番目には奇数を予想
しなければならない (この部分が最も見えにくかった).

問題文が読めれば簡単.少し足せばよい.
少し足すと 10^9 を超えるので注意.
これに注意しすぎて,超えたときに 10^9/2 を引いてしまったが,100 より離れてしまっていて WA.

R: Rotate to divide


b 進法で書いて,最後 (小さい方) の桁をとって先頭に持ってくるとちょうど 1/k 倍になるような整数のうち,
最小のものの桁数と最初の桁を答える.存在しないならば指摘.
ただし b 進法で 2 桁以上のもののみ考える.
R1 では 2 <= b <= 8, 1 <= k <= 8.
R2 では 2 <= b <= 2,000,000,1 <= k <= 2,000,000.

k = 1 のときは "11",k = b のときは "10" が最小.k > b のときは解なし.
そうでない場合,l + 1 桁とすると,bx + y = k(x + b^(l-1) y) となる x, y を求めればよい.
b^(l-1) * y が b - k で割りきれることが必要で,これは簡単に確認できるので結構刈れる.
割りきれたら多倍長整数を使って割ってみる.x が適切な範囲なら OK.
l を 1 個ずつ進めて,解が見つかっていたら最小のものを返す.
b^(l-1) が被ったときにやめたらそれで大丈夫のようだった.

計算量やメモリはそこそこ使うが現実的サイズ.
しかし D 言語だと答が最大になっているケースで Access Violation で落ちた.
Java は遅かったが動いたのでそのケースだけ Java で解いた.

最初,k = b が解なしと勘違いして 1 WA.

«  | ホーム |  »

プロフィール

hos.lyric

Author:hos.lyric

 

最新記事

最新コメント

 

最新トラックバック

 

月別アーカイブ

カテゴリ

検索フォーム

 

 

RSSリンクの表示

リンク

ブロとも申請フォーム

QRコード

 

QR

 

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