日記 - 2012-11
2012-11-04
模擬アジア地区大会
ICPCの模擬アジア地区大会に参加しました． A,C,Gを解いて22位．
チームの実力的にはあとDとHくらい解けた気がします． Bは解き直したら1時間かけて実装するだけだったけど，そこまでの時間があったかは微妙．
明らかに時間配分がうまく行っていませんでした． 理想的には紙上でアルゴリズムを詰める→PCを使ってアルゴリズムをコードに落とす，とすべきですが， 開始直後に問題文の読み合わせをしてから即座に解けそうなものがなかったので @eagletmt さんに G の重い構文解析を投げてしまい， さらに G を実装している間に裏で A，C，E(これは結局方針が違って解けなかったけど) を解くという時間配分になってしまいました． これがまずかった． 本来ならこの手の重い実装こそ十分に整理してから書くべきです．
今回は A と C が実装簡単，D が実装するだけで実装量中程度， B と G が明らかに解けるけど実装重い，その他はアルゴリズムを考える重さという感じでした． したがって A の方針が早期に見えた時点で PC を代わって，G は紙実装に移ってもらうべきだったと思います． D の幾何も紙で整理すれば書きやすい．
E に関しては区間DPが見えなかったので完全に実力不足ではあります． H はもうちょっと考えれば解法に気付けたはず． なまじ E で嘘 DP が見えてしまい，さらに計算量も落とせてしまったのでそっちにかかりっきりになってしまい，H に戻れなかったのが不幸でした． E を途中で諦めれば良かったのかもしれないけど，解いてるときは当然正しいと確信していてサンプルもほぼ通ってしまうので難しいですね……．つらい．
2012-11-02
Real-world Competitive Programming
最近卒研のために読んだ論文で，グラフの最小コストカットを使ったエネルギー関数の最小化があって面白かったです．
- Shift-Map Image Editing
- What energy functions can be minimized via graph cuts?
- Improved Seam Carving for Video Retargeting
このへん．
概念的には，まずエネルギー関数に使われている変数(たとえばv_n)を0/1しか取らない変数(の関数)で置き換えて表現し(F_n(x_n) = x_n*v_n のように)， x_n を頂点としたグラフの最小カットで x_n が Source 側にあれば 0 ，Sink 側にあれば 1 とします． このときグラフの辺は「カットすることで x_n を Source 側か Sink 側か決める」という性質を持つことになります．
したがって，仮に F_n(0) < F_n(1) だとすると 1 ，x_n を Sink 側に決めるようなカットをしたときに余分なコスト F_n(1)-F_n(0) が生じるように辺の容量を決定すると 2 ，最小カットとは最小の余分コストで全ての x_n の 0/1 を決定する操作に他ならないので， エネルギー関数の最小化が達成できます．
この手法そのものも相当賢くて興味深いですが，それよりも競技プログラミングで親しんできた最大流問題とこんな形で出会うというのが面白く感じました． 競技プログラミングで使われるアルゴリズムは当然競技だけのものではなく，ほとんどが実際の研究から生まれたものであるというのは分かってはいたけど 改めて自分の研究として出くわすと，やはり競技で培った知識は無駄じゃないんだなあと再確認できる気がします．