Entries

スポンサーサイト (この記事を編集する[管理者用])

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

コメント

コメントの投稿

コメントの投稿
管理者にだけ表示を許可する

トラックバック

トラックバック URL
http://rsujskf.blog32.fc2.com/tb.php/672-fb623828
この記事にトラックバックする(FC2ブログユーザー)

CUPCAM 2009 (この記事を編集する[管理者用])

2009年10月17日17時から5時間,9問.
[ Link ]

全体的に英語が難しかった.
色々,嵌りながらも,なんとか全部解けた.
以下時系列順.

取り敢えず最初から問題読んでいく.
Aは幾何+尺取りメソッドでいける問題だ.
書く.WA.点が全くない場合とかちょっとまずいことに気づく.直す.AC.(14分)
BはゴールからBFSするだけ.
愚直に書くと計算時間50^4で,頑張って書くと計算時間50^2.
愚直に書いて50^4でも0.016sとかだった.AC.(31分)
Cを読む.問題文難しい.
Dを読む.めんどそう.
Eを読む.実装問題.
取り敢えず多倍長必要だったら面倒.20!+20*19!+20*19/2*18!+...を概算してみる.なんとか64bitで収まるっぽい.
だったら書くか.書いた.あっさりAC.(61分)
Fを読む.あからさまな強連結成分分解.ライブラリコピペ.AC.(70分)
Gを読む.これまた,あからさまな最小全域木.Primをコピペ.AC.(79分)
Hを読む.実装問題.104ステップではなくて10^4ステップであることに気づくのに時間を要した.AC.(98分)
Iを読む.Hの逆をやるだけ.適当にチューリングマシンとテストケースをでっちあげれば良い.でっちあげた.でもなぜかWA.なんで?
Dに取り掛かる.簡単な幾何系実装問題.手抜きでライブラリ貼り付けたらTLE食らった….ちゃんと直してAC.(166分)
Iでついに気がついた.XとYは1以上でなければならない!
HのサンプルでX=0とかあったので,X=0で作っちゃったよ….って,そういうことならHのサンプル間違えてるじゃん.
IでACもらう.(196分)
Cは苦手分野のグラフ問題.
30分ぐらい悩んでたらなんか突然ひらめいた.
枝に色を塗る(1回目のパーティか2回目のパーティか).
3つのノードが3つの枝で結ばれていれば全部同じ色で塗らなければならない!
3つのノード間で2つだけ枝があれば違う色で塗らないといけない.
ってことで,枝を2彩色できるかどうか判定すれば良いのだね.
これで正しいのかちょっと不安だったけど,2彩色ライブラリコピペでAC.(242分)

コメント

コメントの投稿

コメントの投稿
管理者にだけ表示を許可する

トラックバック

トラックバック URL
http://rsujskf.blog32.fc2.com/tb.php/672-fb623828
この記事にトラックバックする(FC2ブログユーザー)

Appendix

Recent Articles

ブログ内検索

Ads


(プライバシーポリシー)
上記広告は1ヶ月以上更新のないブログに表示されています。新しい記事を書くことで広告を消せます。