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

Xmas Contest 2017 I問題 SAT Puzzle 解説

問題 | 解説まとめ

まずはコードです。
このコードでやっていることを解説します。

まず、各マスには「黒」または「白」ではなく、「黒」または「(1,1)~(4,4)」を割り当てることにします。
ただし、(j,k)は「j番目の白マスグループのk番目のマス」を表すものとします。
これを実現するには、黒を割り当てることを表す x[1]~x[36] の他に、マス
i に (j,k) を割り当てることを表す変数 x'[i][j][k] を用意し、条件を節として書き連ねていきます。
書かなければいけない条件は以下の通りです。

• 各マスは「黒」または「(1,1)~(4,4)」のいずれかちょうど１つに割り当てなければならない。
• 「(1,1)~(4,4)」が割り当てられるマスはそれぞれちょうど１つずつでなければならない。
• 「(j,1)~(j,4)」は連結でなければならない。
• 「(j,k)~(j',k')」(j≠j')は隣接してはいけない。

１つ目と２つ目

１つ目の条件では、各 i について x[i] と x'[i][1~4][1~4] のうちちょうど１つが真であれば良く、
２つ目の条件では、各 j,k の組について x'[1~36][j][k] のうちちょうど１つが真であれば良いです。
いずれにおいても「いくつかの変数のうちちょうど１つが真」というのを表現できればいいです。
これは、例えば a,b,c の3つの変数のうちちょうど１つのときは、

• (a V b V c)（少なくとも１つは真）
• (-a V -b)^(-b V -c)^(-c V -a)（どの２つを取ってきてもどちらかは偽＝多くとも真は１つ以下）

と表現できます。

３つ目

「連結」という条件をそのまま扱うのは難しいため、「うまく有向辺をはると根付き木ができる」という条件として実装します。
このとき、辺は小→大へのみ張れることとし、根は1番になるようにするとします。
つまり、k=2~4について、隣接のいずれかに1~k-1のいずれかがあれば良いことになります。
これを節で表すと、

• (x'[i][j][k] → V(x'[i'][j][k'] | i' ∈ iの隣接, 1 ≦ k' < k))

A→Bは「AならばB」の意味で、(A,B)が(真,偽)のときのみ偽となります。
これをCNFに直すと、

• (-x'[i][j][k] V (V(x'[i'][j][k'] | i' ∈ iの隣接, 1 ≦ k' < k)))

となります。（数式が見にくいのでソースコードも参考に・・・）

４つ目

隣接するマスが別グループであってはならないという条件。
ドモルガンでandの否定を否定のorに変換するのはSATの基本。

• (-x'[i][j][k] V -x[i'][j'][k']) (i' ∈ iの隣接, j ≠ j')

これで満点が取れます。

パズルをSATで解く話は昔、準急がJOIの春合宿の講義でしていて、すごく面白かったので自分でも遊んでみてたりしました。（なのに準急がこれ解けなかったのは意外だった）
楽しいので、他のパズルのソルバも書いて遊んでみてください。
初心者向けなのは数独かなぁ。
僕は美術館とひとりにしてくれを昔書きました。
僕のコードはここにあります。（honeyはこの問題の元になったハニーアイランドというパズルで、これは普通に枝刈り探索のコードです）（number_linkはgraphillionで書きました）
github.com