Mail.Ru Cup 2018 Round 1

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

A

問題文が難しい><

B

まぁ。

C

 ans_i=n-l_i-r_i として、正しいかチェック。

D

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

E

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

F

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

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を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のコード