スポンサーサイト

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

ICPC Asia regional 2012 へ行きました

結果とコンテスト中の経過を、覚えている範囲で書く。

Tag : ICPC

結果

ABCDEFG の 7 問解いて
Team rank : 9
Univ. rank : 6
だった。チームとしてベストパフォーマンスを出せた ( と勝手に思っている ) けど、それでも世界大会には届かなかった。大学の順位としては過去最高らしくて ( といっても OU が ICPC に参加し始めたのが数年前とかだけど ) その点はよかった。

チームを組んでくれた lyoz さんと rofi さん、色々めんどうをみてくれた komiya さん、ありがとうございました。

経過

0:00 コンテスト開始
僕が A を rofi さんが B を読み、lyoz さんにはテンプレを打ち込んでもらう。

A は整数のペアどうしのかけ算を定義して、そのかけ算を使って約数・倍数・素数を定義して、与えられたペアが素数かどうかを判定する問題だった。
問題文の最後に重要な Notes が書かれていて、これを使えばなんかできそうな気がした。
あと、問題文の書き方が妙に mathematical だなぁと思っていた。
かけ算の定義が複素数っぽいなと一瞬思ったけど、なぜかちょっと違うと勘違いして考えを捨ててしまった。見直してみたらそのまんまガウス整数だし、問題はガウス素数かどうかの判定だった。これはライブラリ化してなかったので、気付いてたところで楽になったわけじゃないけど。

数分考えて、Notes の事実を使えば全探索できることに気付いて、それを実装した。
Notes の m,n を問題文中の m,n と違う意味で使う必要があって、ちょっと混乱した。いじわるだなぁと思った。

0:18 A accepted
second acceptance だったらしい。

C がどうみても行列べき乗だったので、lyoz さんに書いてもらう。
僕は rofi さんと B の方針をしゃべったり次の問題を読んだりしていた。
そうこうしているうちに C が通っていた。

0:43 C accepted

B はサイズが大きいとかなり難しい感じがしたけど、小さいので単に全部試せばよい、ということになり、続けて lyoz さんに書いてもらった。

B を書いてもらっている間に E を考えていた。

一番ナイーブには、king の位置と二つの空きマスの位置を状態とするメモ化 BFS とかだけど、O(H^3 W^3) とかになって間に合いそうにない。
そこで king にだけ注目してみると、king が移動できるためには隣接する二マスが空きマスじゃないとだめで、じゃあそういう状態だけメモればよさそう、と考えた。
つまり、状態は [king の x 座標][king の y 座標][king の 4 方向のどこが空いているか] で 50*50*4。
遷移がコスト 1 じゃないので、BFS じゃなくて Dijkstra にする。
あとは遷移コストが計算できればいい。
つまり、king の位置を固定したとき、二つの空きマスを特定の二マスに移動させるための最小コストを求める問題が解ければいい。
二つの空きマスの移動は独立に考えてよさそうなので、それぞれ BFS する。どっちがどっちに移動するかのパターンを全部試して最小値をとった。

この時点では E の正解者はいなかったけど、多分方針はあっているので、B と平行して ( B を印刷してデバッグしてもらいながら ) 書き始めた。

実装が重い。
それから少しして B が通った。

1:15 B accepted

ひきつづき E を書いていたけど、全然終わらない。
D ができそうだということなので、E を中断して D をやる。

多項式の係数を復元するのは単純な掃き出し法でやればいい。
行列が退化しているとやばい気がしないでもないけど、これはいわゆるヴァンデルモンドの行列式で、0 にはならないので大丈夫。
rofi さんにデバッグしてもらいながら、D と E を平行して書いていた。
問題文に誤差が 1e-6 とかなんとか書いていたので EPS=1e-5 にしていたけど、これだといくつかのサンプルがあわなくて、EPS=1e-3 にしたらサンプルが全部通ったので投げた。

2:01 D accepted
実は Lagrange の補間多項式はライブラリに準備していたのに、コンテスト中は気付かなくて使えず、ライブラリにした意味なかった。

E の続きを書き、二人にはたくさん解かれていた F とか G を考えてもらう。
途中、僕も G をやってた気がするけどどのタイミングだったか覚えてない。

F はまったく関わらなかったけど、なんか union-find を拡張すればできるらしい。
日本の regional でクエリ処理が出たのでびっくりした。
lyoz さんに書いてもらっていつの間にか通っていた。

2:43 F accepted

G は三次元の線分と点の距離が計算できれば、あとは全探索すればよい、ということになった。
三次元の線分と点の距離は、練習会で Live Archive 4973 ( 三次元の線分と線分の距離 ) を解いたときにライブラリに加えていたので写すだけだった。
サンプルがあったので投げるも WA。視線が風船に接しているときの処理を変えてみても WA。

G wrong answer
G wrong answer

間違える要素がないので途方にくれていたけど、直後 scanf の引数に & を付け忘れていた事に気付き、提出。通る。

3:33 G accepted
これでサンプル通るとか不運すぎる。

E がいよいよ書き終わって、デバッグに入る。
Dijkstra の中で、どうやら king がフィールドを突き抜けてショートカットしているらしいことがわかったので、H+=2, W+=2 して、まわり全部を壁で埋めたらサンプルが全部通った。提出。

4:23 E accepted
190 行くらいだった。しかし改めてみると実装遅すぎ。

残り 30 分くらいしかなかったので、順位表をみて三人で I をやることに決めた。
二分探索はすぐに気付いたけど、そのあと答え s 以下にできるかどうかの判定がわからず、その方針は捨ててしまった。
結局あまりいい案が浮かばず、O(n^2) の DP をとりあえず書いてみることにした。ジャッジサーバーが爆速で通ったらラッキー、通らなくても DP を加速する方法がわかるかも、とか。
この DP もちょっと書きにくくて、残り 5 分くらいで書きあがった。提出。

I time limit exceeded
はい。

枝刈りを入れようとコードを書き換えているときに終了。

5:00 コンテスト終了
おつかれさまでした。
スポンサーサイト

コメントの投稿

非公開コメント

プロフィール

fura2

Author : fura2
数学・コンピュータを中心に、考えたこと・やったことを書いていきます。

誤植等を含め、間違いはご指摘いただければ幸いです。

FC2カウンター
検索フォーム
最新記事
最新コメント
最新トラックバック
月別アーカイブ
リンク
RSSリンクの表示
上記広告は1ヶ月以上更新のないブログに表示されています。新しい記事を書くことで広告を消せます。