Entries

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

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

コメント

コメントの投稿

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

トラックバック

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

Smartmatic CONNECT IV (この記事を編集する[管理者用])

2010年04月25日02時30分から4時間,6問.
[ Link ]

なんか,最初1時半からって書いてたのに,気づけば30分延長してて,また気づけば30分延長してた.
なんか最近ケアレスミスが酷い.
どうしたものか…,問題をちゃんと読め,そして,コードを慎重に書け.
一応2時間42分ぐらいで,6問全完.
BGMをデートコースのいちゃぷりOPとゆいにゃんのすきッスSTE(ryを2曲で永遠とリピートするという素敵なことをしてみる.

A. Miles 2 Km

n=fib[i]+fib[j]+…と分解する.
1.6n と fib[i+1]+fib[j+1]+…
の差の絶対値を最小化したい.差の絶対値の最小値を求める問題.
fibはフィボナッチ数列.
nは1000以下.

DPでやるだけすぎる….
状態は,nとfib[i+1]+…で,取りうることができるかどうかのbool値の配列.
だけど,dp[1000][1600+α]ぐらいは必要なので,結構厳しい?
と思ったけど,そんなこともなくて,使えるfibは20個ぐらいしかなくて,最初に1回計算しただけで全部答えは求まるし大丈夫.
サクっと書いてサブミット.Accept.

F. Hypercube

ノード数K,枝数Mのグラフが与えられる.
Hypercubeなグラフとは以下の条件をみたすものである.
・ノード数が2^nで,各ノードは0から2^n-1の番号がつけられている
・2ノードの番号を2進数で表したとき,1桁のみ違う場合にのみ,その2ノード間に枝がはられている
与えられたグラフがHypercubeなグラフかどうかを判定する問題.
Kは2^10以下.

解いていた人がいるのでFを読む.
すっごいやるだけ.
実際に,Hypercubeなグラフを作って,枝が全部対応してるかどうか調べた.
サクっと書いて提出.Accept.

C. Optimal Cut

高さHの完全2分木が与えられる.
カットとは,ノードの集合で,始点から各葉にたどり着くまでに,カットに属するノードにちょうど1回だけぶつかるようなもの.
ノードに重みが与えられたとき,カットの重みはカットに含まれるノードの重みの和.
サイズK以下のカットで,重みが最大のものの重みを求める問題.
Hは19以下,Kは20以下.

下(葉)から順番に計算して行くDPだよね.
ノード数が2^20ぐらいあって,O(2^20 * K^2)とかになるのだけど,大丈夫だろうか….
まぁ,大丈夫に違いない,書いてみる.
サブミット,WA.
時間は全然大丈夫そうだった.が,WAってなんだ….
カットサイズがちょうどKじゃないと駄目だと思ってた.K以下で良かった!
修正.Accept.

D. Nails

二次元平面上に線分が1000個以下ある.
3本以上の線分が1点で交わっていることはないし,線分がぴったり重なっていることも無い.
線分同士の交点を釘で打つ.
どの線分とも交わっていない線分は,その線分の両端を釘で打つ.
必要な釘の数を求める問題.

解いている人が居るし,順番通りDを読む.
2次元幾何,やるだけっぽい.
ライブラリコピペ,ぽちぽち,がりがり.
書いた.提出.TLE.
明らかに交わらない線分同士の判定はちゃんと計算しないようにしてみる.TLE.
何が重いのか…,全部doubleで計算してるからか….
2つの線分の端点4点が,一直線上にある場合は考えないことにしてみる.
これで取り敢えずまだTLE食らうかWAになるか試してみる.Accept.あれ?
まぁ,いいやw

E. Escape

壁に囲まれた部屋で,何か所か穴があいていて,そこから脱出したい.
一度,上下左右の4方向の何処かに向かって移動し始めたら,方向転換できないし止まれない.
壁はぐるぐる回っている.
脱出できるまでの最短時間を求める,また,その最短時間で脱出できる最短距離を求める問題.
部屋のサイズは1000*1000以下,障害物などはない.

毎時間壁を回しながら,穴までの距離を求めて,辿り着けるかどうか判定.
回る処理を頑張って書くだけ.
サブミット.WA.
あ,方向転換できないってのを読み飛ばしていた.
さくさく修正.
サブミット.WA.
うーん?
穴の数の最大値は4000ぐらい…,配列のサイズは2000,足りてねぇorz
サブミット.Accept.

B. Books

幅30以下,高さ30以下の同じサイズの本棚が10個以下あります.
本が100冊以下あります.
奥行きは考えない,本は重ねない,横に倒さない,で,もっとも多くの面積を詰め込みたい.
最終的に,本棚で本の入ってない部分の面積を求める問題.

どう考えても無理ゲー.
適当に枝刈り探索をサブミット.TLE.
ランダム化して,適当に打ち切って,1000回ぐらいリスタートさせてみる.WA.
色々ヒューリスティックスを考えて試して(送って)みる.
12 rejectsの後, Accept.
勿論最適解が出る保証なんてないコードです.

コメント

コメントの投稿

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

トラックバック

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

Appendix

Recent Articles

ブログ内検索

Ads


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