ICPC 2014 Taichung Regional Contest 参加記

12問 (A-L) のうち8問 (ABDEFGIJ) を解いて大学別4位（チーム別8位くらい?）でした。
上から上海交通・国立台湾・京都・筑波らしいのでさすがにいくらかはスロット確保できてるはず。

問題別に起こっていたこと

ちょっと時系列をちゃんと覚えきれていないので問題別に何があったかを軽く。だいたいAC順に。
解法に触れちゃっているところもあるので練習会とかで使うかもしれない場合はお気を付けください。
（といっても例年通りだとジャッジデータが公開されるか怪しいところはありますが。）

問題リンク: http://icpc2014.pu.edu.tw/2014%20ACM-ICPC%20Problem.pdf

A問題
  • あみだくじのシミュレーション
  • ソートしてシミュレートするだけ
  • サンプルが一発で合わないものの逆変換のテーブルを作ってしまっていただけだった
    • さらに逆にするコードを追加して提出
  • First AC かと思ったら秒単位の差で他チームに持っていかれたらしい
B問題
  • 一般グラフの辺の重みの総和からMSTの辺の重みの総和を引くだけらしい
  • 普通の Kruskal 法で OK
E問題
  • 幾何ライブラリ貼るだけ
I問題
  • 極座標ではあるけど特に気にせず二部マッチングでOK
  • 座標圧縮して二部マッチングライブラリに通す
J問題
  • I問題をやる前か直後くらいにsを全列挙してハフマン符号化みたいに作ればOKと聞く。
  • 最大ケースをローカルで食わせると頑張っても1ケースあたり4秒くらいかかる
    • 1入力あたり5ケースまでなのでTLEだと思ってしばらく放置する
  • Dが詰まりまくっていたので半ば自棄になって「とりあえず出してみよう」となる
    • まさかのAC。ジャッジ入力が弱かったか手元のマシンが弱かったか。
G問題
  • zerokugi君と二人でDに悩まされていたらn_vip君から解法が飛んでくる
  • 解を最大化する1の置き方は1の数のみによる
    • 正方形っぽい形にまとめて0はその外側に迂回させる
    • n <= 11 なのでうまくやれば外を迂回する部分をすべて最外周に逃がすことができそう
  • テーブルを求めてもらって埋め込み。AC。
D問題
  • 今回一番闇が生えてしまった問題
  • 割と早い段階で木DPということで回ってくる
  • Balanced にならない頂点は黒でなければいけないということを見落とす
    • そこに気付くまでにWAを食らいまくった上にそこに気が付いてからも修正が不十分でさらにWAを食らいまくる
    • zerokugi君に書き直してもらっても同じバグを2人そろって入れてしまったり……
  • 結局8WA食らってしまい、取りかかった順番だと4番目くらいだったのに通った順番だと7番目でした。
F問題
  • Dを通したころにはもうCに嫌気がさしていたので考えてみる
    • すでに使う行を固定すれば列の問題になることは聞いている
  • 列の問題として考えると使用する区間の長さは [k, 2k] の範囲内にはなっていそう
  • なんか微妙な制約あるし定数倍改善でゴリ押せるタイプの問題じゃないかと疑う
    • nm <= 10^6 なのに n <= 600
    • 別に n <= 1000 でも大差ないのでは……
  • 転置してループ順を変えるとうまくSSE化できそうな感じになったので試しに書いてみる
    • まさかのAC（二度目）
    • Jが通った後だったのでこれもジャッジ入力が弱いというのも少し期待していたり
C問題
  • また N Queen か
    • ナイトと同じ方向への移動が追加されている
  • 数え上げも含まれているからDPか全探索か
  • n個おける場合の数え上げとかやってみたけど結局うまくまとまらず。
    • 他チームの話だと普通のバックトラックで通るらしい?
H問題
  • zerokugi君曰く「kd-Treeで通せそう」らしい
  • Fが終わった時点で残り30分を切っていたのでCに注力することに。

まとめ

  • またCJCにペナルティ差で負けてしまった……
    • 昨年同様のスロット割り当てならWFに行けるとは思うので今度こそはリベンジしたいですね
  • 2人そろって同じバグを入れてしまうというのはどう対策すればいいんだろう
    • 今回はzerokugi君にバグ入りコードと長時間つき合わせてしまったのが原因な感じはあるのかも