Knapsack And Queries - JAG夏合宿2018 day2 D

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

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

どうやるかというと、

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

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

f:id:snuke:20180918164151p:plain
[図1: 2つのstackからqueueを作る様子]

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

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

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

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

ちなみに、dequeもstack2つで実現できる。(償却計算量は同様に線形)

www.slideshare.net

正規表現は便利なので知らない人には少しだけでも知ってほしい(競プロ勢向け)

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

はじめに

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

正規表現入門

正規表現とは、文字列の集合を一つの文字列で表現する方法の一つである。(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のコンストラクタでは正規表現コンパイルしていて重いので何度もマッチングする場合はこのようにコンストラクタを1回しか呼ばないように書いた方がいいでしょう。

応用例

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(): # 次の行を整数1個として取得
    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 個として範囲制約付きで取得(引数には長さ2のリストを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 以下の整数を読み込む(1個だけのときは(下限,上限)を引数として渡す)
  a, b = getil([1,MX], [1,MX]) # 1 以上 MX 以下の整数を2つ読み込む(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,1)~(4,4)」が割り当てられるマスはそれぞれちょうど1つずつでなければならない。
  • 「(j,1)~(j,4)」は連結でなければならない。
  • 「(j,k)~(j',k')」(j≠j')は隣接してはいけない。

1つ目と2つ目

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

  • (a V b V c)(少なくとも1つは真)
  • (-a V -b)^(-b V -c)^(-c V -a)(どの2つを取ってきてもどちらかは偽=多くとも真は1つ以下)

と表現できます。

3つ目

「連結」という条件をそのまま扱うのは難しいため、「うまく有向辺をはると根付き木ができる」という条件として実装します。
このとき、辺は小→大へのみ張れることとし、根は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)))

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

4つ目

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

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

これで満点が取れます。

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

Xmas Contest 2017 H問題 Ango 解説

問題 | 解説まとめ

リアクティブ・encode/decode系の変わった問題。
部分点はmax(x)に関する関数にしてもよかったかなぁ。

部分点1

割と効率が悪くてもACできますがそこまで簡単ではないと思います。
例えばNが小さければフィボナッチ数列でいけますが、N=300だと厳しいです。
解答例としては、xを乱数にしたり、和が被らないようなxを愚直に探索するなどがあります。
N=300なら2つ選んだ時の和というのはあらかじめ列挙できるのでクエリに答えるのはあまり難しくありません。

部分点2

xは乱数でもおそらく被らないと思いますが、Nが大きいのでクエリへの応答が困難です。
ここで、(a^2+b^2)と(a+b)さえ分かっていれば a も b も求まるということを唐突に思いつきます。(そもそも僕が数日悩んだのち唐突に思いついたため、こうとしか解説できず)
S=(a^2+b^2), T=(a+b)として、ab=(T^2-S)/2が求まり、|x-y|=sqrt(S-2ab)が求まり、T+(a-b),T-(a-b)として a, b が求まります)
これを実現するにはGETA=500000などとしてx_i = i^2*GETA+iなどとしておけば、S=sum/GETA, T=sum\%GETAとして S, T が求められます。

部分点3

p=900001などとして、全ての演算の法をpとして計算します。
mod計算で難しい部分はsqrtですが、今回は1~400000についての二乗mod pの値を前計算しておけば十分です。(効率的に計算したい人はこちらを)
ちなみにsqrt(x) mod pの値は一意に定まらず2つありますが、正負が違うだけなのでどちらでも良いです。

Xmas Contest 2017 G問題 Maze 解説

問題 | 解説まとめ

作問slackに最初に投稿した問題。
今年はこんな感じの問題にするぞという思いも込めて作りました。

解法:ペイント等でゴールのラインに縦線を引き、バケツツールで塗りつぶすと・・・

f:id:snuke:20171226174325p:plain

答え:ACEFGHNPQSYZ
ペイントってBFSができるんですねぇ。

おまけ:迷路を生成して遊べるprocessingのコード

Xmas Contest 2017 F問題 Tree Disassembly 解説

問題 | 解説まとめ

1~5は全探索ができる大きさのランダムケース、6~10は大きいけれどそれぞれなんらかの性質を持ったグラフとなっています。
手元で全ての答えを計算して埋め込めばいいですね。Nが全ての入力で異なるので、ケースの特定も簡単です。

1~5

1は手計算でも頑張ればできるかも。
2は各辺について色を全通り試して判定しても間に合います。
3以降はちゃんと枝刈り探索などを書かないと厳しいと思います。

想定解はgraphillionで殴る」です。
グラフの列挙したりするのが得意なライブラリです。
辺に重みをつけて重みを最大化/最小化する問題なんかも解けます。
数え上げおねえさんを救うために開発された(page3)ライブラリで、はなく(page4)、ZDDを使ったすごいやつです。強い。
パスの他にもサイクルや木や森やクリークや...といろんなグラフが扱えるし、それらを組み合わせたものを列挙みたいなこともできます。結構いろいろできます。
例えば今回の問題の1~5は以下のコードで解けます。

from graphillion import GraphSet

def read():
  return map(int, raw_input().split())

n = read()[0]
edges = [tuple(read()) for i in range(2,n*2)]

GraphSet.set_universe(edges)
trees = GraphSet.trees(is_spanning=True)
comps = trees.complement()
ans = comps&trees

print(len(ans) % (10**9+7))

こういうアルゴリズム系のライブラリはpythonが結構多いのでpython書けるとだいぶいい感じです。
やってることとしては、辺をタプルで持ったリストを作って、それをグラフに登録し、全域木(trees)を列挙し、その補グラフ(comps)を列挙し、それらの積集合を取ってそのサイズを求めています。
"列挙"と言っても、全部を実際に列挙しているわけではなく、実態としては条件を満たす集合の圧縮表現を構築しているだけで、かなり速いです。
自分はまだあまり使いこなせてはいませんが、それですらかなり強力なライブラリだと思うのでオススメです。

6~10

6~10はそれぞれのグラフをビジュアライズするとどんなグラフかが見えると思います。
グラフのビジュアライズはgraphvisやjs製のそれっぽいライブラリを使うと良いでしょう。
僕はこのサイトをよく使います。(超便利、EMKさんありがとうございます)

6

f:id:snuke:20171226144116p:plain
K4が頂点どうしで繋がって木っぽくなっています。
この問題の性質を考えると、関節点で分離して独立に解いて掛け合わせると良いことが分かるので、K4の答え12を33乗すれば良いです。

7

f:id:snuke:20171226144752p:plain
幅2の管状になっていて木幅が小さいので列単位で適当なDPをすれば解けます。
実際に考えて見ると、実は状態は「片方の色が繋がっててもう一方が繋がってない」の実質1通りしかないので、単に2*6^50が答えになります。

8

f:id:snuke:20171226145433p:plain
これを見ても104の次数が高そうなことくらいしかわからないので、graphvisの方の画像を見た方がいいですが、サイズがデカすぎるので載せないでおきます。
f:id:snuke:20171226145439p:plain
代わりに、小さい版を作ってビジュアライズしました。
こんな感じで多角錐みたいになってます。
N=4から実験して見ると、12,28,60,124,252...となっていて、これは2^N-4です。
なぜこうなるかを考えてみると、周りの輪っかの辺の色を決めると、全部同じ色の時以外はスポークの辺の配色が2通り存在するので(2^(N-1)-2)*2という感じ。
f:id:snuke:20171226153239p:plain

9

f:id:snuke:20171226154355p:plain
なんか投網みたいな形です。
良く考えると輪っかサイズが10になった08.txtを10個繋げたのと同じ状況なので、(2^11-4)^10が答えです。

10

f:id:snuke:20171226155051p:plain
これもgraphvisの方が見やすいです。
f:id:snuke:20171226155049p:plain
グリッドの最後をK4で帳尻合わせた形になっています。
この問題の性質を考えると、次数2の頂点は片方が赤でもう片方が青になるだけなので、答えを2倍して取り除いても同じだということがわかります。それを隅から順番にやっていくとK4が最後に残り、(2^99)*12が答えであることがわかります。