最大マッチングを貪欲する問題の証明典型テク

ARC092C - 2D Plane 2N Pointsの証明が話題になってたっぽいので問題を見てみたら、最大マッチング系貪欲の証明テクが詰まった問題だなぁと思ったので書いてみた。

問題概要

• 平面上に赤い点と青い点がある。
• 赤い点が青い点の左下である（つまりxもyも小さい）とき、それらはペアにできる
• 何ペア作れるか

解法

青い点をxの昇順に見て、マッチングできる赤い点があればそのうちyが最大のものとマッチングさせていく貪欲。

証明テク１：マッチングできるときはしてもよい

つまり、あえてマッチングさせないことによって答えが増えることはない。

なぜなら、ある青い点 A と赤い点 X をマッチングできるとき、

• マッチングさせる：残りの点集合から A と X が消える
  • メリット：答えが 1 増える
• マッチングさせない：残りの点集合から A が消える
  • メリット：X を残せる

で、「X を残せる」ことによって答えは高々 1 しか増やせないため、(マッチングさせたときの答え) < (マッチングさせないときの答え) となることはない。

ただし、A と別の赤い点 Y をマッチングさせる方が答えが良くなるという可能性はある点に注意。

このテクは結構出てくる。
使えるのは以下のようなケースのとき。

• 次数１の頂点がある：木でのマッチングなど
• マッチング相手に全順序がある：後述

例題：最近だとこれとか

証明テクテク２：マッチング相手に最弱の頂点があれば、それとマッチングさせてよい

以下のような状況を例に取って説明します。

緑の線の接続関係は同じとします。（灰色は何でもいい）

今、A にマッチングできる点は X と Y です。
X, Y とマッチングさせられる頂点集合を n(X), n(Y) とすると、n(X) ⊆ n(Y) です。
このとき、A と X はマッチングさせてもいいということです。
（少なくとも X か Y のどちらかとマッチングさせてもいいというのはテク１から言えますね）

なぜなら、

• Y とマッチングさせる：このとき残る辺集合を E とする
• X とマッチングさせる：このとき残る辺集合は(X と Y を区別せずに見ると) E + 辺(Y,α) となる

となり、辺が多い方が当然答えは大きくなるので X とマッチングさせても良いため。

マッチング相手が３頂点以上あった場合でも、その中で n(v) が最弱の頂点があればそれとマッチングさせて良い（つまり、どの他の頂点 u についても n(v) ⊆ n(u) が成り立つ v があれば）
大抵の問題ではマッチング相手の中に全順序があるが、一応そこまでは必要ない。

相性の良い競プロテク１：平面走査で変数を１つ消す

この問題の最後のピースです。
このままだと２変数あるので全順序とかも成り立ってないので工夫が必要です。

"A" として試す青い点を x の昇順で見ていくことによって x を消して１変数にすることができます。
すると y の大小だけの全順序が成り立つようになるわけです。

もう少し詳しく言うと、

1. A の x 座標 x_A は残っている青い点のうち最小である
2. 以降は x 座標が x_A 以下の赤い点は全部 x 座標が -∞ だと思っても答えは変わらない
3. A とマッチングできる頂点は x 座標が -∞ の赤い点のうち y 座標が y_A 以下のものである
4. x 座標が -∞ の赤い点の中では、y 座標は大きければ大きいほど "弱い"

ということから、最初に書いたような解法の正当性が示せる。

あとがき

貪欲法の問題は、正しいと確信できる程度の証明までして初めて解けた言えると思うんですが、
証明方法にも典型パターンというものは存在して、そういうのに積極的に触れていけばその内できるようになっていくと思います。

Xmas Contest 2018 ギャラリー編

XmasContest終了後にA問題の解答画像をtwitterに上げてくれてる人がたくさんいて嬉しかったので、展覧会を開くことにしました。

まずは画像一覧をどうぞ。
photos.app.goo.gl
ダウンロードするとファイル名がユーザ名になってます。

これだけだと芸がないので、Dendrogram描いてみました。

配色

まずは配色でクラスタリング。

Dendrogramの簡単な説明

木上で距離の近い頂点どうしは似ている、遠い頂点どうしは似てない、ということを表しています。
plotlyを使って描画しました。
plotlyのdendrogram機能には距離行列を入力すればいいです。

配色の距離の計算方法

４色×4色で重み付き二部マッチングをしました。
色どうしの距離は、RGB値をHSV値に変換して、H(色相)の差*1.0 + S(彩度)の差*0.2 + V(明度)の差*0.1 として計算しました。
色相の差は円環上の距離なので max(|A-B|, 1-|A-B|) のように計算しないといけない点に注意。

観察

jken_ullさんの作品とarmeria_betrueさんの作品は配色が （赤#F00, 緑#0F0, 青#00F, 黄#FF0）で完全に一致しています。
RGB値の差はあれど、この配色が多かったです。
黄色ではなくオレンジを使った人も結構いました。

１人明らかに様子がおかしい人がいるのはおいといて、259_Momoneさんの作品は結構独特な配色で、唯一灰色を使用しています。赤・緑のクリスマスカラーに白・灰と、かなり配色センスを感じました。
あと、Feunard_Luneさんの作品の配色は、なんというかパステルカラーでかわいい感じでいいですね。（AtCoderユーザ名の顔文字もかわいくて好きです）

塗り分け方

次に配色を無視して、塗り分け方でクラスタリング。

距離の計算方法

各領域を頂点とした完全グラフで、各辺に端点どうしの色が同じかどうか(bool)を書き込んだ行列を作ります。
で、行列どうしのハミング距離を距離としました。

観察

ceni1055さんの作品とant2357さんの作品が驚異のシンクロ率でした。色の割り当てまで同じです（驚） もはや間違い探しですね。（１箇所だけ違います）
ceni1055さんは昔自作されたソフトを使って解かれたようです。
ant2357さんは恐らくこのサイトを使われたのだと思います。
プログラムで解くとこういう感じになるんですね。

あと特徴が分かりやすそうなのは、文字の部分の塗り方でしょうか。
X以外が同じ色：Py2K4さん、semiexpさん、tatyam_primeさん（、と自分）
"Xmas"と"Contest 2018"をそれぞれ同じ色：kakira9618さん、skkytkstexhkさん
"Xmas"と"Contest"と"2018"をそれぞれ同じ色（未遂）：jken_ullさん（後で自分もやってみようとしましたが、下の方が不可能なことを証明できたので諦めました）

ビジュアル

最後に、色も塗り方も考慮した感じのクラスタリング。

距離の計算方法

各領域ごとに色の距離を計算してその和を取った。

観察

たしかに似てるような。（それ以外特に感想もない）
まぁ、おまけですね。

Xmas Contest 2018

Xmas Contest 2018 今年も開催しました。
コンテスト密度の高い中、ご参加いただいた皆さまありがとうございました。
楽しんでいただけたでしょうか？（よろしければアンケートお願いします）

今年の運営は４年連続のじゃっぷるさんと、2010~2014の運営の本家本元hosさんとやりました。
hosさんが数学的に面白くて奥深い問題とかをどんどん出していてすごかったです。さすが。
特にxorのやつはまじですごいのでおすすめです。クッソむずいですが。
diceの問題も楽しかったです。（楽しくなって作った謎ゲーム）

自分が原案の問題の解説を書いておきます。

Mail.Ru Cup 2018 Round 1

久しぶりにCFに参加した。（開始10分後くらいに偶然TLを見て気づいた）

A

問題文が難しい＞＜

B

まぁ。

C

として、正しいかチェック。

D

累積xorをとって長さn+1の数列Xを作る。
Xから同じ数を２つ取ってきてその間を選ぶとxorが0になる。
つまり、とすると、を最小化すればいい。
操作はある場所以降をflipに対応してるので、組み合わせると最初以外の要素を好きにflipできる。
は一定だが、その範疇では好きに配分できる。半分ずつくらいに配分すると最小になる。

E

「1行目に0を、2行目に1を集める」というのを標準形とする。
任意の状態←→標準形も標準形←→標準形もs回の操作で変換できるので、3s回でできる。

F

とりあえず各点を長さ0の線分で覆えば達成はできる。
隣り合う線分の間を繋ぐと答えが１減る。
"間"の線分を交差しないようにできるだけたくさん選ぶ問題になる。
縦と横の二部グラフで最大独立集合を取る問題になってあとは復元とか頑張って。
二部グラフの最小点被覆、最大安定集合 (最大独立集合)、最小辺被覆を総整理！

G

葉から順に消していく。

• ビット数=1のコミュニティは消す。
• 残りのコミュニティで常にs[i][v]=1,s[i][u]=0になってるiが無ければvをuにくっついてる葉としてvを消す。

コミュニティを全部消せればYES。（連結になってなかったら適当に繋ぐ）
実装はbitsetを使ってO(2000^3/64)

• a[i] = s[i]
• d[i] = a[j][i]=1であるようなa[j]の&を取ったもの(iビット目は0にする)

を持って、

• a[i].count() == 1があったらa[i]を消して、立ってるbitをjとしてd[j]だけ再計算
• d[i] != 0があったらiを葉にする

って感じでやる

lewin氏の別解頭良さそう。
完全グラフを作って辺uvの重みはs[i][u]=s[i][v]=1になってるiの個数にする。そのグラフでMST(minじゃなくてmaxだけど)を求めてそれをチェックすればいい。
重みを全部計算するのは長さMのbitsetで&とpopcountをすれば/64できる。（CFだと/32なんだっけ...）

感想

普通に楽しかったしCFもっと出ていきたい。（とりあえずIGM,LGMに戻すぞー、Nutellaになりたい）

Knapsack And Queries - JAG夏合宿2018 day2 D

D - Knapsack And Queries
良く出来てるなぁ。

queueをstack２つで実現できるっていう知る人ぞ知るテクがある。
純粋関数型データ構造界隈とかで有名らしい。

どうやるかというと、

• queueにpush
  • 単にstack2にpushする
• queueからpop
  • stack1が空でない：stack1からpop
  • stack1が空：「stack2からpopしてstack1にpush」をstack2が空になるまでやる

計算量は、各要素が高々2回ずつしかpushされないことから、均しで線形であることがわかる。

[図1: ２つのstackからqueueを作る様子]

これをそのまま使うと例えば以下の問題が解ける。

• 正整数の集合Sがあり、最初は空である。Sに対する以下のクエリを処理せよ。
  • push x：Sにxを追加する
  • pop：Sの要素のうち最も古いものを削除
  • gcd：Sの要素のgcdを答える
• 計算量は O(クエリ数*gcdの計算量)

ただ、これだとsegtreeを使ったりするのと区別ができないのでコンテストで出題するのは難しい。

元の問題の解法に話を戻すと、あとはdpテーブル２つから答えを計算できればいいけど、これは片方のテーブルを全部舐めてもう片方のテーブルでスライド最小値をすれば良い。
なるほど、このテクでは２つの要素をマージできる必要はなくて、２つの要素から答えを計算できれば十分なんだなぁ。
作問が上手すぎる。

ちなみに、dequeもstack２つで実現できる。（償却計算量は同様に線形）

Amortize analysis of Deque with 2 Stack from Ken Ogura

www.slideshare.net

CodeForces #485 Div1 C AND Graph

Um_nik回のCが面白かったので。
あと、自分の解法が想定解と違ったっぽいので。

問題概要

ビットの二進数 が 個与えられる。
のとき頂点 に辺を張ったグラフの連結成分数を求めよ。

制約

• 
• 
• 
• はdistinct

パソコン詳しくない系競プロ勢向け正規表現

この記事は「競プロ!!」 競技プログラミング Advent Calendar 2017の記事として書かれたものです。
上のリンク先にはリンクが張られていないので書いておきますが、競プロadvent calendarはもう１つあります。
昨日の記事 / 明日の記事（明日の記事がすでにあるのなーんでだ？）

はじめに

とりあえずカレンダーに登録してからネタを考えていたのですが、そういえば正規表現って使ったことない人結構いるよなぁと思ったので軽く紹介します。
正規表現、かなり強力なツールなので使えるようになる価値は大いにあると思います。
入力チェッカを書くときとか重宝しているので布教しておきます。

正規表現入門

正規表現とは、文字列の集合を一つの文字列で表現する方法の一つである。(wikipediaより)
強そう。
まずは例からみてみましょう。

例：にゃーん

nyaa*nという正現表規を考えます。
正規表現において '*' は「直前のものを0回以上繰り返す」という意味です。
つまりこの正規表現には "nyan"、"nyaan"、"nyaaaaaan" のような文字列がマッチします。

なにが嬉しいのか

正規表現を使うと主に以下のことができます。

• ある文字列が、あるパターンに当てはまっているかをチェックする(match)
• ある文字列から、あるパターンに当てはまる部分を取り出す(find)

上は競プロのYES/NO問題とか、入力チェッカとかに使ってます。
下は簡易的なスクレイピングとか文書からなんらかの情報を取り出したりだとか一斉置換（例えば「"~~~"」を「'~~~'」に一斉置換したいとき）とか、色々使ってます。
この記事では下は扱いませんが、興味が湧いたら使い方を調べて使ってみてください。

よく使う機能一覧

正規表現には '*' の他にも様々な特殊文字が用意されています。
そのうち僕が特によく使うものの一覧を書いておきます。
「例」のリンク先には正規表現の例とテストケースが書かれていて、Match resultで青くなっている行のみがその正規表現にマッチすることを表しています。

文字	意味	備考
^	行頭	例
$	行末	例
*	直前のものを0回以上繰り返す	例
+	直前のものを1回以上繰り返す	つまり上の例はnya+nとも書けます
?	直前のものを0回または1回繰り返す	例
{n}	直前のものをちょうどn回繰り返す	例
{n,m}	直前のものをn回以上m回以下繰り返す	例
{n,}	直前のものをn回以上繰り返す	例
(〜)	括弧内をひとまとめにできる感じ	例
｜	または	例
.	任意の文字にマッチする	例 .*で任意の文字列を表せる
[〜]	括弧内のいずれかの文字にマッチする	例
[a-z]	a-zのどれかにマッチする	例
[^〜]	括弧内以外の文字にマッチする	例
\d	数字(0-9)にマッチする	例
\w	[A-Za-z0-9_]と同じ
\s	空白（スペース/タブ/改行）にマッチする	例

まだまだ便利な機能があるので興味が湧いたら適当に調べてみてください。

競プロで正規表現を使う

C++での使い方

C++11からstd::regexが追加されたのでそれを使います。
以下は入力された文字列が"にゃーん"かどうかを判定するプログラムです。

#include <regex>
#include <iostream>
using namespace std;

int main() {
  regex re("nya+n");
  string s;
  while (cin >> s) {
    bool res = regex_match(s, re);
    cout << (res?"YES":"NO") << endl;
  }
  return 0;
}

ideone

regexのコンストラクタでは正規表現をコンパイルしていて重いので何度もマッチングする場合はこのようにコンストラクタを１回しか呼ばないように書いた方がいいでしょう。

応用例

CODE FESTIVAL 2017 A - AKIBA
場合分けをとかをするとWAを出しがちなのであらかじめ全列挙しておいてチェックするみたいなのが想定解でしたが、正規表現を使うとあっさり解けて嬉しいということに後で気づきました。

#include <regex>
#include <iostream>
using namespace std;

int main() {
  regex re("A?KIHA?BA?RA?");
  string s;
  cin >> s;
  bool res = regex_match(s, re);
  cout << (res?"YES":"NO") << endl;
  return 0;
}

あとは、この問題を意識して作ったこの問題もどうぞ。（解説記事）
動的に正規表現を組み立てると解ける問題です。
ただこういうことをする場合は、C++の正規表現は実用面ではともかく競プロ的には微妙な実装なので、D言語などを使うと良いでしょう。

他の応用例はyurahunaさんの記事に載っているので是非お読みください。

まぁでも基本的には競プロそのものに使う場合は少し楽になる程度の嬉しさしかないケースが大半かもしれません。

正規表現で入力チェッカを書く

僕は最近はずっとwriter/testerをするときは正規表現を使って入力チェックをしていて、かなり快適なのでオススメしておきます。

以下は僕が使ってるコードです。

#! /usr/bin/python
import re, sys, os

re_num = '(0|-?[1-9]\d*)' # 整数の正規表現（負数/0にも対応）

def check(fname, f):
  lines = re.split(r'\r*\n',f.read()) # windowsの改行コードにも対応
  global li; li = 0
  def get(): # 次の行を取得
    global li
    in_s = lines[li]; li += 1
    return in_s
  def getf(fmt): # 正規表現チェック付きで次の行を取得
    in_s = get()
    assert re.match('^%s$'%fmt, in_s), 'format : line {}'.format(li)
    return in_s
  def geti(): # 次の行を整数１個として取得
    return int(getf(re_num))
  def getis(n): # 次の行を整数 n 個として取得
    return list(map(int, getf('{0}( {0}){{{1}}}'.format(re_num,n-1)).split()))
  def getil(*l): # 次の行を整数 hoge 個として範囲制約付きで取得（引数には長さ２のリストをhoge個渡す）
    if isinstance(l[0], int):
      val = int(getf(re_num))
      assert l[0] <= val <= l[1], 'out of range : line {}'.format(li)
      return val
    vals = getis(len(l))
    for nx,nl in zip(vals,l):
      assert nl[0] <= nx <= nl[1], 'out of range : line {}'.format(li)
    return vals
  def getils(l,r,n): # 次の行を l 以上 r 以下の整数 n 個として取得
    return getil(*[[l,r]]*n)
  def eof(): # EOFチェック
    assert lines[li:] == [''], 'EOF'

  MN = 10**5
  MX = 10**9

  n = getil(1,MN) # 1 以上 MN 以下の整数を読み込む（１個だけのときは(下限,上限)を引数として渡す）
  a, b = getil([1,MX], [1,MX]) # 1 以上 MX 以下の整数を２つ読み込む（getils(1,MX,2)とも書ける）
  eof()

  print('o')


if __name__ == '__main__':
  for fname in sorted(os.listdir('../in/')): # 
    if fname[0] == '.': continue
    sys.stdout.write(fname + ': ')
    with open('../in/' + fname) as f:
      try:
        check(fname, f)
      except AssertionError as e:
        print('invalid! ({})'.format(e))

コメントなしバージョンもgistに上げておきます。
C++でも例えば「Sは小文字アルファベットのみからなる長さ10以下の文字列である」を "[a-z]{1,10}" みたいに正規表現でチェックしたりするだけでもいい感じだと思います。
testlib.hを使っている人は、たしかtestlib自体にそういう機能があったはずなのでそれを使うといいかもです。（testlib.h内で"regex"で検索かけるとそれっぽいところが見つかるはず）

おまけ：{}とか使うとやばい正規表現が作れるんですね。
Ideone.com - 5f3WAn - Online Go Compiler & Debugging Tool
Ideone.com - Glf1Wl - Online C++0x Compiler & Debugging Tool