CODE THANKS FESTIVAL 2017で解けなかった問題群
この記事はTSG Advent Calendar 2017の15日目の記事として書かれました。空いていたので放っておきます。
最近、多忙で競技プログラミングの進捗が埋めていないのですが、取り敢えず2問。それぞれ出てきた2解法ずつ取り上げます。
G - Mixture Drug
問題概要
N種類の薬品を可能な限り混ぜます。が、M組同時に混ぜてはいけないリストが存在するので、その中で何種類まで混ぜられるか答えてください。
N≦40
G: Mixture Drug - CODE THANKS FESTIVAL 2017 | AtCoder
半分全列挙とか浮かびましたが、上手く組み合わせる方法が思いつかずに死亡しました。コンテスト中はこれはさっさと諦めましたね…
解法1
取り敢えず枝刈り解。結局はただの最大独立集合なので、指数時間アルゴリズム入門を読むと解法が降ってきます。高々40頂点なので普通にlong longの中でビット操作で殴ります。
実際の実装で辺を落としたりするのはナンセンスだと思ったので、用いた枝刈りは
次数が1以下の頂点は選んでよい（ただし、2頂点からなる木があると死ぬので注意）
選ぶ際に周りに選んだ頂点があってはならない（これは、初めにNGリストなるものを作っておき、現在の情報とandを取って確認します）
残りの頂点全部を選んでも現在の最適解に届かないなら探索を打ち切る
の3つです。
Submission #1870578 - CODE THANKS FESTIVAL 2017 | AtCoder
なお、自分はVisual Studioを使う人なので、当然__builtin_popcountが使えず、折角なので実装しました。CPU命令として存在しているらしいので、多分遅いのですが…
解法2
bitDP+半分全列挙。普通半分全列挙といわれると、ナップザックがイメージできて、左右両側を全パターン列挙して、それを上手くまとめるイメージです。今回は初見のまとめかたでしたね…
後半半分は全列挙します。後半部の各パターンに対し、前半部で取れる最大集合（＝後半部選ばれた頂点に隣接しないものの中での最大集合）というのが存在します。解法1のNGリストを反転して利用すると一瞬で求まります。
前半部に対して「その集合の中で何頂点まで選べるか」というbitDPを用いると、「後半部の選んだ頂点数」+「前半部で選べる最大値」が最大値です。これを後半部全パターンに対して行うことで答えが得られます。bitDPで各パターンについて、1となっているビット1つを0にしたものから遷移していくので、O(n2n/2)というのが時間計算量です。
Submission #1841718 - CODE THANKS FESTIVAL 2017 | AtCoder
追記
自分が書いたコードがO(nlogn 2n/2)であることがTSG内のプロによって指摘されました。はい。
nglistを作ると、iと論理積を取ることでlogは落とせます（無くてもoklistで頑張れば出来ますが）
H - Union Sets
Union Findでくっつけていくのですが、2頂点を指定したQ個のクエリに対して「何回目の操作でその2頂点がくっついたか」を答えてください。
N,M,Q≦105
H: Union Sets - CODE THANKS FESTIVAL 2017 | AtCoder
LCAが浮かんで、2iだけ遡って何とか出来ないかな…なんて考えていたけど、辺に重みを付けるなんて発想もなく、各頂点・各時間についてその際のグループを把握してなきゃ出来ない気がして時間切れでした。
解法1
LCA。辺をつなげる際に「既にその2頂点がくっついているならその辺は追加しない」というルールを加えると、必ず森（閉路が無い）になります。実際Union Findを考える上でも不要です。これでLCAが使えます。
辺に何回目の操作であるか、という重みをつけてあげると、(x,y)というクエリに対してv=LCA(x,y)の時、パスx->v->yの辺の最大値が答えです。が、このままでは計算量は落ちません。これは、LCAの先祖を覚える配列の持ち方を流用して「頂点iから2j頂点分上に行く際に通る辺のうち、最大の重み」を記録しておくと、x,yを変えながら上っていく際に情報を落とさずに拾えます。
多分RMQに帰着すると楽なのですが、LCAでそれをやる手法を忘れました…そもそもLCAの実装もやったことなく、蟻本無しで脳内の実装をそのまま行ったら通ったのですが…
Submission #1871897 - CODE THANKS FESTIVAL 2017 | AtCoder
解法2
これは「なんか面白い解法無いかなー」と探していたら案の定プロがいたので掲載。
CODE THANKS FESTIVAL 2017 : H - Union Sets - kmjp's blog
にぶたんを行うことで各クエリに対してO(MlogM)で解くことが出来ます。が、毎回のシミュレーションで確認するのは1箇所のみでもったいないので、全クエリを並列で行うと、1回のシミュレーションがO(M+Q)で終了するので、セッティング含めてO((N+M+Q)logM)で終わります。ものすごく単純明快なのだけれども、何でこんな解法思い付くんだろう、はぁ…
