KUPC2012

その他のコンテスト コンテストの結果

結果。
8完+部分点で8位。無駄なWAはそんなに多くなくてよかった。今年もおもしろい問題が多くてさすがだと思ったし、去年に比べると全体的に難易度は上がっているにも関わらず参加者の正答数は全体的に増えているようで驚いた。
以下コンテストの流れ。

  • 開始前に方針確認。分からなかったらググることを厭わない。解が十分たくさんありそうなときは乱択を視野に。無駄なWAを出さない。十分な量の情報を順位表から得るために最初の問題は後回しにする。部分点は小さいので最後の最後までとりに行かない。
  • コンテスト開始。問題文が短めでちょうどよい位置にあるGにとりかかる。
  • 入力に特徴がある問題。とりあえずUnionFindでまとめるだけだが効率よくまとめるのはどうするか。
  • というか、クラスタ間がこれだけ離れてるなら適当に回転すれば分離できるはず。
  • ランダム回転した解を出す。WA。普通にロジックが間違えてた。
  • その後ランダム回転を何度も繰り返す解法を思いついた。適当に高速化と定数調整してAC。
  • 1問通しただけなのに時間を大量消費してしまった。順位表見たところ序盤の問題は特に罠もなさそうなので処理しよう。
  • A~Dは書くだけ。提出は後でいいや。
  • Eは見るからに乱択+リアクティブ。勝利条件緩いので適当に手を選ぶ解答つくるけど何故か全ケースTLE。
  • 修正方法がずっと分からず、まったく本質と無関係なところで時間消費してしまいイライラが募る。
  • どうせprintfとscanfが悪さしてるんだろうから、iostreamで書き換える。
  • 通った。ストレス解消にA~Dを一気に通す。
  • 順位表見てFかHか迷った末にやや正答数多めのFに行く。
  • これはBIT使ってRange Sum Queryやれば一応できるけど3e7はさすがに重そう。
    • 3e6だったことにコンテスト終了後気づいた。
  • しかし他の方法も思いつかない。仕方ないので書いてみるか。
  • 通った。AtCoderのジャッジってこんな速いのか。
  • 次に解かれているHに行く。
  • 偶数というのがどう効くのか全く分からない。とりあえず全マスの縦と横でxor重ねると何か答えっぽいのが出た。最小性とか全然分からないけどいろんな人が通してるからうまく行くだろと投げやりに出したら通った。
  • 残り時間は多くないがJを考える。えっ、こんな有名っぽい問題計算量落ちるんですか…。
  • ちょっとこれは手が出ないので部分点の自明解だけ出した。
  • 最後の問題の部分点も拾っとこう。
  • 頂点と辺のxorを組にしてflood fillすればTLEが厳しそうだが何とかなりそう。これ座標圧縮しなきゃいけないのかと思っていたら連結という条件がついていたので喜ぶ。
  • がりがり書く。無事部分点を拾えた。