GCJ
なんとまぐれで３位を取ってしまった！！！ 開始 なんか点数の割り振りがすごく偏っているが気にせずとりあえずAから読むことに 読んですぐ方針は立ったので組んでみたがなんかバグってサンプルが通らないorz 最近はICPCの影響でバグ取りがめんどくなってき…
なんか運よく通過してしまったｗ 一人旅とかやばい…英語勉強しないと… A 全て連結という条件から状態数がとっても減るのでてきとーに幅優先探索するだけ B smallは全組計算するだけ largeもいっぱい提出があったのでずっと考えてたけど、さっぱり分からなか…
A 使えるやつで一番上のから貪欲に使うだけ B 現在位置とその段で掘られている区間を状態としてDPすればいい 現在位置は掘られている区間の左端か右端のどちらかなので状態はO(RC^2) 次の状態は左右に移動して穴に落ちるか、ある区間を掘ってその左端・右端…
A どうせそこまで大きくならないだろうと想定して、てきとーにsmallを通した largeは最悪ケース試したら遅すぎたので、最初に全パターン計算させることにした てきとーに最適化したら10秒くらいで全部解けるようになったけど、最悪埋め込めばおk B ただのダ…
A ひとまずsmallは全部試すだけだったのでとりあえず出すかと思ったら、なぜかEclipse上で実行できない… どうやらJREのデフォルト設定がおかしいっぽく、設定し直したりして無駄に時間を食ってしまったorz プラクティス中にちゃんと試しておくべきだったorz …
A 全ての鳥を含む最小の長方形を求めて、その中に入っていれば鳥で確定 そうでない場合は長方形をその点を含むように拡大した時に鳥でない点が含まれたなら、鳥でないことが確定 残りはUnknown smallもlargeも同じ D smallは大きい方のどの頂点が小さい方の…
A マップのサイズの配列用意して通った道記憶して縦方向と横方向から眺めればいい メモリがやばいことになったけど気にせずヒープサイズ増やして強行突破 B ただの探索ゲー 奇跡のバグ0で動いてすんなり終了 C どう見ても二部グラフの安定集合 おいしく頂い…
A ただのDP コピペしたとこ一部直し忘れてWA×1orz B 小さい方は一点原点に固定して残り二点四乗ループで間に合う 大きい方はO(NM)の解法なら分かったけどテストケース1000個もあったら間に合う気がしなかったのでパス なんとx1y2-y1x2=Aにおいてx1=N,y1=1と…
A ソートして片方逆向けるだけ B フローじゃね？とか思ってずっと考えてたけど分からずorz ひとまず何も出さないのはさびしいので全探索でsmallを通した よく考えたら一つに絞られた人から順に使ってけば大丈夫なので、テキトーに実装してlargeもクリア C 数…
A てきとーにDPした B 各出発時刻について二つ頂点作って間に合うところに辺を引いて二部マッチング なんていう激しいことはしないで、てきとーにPriorityQueue使って貪欲に使った C 正方形と円の共通部分の面積をまじめに計算した 三問とも通って予選通過 …
