とこはるのまとめ

多分考えたことがまとまっているはずです。きっと。おそらく。

競プロとLP双対まわりの話で最近知ったこと

こんにちは。tokoharuです。

これは
Competitive Programming (その2) Advent Calendar 2016 - Adventar
の12/7の記事です。

問題も稀にしか確認しなくなりましたが最近得た知見をここで報告・宣伝しておきます。少々マニアックな記事です。

概要

私のtwitter(鍵)を確認している人はご存知かもしれませんが、二年前に公開したドキュメントhttp://tokoharu.github.io/tokoharupage/docs/formularization.pdfを改訂しました。内容はフローとかLPとか双対とかそのあたりの話です。元々は自分だけ読めればよかったものを少しずつ他の人に読めるものに変えている途中なのでまだまだ読みにくいかもしれません。特にLPとかの話は情報系学科の人でも触りくらいしか知らないでしょうし...

それから最初のほうにLPを用いた細かな話をしているので挫折する方もいるかもしれませんが、Project Selectionあたりの話はちょっと毛色が異なるし、おそらくこのドキュメントで最も実用的な箇所なのでそこを読むのがよいと思います。

知見1(最小費用流問題の双対っぽい問題への対処)

LP双対をとって最小費用流問題に帰着させるような問題は双対という操作を覚えないといけないし、操作を間違えやすい意味で厳しい問題という印象でした。しかし、最近yosupoさんの力を借りることでいい感じに解釈して辺を張ることに成功したかと思います。
この考え方をマスターすれば、例えばHow to create a good game(AOJ-ICPC 1100点, 2016/12/6現在)の解法を紙を使わず頭の中だけで構築することも可能かと思います。

知見2(牛ゲーの罠)

書いた文章をもう一回読んだり検証したりして気づいたのですが、
AOJ0304はデータセットが甘いっぽいことに気づきました。
今後こういう問題を作るときはこういうケースを仕込んでおいてガンガン落としていきたいですね。
詳しくはこの記事をご覧ください :
tokoharuland.hateblo.jp


今後

最近はフローで解くと部分点でさらに深い洞察を踏まえることで高速なアルゴリズムを導く系統の問題が増えてきたような気がします。そういう問題は結局はフローの特殊ケースであるといえることもあり、こういうのもいずれ体系立てれたりしないかなぁと思ったりしますがそんなにちゃんと考えてないです。背後に何かいい感じのものがあったりしないかなぁ。

今年の JOI2016 春合宿「最悪の記者2」, KUPC2016 H「壁壁壁壁壁壁壁」なんかの問題はこの意味で非常に興味深いですし、作問者の方は素晴らしい問題をありがとうございます。この系統でいくとhttp://codeforces.com/contest/724/problem/Eもですね。この辺は深く理解したいですね。

次のアドベントカレンダー担当者

明日はskyさんとyosupoさんですね。

skyさんとは長い付き合いのはずなのにあまり話してない気がするのですが、
きっと彼の印象に残ってるイベントとぼくの印象に残っているイベントはかぶってる気がするので楽しみです。

yosupoさんは言わずもがなで、どんなネタを提供してくれるのか楽しみです。