てきとーな日記

2009-11-16

[]World Finals 00:29

なんとまぐれで3位を取ってしまった!!!

開始

なんか点数の割り振りがすごく偏っているが気にせずとりあえずAから読むことに

読んですぐ方針は立ったので組んでみたがなんかバグってサンプルが通らないorz

最近はICPCの影響でバグ取りがめんどくなってきたので放置して他の問題やることに

Bを読んだらこないだの台湾大会の問題となんか似ている…

とりあえずこないだと同じ嘘解法すればsmallはいけるんじゃね?と思ったがTLEしたorz

まぁちょっと改良すればいけそうなので放置して次へ

Cはsmallはやるだけでlargeはさっぱり分からない…次へ

Dのsmallが全問題中一番点が低かったのでとりあえず通しておくことに

small書いてる途中で、あれこれただのフローじゃんってなったのでlargeもすぐに通った

1時間経過

Eを読んだらlargeはさっぱりだけどsmallはやるだけな感じがしたので組むことに

サンプルは通ったのにsmall通らねーというわけで放置して次へ

やたらと点数の高いFを読んだら幾何ktkrってなって実装開始

なんかバグったので例のごとくVisualizerを作成してデバッグ

途中気分転換にEに戻ったりしてた

2時間経過

ようやくFのsmallが通った

まぁlargeも通るに違いないと信じて時間が余ったら見直してから提出しようと思って放置してBに戻ることに

周囲の長さ最小の三角形ってドロネー三角形のどれかなんじゃね?とか思い始めてそんなの組めねーってなった

とりあえずマンハッタンでのドロネー図っぽいやつは昔実装したのがあったのでそれコピって出してみたらなんか通ったw

さすがにlargeは通らなそーだなーと思いつつ放置してAに戻ることに

3時間経過

なぜかどうしてもサンプルが通らず、よーく見たらClarが出てることに気付き、入力の解釈間違えてたorz

そこ直したらようやくサンプルが通りsmallもlargeも通った

残り時間が少なくなってきたのでやるだけなC-smallをてきとーに通し、B-largeをやってみることに

だいたいO(n log n)の嘘解法だけどTLEしたorz

最後にF-largeをやってみることに

large動かしてみたら、なんか解の正しさチェックが落ちている…

なぜだーと思ったらバグ発見!!!

急いで修正したものの直しきれずTLEorz

終了後

Eの問題文勘違いが発覚orz

暫定順位が6位でE-small通してれば3位だったので鬱になってたが、なんか他の人のが結構落ちてまぐれで3位獲得w

しかしACRushにダブルスコアされたのでやっぱり鬱

ホテルに戻ってからFのバグを取ってみたが、今度は円と多角形の共通部分面積あたりで誤差ってるぽくて正しい解が出なかったので、まぁしょうがなかった

Bは最近点対と同じような分割統治をすればよかったぽい

最近点対知ってるのにこれ解けないとか終わってたorz

Eは帰りの機内で考えてたらてきとーにDPすればいけそう

Cは知らない

2009-10-10

[]Round 3 04:08

なんか運よく通過してしまったw

一人旅とかやばい…英語勉強しないと…

A

全て連結という条件から状態数がとっても減るのでてきとーに幅優先探索するだけ

B

smallは全組計算するだけ

largeもいっぱい提出があったのでずっと考えてたけど、さっぱり分からなかったorz

C

グラフを作ると、平面かつ全ての内面が三角形であることが簡単に証明できる

平面グラフなので、3彩色できるか判定出来ればよくて、三角形性を使うと、線形時間で解ける

まず、ひとつ三角形を彩色して、それと辺を共有する三角形の残りの頂点は色が一意に決まり、共有しない三角形の頂点は、どんな色で塗っても、もう合流しないからどうでもいい

ちなみに組むのめんどかったから彩色ライブラリをコピペったがちゃんと通ったw(追記: これじゃだめなケースがあったorz)

ところでこのグラフなんていうんだろう…

D

あまり解かれていなかったのでほとんど考えてない

smallくらいは解くべきだったorz



合計48pointの12位

2009-09-26

[]Round 2 04:23

A

使えるやつで一番上のから貪欲に使うだけ

B

現在位置とその段で掘られている区間を状態としてDPすればいい

現在位置は掘られている区間の左端か右端のどちらかなので状態はO(RC^2)

次の状態は左右に移動して穴に落ちるか、ある区間を掘ってその左端・右端で落ちるかでO(C^2)

合計O(RC^4)で解ける

C

最初貪欲でよくね?と思って組んだがそんなことはなかったorz

彩色問題のように見えるが、折れ線に上下の順序があるため、昔実プロでやったゴミ拾い問題のように二部マッチングで解ける

頂点をinとoutの二つに分割して折れ線iの上に折れ線jをもってこれるなら辺out(i)->in(j)を引っ張って二部マッチングして全体から引けばよい

D

半径決めると、置く候補は二円に接する場所なのでO(n^2)個あって、そいつらの組全部について可能か調べるのでO(n^5)

二分探索の反復50回くらいと合わせてかなりきついなーと思い、BitsetでOR演算定数倍高速化ーとかやったが十分すぎた

しかも高速化したせいでバグ埋め込んで再提出orz




全問通って4位でRound2通過

しかしid:iwiwiに4秒差で負けたorz

2009-09-12

[]Round 1A 12:47

A

どうせそこまで大きくならないだろうと想定して、てきとーにsmallを通した

largeは最悪ケース試したら遅すぎたので、最初に全パターン計算させることにした

てきとーに最適化したら10秒くらいで全部解けるようになったけど、最悪埋め込めばおk

B

ただのダイクストラ

入力が南からだと思ってWA*2orz

C

集まった枚数の大きいほうから順に計算していくだけ…

なのに、サイズが小さかったので連立方程式かーとかおもってしまったorz

というわけで、上三角行列の連立方程式を解くというわろす解を提出w



全問通って13位でRound1通過

2008-11-16

[]World Finals 23:50

A

ひとまずsmallは全部試すだけだったのでとりあえず出すかと思ったら、なぜかEclipse上で実行できない…

どうやらJREのデフォルト設定がおかしいっぽく、設定し直したりして無駄に時間を食ってしまったorz

プラクティス中にちゃんと試しておくべきだったorz

条件を満たす領域は、2変数で考えるとただの三角形で、片方固定すればただの線分なので、下から順に見ていけばO(n^2)でlargeも解ける。

B

smallは塗りつぶすだけ

largeは片方全部回して…とかではできなさそうでむずい

C

smallは2^2n試すだけ

largeは和に注目すると、実は一意に定まるんだとか…

よく分らないw

D

smallは二つの森からの距離のうち近い方の和に森につなげるためのコストを加えるだけ

largeは森をつなげる部分を最小全域木にすればよい??

よく分らないw

E

smallは2^2nのDPではビミョーに間に合わず、2回もミスってしまったorz

マルチスレッドテンプレートを作ってくるべきだったと後悔しながら考えてたら、連続する3つの?を全て#にして解がよくなることはあり得ないことに気づいたので、その部分を枝狩りしたら間に合った

largeはどう見ても最小カットだろーと思いながらも、かなりの時間考えていたが、結局解けなかった。

カット後に、始点に接続→使う、終点に接続→使わない、となるようにグラフを作ると、負の辺ができてしまって、負の辺の最小カットってどうやるんだーとなって詰まってしまった。

終了後に考えてたら、チェス盤の白黒で分割して、片方逆向きにすればいいだけだったorz

結局負の辺がある時の最小カットを求めるのは無理なんだろうか…


結果はA~EのsmallとAのlargeを通して36点の40位orz

来年もあるなら次回こそはもっといい順位をとってやる〜

ymatsuxymatsux 2008/11/17 00:23 最大カット問題は辺が非負の場合でもNP完全であることが知られていて,負の辺がある時の最小カット問題は最大カット問題に変換できることから,負の辺がある時の最小カット問題もNP完全です

wata_orzwata_orz 2008/11/17 00:28 なるほど、ありがとうございます。