hogloidのブログ

へなちょこ

GCJ 2017 R3

ちょっとうれしいので大雑把なコンテスト経過をメモ:

始まる前

  • 昼に起きた。あまり頭は使いたくないので、家の掃除をして、東方のなろうを少し読む
  • なんか頭が明らかに動いてないので10分横になって紅茶を飲む
  • 直前にsigmaがク☆バンバードを視聴完了していたので釣られて視聴する

始まった後

  • とりあえず点の取り方をソートするプログラムを動かす。でも問題を見ないと何もわからないので、Aを読む

A

  • なんか難しい?サイズ10^9のグラフを陽に構築すればできるのはすぐ分かったから、とりあえず書こうとする
  • あまり手が進まない
  • 逆から見たほうが書きやすいことに気づいたので、逆からにして書く
  • smallは通る。
  • largeは少し怖かったが、うっかりボタンを押してしまい走らせる。
  • 明らかに途中のケースで30秒ぐらいかかってる…がそういうケースは4個ぐらいだったのでヤキモキしながら実行の終了を見守る
  • さすがに見守ってられないのでBを読む、があまり頭に入らない
  • 結局4分ぐらいで終わった。すぐに出す

B

  • 読む、さっぱり分からない。フローに見えるけどとても制約を表せそうにない

C

  • 読む
  • Cやりゃ通るだろと思ってたので、やる気が出る。
  • 最初頂点ごとの2通りの結び方のうちコストの小さい方をやれば必ずいけるのかと思い書き始めるが、さすがにそれだと非連結になることに気づく
  • 少し焦り、B/Cどちらを解くにせよD-smallが必要だと思いDに行く

D

  • 読む、10^9+7 だからどうせlargeは解けないな~ラッキーと思ったが、数え上げではない。でもどちらにしろ大変すぎる見た目だし、元々smallしか解く気はないのですぐにdijkstra調に小さいところから埋めていく
  • 通る

C

  • コストが小さい方でとりあえずつなげて、コストが大きい方にswitchすれば2つの連結成分をつなぐ感じになるから、それでKruskal調にやればいい気がする
  • 書いた実装はそこまで消さずに済んだ。始点周りが面倒になって、2通り試せばいいかと思って書く。後で2*2通り試さなきゃいけないことに気づいて直すことになる
  • 書き上げる。smallを通す。残り1hちょい。
  • この時点でAbCdなら通ると思ってたので、bを書いてからCをちゃんとチェックしようと思う

B

  • 考えても分からない。接続行列に掛けるとゼロになる非ゼロベクトルを求めるのかな?と思ったけど、吐き出すと変なことになるしとても簡単には扱えそうにない。smallの愚直は本当に愚直だと間に合いそうもない。
  • 分かんねえ…ACdで終わってしまう可能性を考え、Cを出しておく。
  • よく考えると同じ頂点組を結ぶ辺が両側にあったときまとめられるな~とか思い、smallができそうな計算量になる
  • いくらなんでも面倒すぎる(特に復元) 間に合う保証もないし
  • 残り35分、さすがにこのままsmallやるのは無理だと思いちゃんとした解法を考える。そもそもこんなに解かれてるのが難しいはずがない!
  • ポテンシャルを与えて適当にごにょる?とかも考えたがダメ。とりあえずdfs木を思い浮かべる。
  • 木の部分だけ決めたら残り一意かな~と思ったがそうでもない
  • SCCして強連結成分ごとに考えればいーやと思う。そしたらとりあえずサイクルが取れるなとか思う。
  • サイクルに分解しつつやるのかな~とか思うが分解できないときもある。
  • そのときは逆辺使ったことにすればエエヤンって思う。
  • 逆辺を取るときに短いpath取ればサイズが毎回1/2になるのかな?とか思う→違う
  • でもともかく何度も辺使っていいなら毎回サイクル取れんなあとか思う。
  • サイクルの長さはN以下だからなあ…→0の辺があったらそれを含むサイクル見つけて全部0じゃなくなるように適当にaddできるやん!
  • 合わせても辺の値はN*Mやん!もうsmall通ればいいしとりあえず書いちゃお
  • 頑張って書く、フローと似た処理になるが1から書く。
  • とりあえずSCCして2強連結成分の間に辺があるとダメだな、とか思う(そうじゃなくて橋があるとダメ。後で書き直すことになる。まあ貼るだけだから大したロスにはならなかった)
  • そこそこバグるがなんとか書き終わる。
  • 少しデバッグする、閉路検出周りを少し直す。
  • 大体20分弱で、久しぶりに満足できる実装速度だった。本気出せばお前できるやんけ!みたいな
  • ウキウキでsmallを出す。通った!でも順位は35位、なんで?
  • ももうLargeも解ける状態なので、Large解いて本当によかったと思った。順位表を見て、自分はpenaltyなしだから74点2:22なら通ることを確信する
  • とりあえず2:22まで色々見る、特に間違いはなさそう(∵2:22+8でコンテスト終了だから2:22より遅く開く理由はない)
  • 2:22になって速攻で出す。残りの時間は確認に費やす。
  • 出力の絶対値がn*n以下、0でないことが確認できたらこの問題だとほぼ間違いなく通るなあ、と思いあまり身が入らない
  • そういえば証明はn*m以下しかしてないな、と思って焦るけど出力に対してチェックしてるのでい~やと思う。
  • 終わる。Cは結構不安だったので見るのを躊躇した…けど20位が19位になってたのでtestが終わったのを確認。やったぜ。嬉しすぎるだろ

感想

  • 自分が通ったから、簡単だなあ…と直後は思ったけど、Bは結構苦戦したし、これよりボーダーが上というのもあり得ない気がする
  • とにかく長年の夢だったので嬉しい。もう競プロ辞めてもいいとすら思える。でもFinalsまではやっぱり頑張ります(+願わくば次のICPC WFまで…)