Google Code Jam 2016 Round 1B 落ちたー😇 (id: sakai)
https://code.google.com/codejam/contest/11254486/dashboard
#codejam #gcj
A. Getting the Digits
整数係数の線形連立方程式の整数解を求めればよい。 とりあえず自作の OmegaTest に投げてみた。
B. Close Match
探索頑張れば良さそう。 Smallはブルートフォースで楽勝。 Largeは面倒そうなので後回しにしてたら時間なくなった。
C. Technobabble
落ち着いて考えると、順序は関係なくて、結局各トピックがrealかfakeかだけが問題だと分かるので、Smallは最大2^16通りについてすべて確認するだけ。 Largeは各トピックがrealかfakeかを変数としてrealなトピック数を最小化する Pseudo Boolean Optimization (PBO) 問題として自作PBOソルバに投げてみたが、Time expired 。
このPBOをよく考えてみると、結局、(重み無し)集合被覆問題で、 Discrete Optimization のコース https://www.coursera.org/course/optimization のオマケ課題の集合被覆問題のをやっておけば……とちょっと思った。 ただ、 https://ja.wikipedia.org/wiki/%E9%9B%86%E5%90%88%E8%A2%AB%E8%A6%86%E5%95%8F%E9%A1%8C によると「k-set cover problem については、k=2 のとき、最大マッチング問題の解法を応用することで容易に最適解が求められる」とのことで、この問題は 2-set cover problem だと思うので、これが想定解だったのかなぁ。 最近たまたま Linear and Discrete Optimization https://www.coursera.org/course/linearopt の復習に、割当問題の主双対アルゴリズムを実装したりしてたので、それを活用できず悔しい。
失敗点としては、よく確認もせずPBOで C Large を解けそうと思ってしまったのが失敗で、面倒だけど堅実に解けそうな B Large に取り組むべきだったか。