文字列の周期性判定

以前の記事「文字列の頭良い感じの線形アルゴリズムたち」で、

この配列を使うと文字列検索や周期性の判定などが高速に行えるようになるのですが、
その辺りの説明は他のサイトにお任せします。

と書いたところ、周期性の判定の方に関して「"他のサイト"なんてものはない」と言われてしまったので、書きます。

文字列 S が与えられる。S[0~i] の最小の周期長を全部まとめて O(N) で求めよ。

という問題を考えます。例えば、

abababcaa
122222778

という感じ。(上がSで下が答えの配列)

例えば、"ababa"なら"ab"を繰り返せばいいので 2 という感じ。

解法

KMPでテーブルを作ります。

んで、「i - KMP[i]」が各場所の答え(1-indexed)

簡単な解説

「最小の周期長」=「k 文字ずらしたものが元の文字列と一致するような最小の k (k>0)」

例えば、"ababa"は

ababa
__ababa

2 文字ずらした時に初めて同じ列にある文字同士が一致するので 2 が答え。

この同値関係は この記事 が参考になるかも

で、「k 文字ずらしたものが元の文字列と一致するようなhogehoge」ってKMPそのものみたいなものですよねという。

練習問題

SAT solverでパズルを解いた話

SAT solverで「数独」「美術館」「ひとりにしてくれ」を解きました。

Githubにあげました。

めっちゃ楽しかったので準急に多謝だー。(JOI春合宿で講義をしてくれた)

準備

SAT solverをインストールしましょう。

僕はminisatにしました。(なんか入れるのに苦労したけど)

SATを知らない人は適当に調べましょう。

流れとしては、

  • パズルを連言標準形(CNF)の論理式にして
  • SAT solverに投げて
  • ビジュアライズする

って感じです。

数独

多分一番簡単です。

「x1,x2,...,x9 のうち、ちょうど1つだけがtrue」

という式が書ければ勝ちです。これは、

  • x1 or x2 or ... or x9 (1つ以上であるという制約)
  • 全てのi,jのペアについて、!xi or !xj (2つ以上ないという制約)

で実現できます。

あとは、X_i,j,k(i行目j列目がkであるならtrue)という変数を使って

  • 行にちょうど1つだけkがある
  • 列にちょうど1つだけkがある
  • 3x3のグループにちょうど1つだけkがある
  • 各マスにはちょうど1つだけ数が割り当てられている

という条件を書いてやればいいです。

美術館

これも基本的

変数は、X_i,j = i行目j列目に明かりを置くならtrue です。

  • 照らしあってはいけない
  • 照らされていないマスがあってはいけない
  • 黒マスに明かりがあってはいけない
  • 周りに 0 個ある
  • 周りに 1 個ある
  • 周りに 3 個ある
  • 周りに 4 個ある

は簡単(実際にプログラムとして書くのはちょっと面倒だけど)で、問題は

  • 周りに 2 個ある

です。これは、

  • どの3個を取り出してorを取ってもtrue
  • どの3個を取り出して否定のorを取ってもtrue

の2つの条件にすると楽に書けます。

ちなみに、フィールドの周囲に番兵を置くとかなり実装が楽になります。

ひとりにしてくれ

  • 各列に同じ数が2つ以上残ってはならない
  • 黒マスが隣り合ってはならない

は簡単。

  • 白マスは連結でなければならない

ひぇーっ!?こんなのできるんでしょうか?

かなりのパズルが連結性判定を必要とするので、これができないとなかなか厳しいです。

連結性判定は、いろいろな方法がありそうですが、僕が今回採用したのはBFSっぽい方法です。

イメージとしては、

  • 適当に根を決めてBFSをするときの、各ステップでのvisitedの配列を変数にする。

という感じ。式を書く方針はこんな感じ。

  • Y_i,j : i行目、j列目を黒く塗るならtrue
  • X_i,j,k : i行目、j列目、BFSのkステップ目
  • X_i,j,0 たちのうち、1つだけがtrue
  • BFSの総ステップ数を T とすると、白マスの X_i,j,T は全部true
  • 黒マスの X_i,j,k は全部false
  • X_i,j,k+1 がtrueなら、X_ai,aj,kのうちいずれかはtrue((ai,aj)は(i,j)に隣接するマス)

※「A ならば B」は 「!A or B」と変換できます

変数も節もO(マスの個数^2)個でいい感じです。

ちなみに、17x17のを1つやらせてみたら20秒で答えが出ました。感動!

自作問題リスト

自作問題をgoogle spreadsheetにまとめました。

snuke問題 難易度表

evimaさんが作っておられたのを見て、確かスプレッドシートに自作問題をまとめておくのはいいなぁと思い、作りました。

evima's problems

りんごさんのもあります。

今年の目標を振り返る

人生ゲーム 2014 - あなたは嘘つきですかと聞かれたら「YES」と答えるブログ
採点します。
algorithmのレート:6/6
思ったより上がった。
marathonの参加回数:1/6
機械学習系にも出ないと回数が増えないなー。
marathonのレート:3/6
3回しか出てないにしては頑張ってる。
CodeForcesのレート:5/5
高すぎるかと思ったら達成できた。
ICPC成績:0/2
来年こそは!
ICPC練習:1/2
オンサイト進出回数:5/5
日本のオンサイト数えていいんだっけ。まあいいや。
個人の最高順位:5/5
UTPC3位で既に達成していたんですが、優勝までできるとは。
writer定期:3/5
writerその他:1/3
意識:0/5
作品:5/10
あんまり作らなかったなー。
スキル:5/10
採点しにくい。
大学:0/10
大学生の鑑(あんまり覚えてない)
雨でもないのに外出しなかった日数:0/4
外出しなかった日には雨が降るべき。
添い寝:0/0
max(0,score)
その他:6/16
適当。

コンテスト系:30/45
その他プログラミング:10/25
大学:0/10
その他:6/20

合計:46/100
評価:D

欠点、留年不可避。
もう一回2014年やります。

CodeFestival 2014 上海ツアー 参加記 〜コンテスト編〜

結果としては、
1位:snuke (GJ以外の8完)
2位:omeometo (HIJ以外の7完)
3位:アジアの人 (GHJ以外の7完)
という感じで、優勝できました。やったー。
7完のままでも時間の差で勝っていたけど、8問目を残り30秒くらいで通して順位表を面白く出来て良かった。
AOJ-ICPCを埋めまくっていたおかげか実装力が上がっていたらしく、前半6問を2時間弱で終わらせて後半の問題をやる時間ができたのが良かったっぽい。
AOJ-ICPCは神。あと、準急を止めた税金さんも神。



・開始前の準備としては、順位表のページをchrome拡張を使って定期reloadするようにしておいた。
・とりあえずA問題から見る。
・なんかgrayコードっぽい。
・適当に実装する。
・WAたくさん
・自明なミスがたくさんあった。つらい。
・とりあえず順位表を見る
・tozan、omeさん、ロジマシさんしかまだ通してなかった。
・最初の数問でtozangezanとかに勝てないのはわかっていた。
・Bを読む。
・慎重を要する感じで怖かったので慎重にやる。
・こういう感じの慎重系はAOJ-ICPCに割と出てきたのでちょっと慣れた。
・部分ごとにテストして1発AC。バグらなくて良かった。
・Cを読む。
・Regular Polygonは多分正多角形だと思いつつもweblioで一応確認した。
・正方形しかないよね、コーナーケースを考えながら適当に実装してAC
・この時点でomeさんの次の2位(AB早かったtozanはCを飛ばしていたっぽい)
・Dを読む。
・解法はすぐ見えたけど、明らかに実装重いし、バグ出したら一気にペース乱れる問題に見えたので飛ばす。
・「Yakiniku」という文字列につられてFを読む。
・問題設定は簡単そう。
・とりあえず数式を立ててみる。
・あー、ax+bをたくさんの区間に対して求める感じかー
・たこ焼きオイシクナール型segtreeを書く。
・ちょっとデバッグしてしまったけど1発AC
・この時点では多分1位だった。
・とりあえずDに戻ってもりもり実装
・流量を1箇所間違えたり、あきれるようなミスとかあった気がするけど、泥沼デバッグとかはせずに一発AC
・調子がいいとはあんまり言えないけど、ハマったりはしてないからまあまあいいんでは。
・この時点でomeさんに20秒差を付けられて2位
・まぁでもこの段階での微妙な順位はどうでも良いので気にせず次。
・omeさんが解いてるEやるか。
・ゲームの戦略系のDPだ。
・こういうのはメモ化で実装すると楽なやつだ。
・状態の持ち方工夫しないとループ起きそうだなぁ。
・「何ステージ目か」も持てば1ステージ目以外はループしなさそう。
・WA!?
・精度が足りてないのかなぁと思ったがそんなことはさすがになさそう
・問題文を眺め直す「if the difficulty of that stage was 2 or 3,」あっ
・AC
・この時点で1位に返り咲く。
・omeさんはDを飛ばしているっぽくて、引退勢には体力的に厳しそうなのかなと思った。
・なんかここまで、「書き終えてサンプルすんなり通って出したらあっさりAC」みたいなACがCくらいしかなかったけど、どハマりはなかった。
・優勝ラインは700~800っぽい
・少なくともあと1問は解かないと。
・順位表を眺めている時になんかIを解いてる人が結構いたことを知っていたのでIを読む。
・なんかLapin Noirっぽいけど、終末状態は複数あるからちょっと違うか(これは「Mr.X disappearsした後はもうMr.Xは二度と現れない」という誤読によるものだった・・・)
・誤読したまま解く。
・WA!?
・あっ、もしかしてこれ「Mr.X disappearsはそのターンだけ」なのでは
・AC。修正箇所がほんの少しで良かった。
・700点の時点で1位だったので、1・2位くらいは取れそうかなーと思っていた。
・あと1完はしとくに越したことはなさそう
・omeさんがGを通していたので読む
・なんかよくわからないけどよくわからなさそうだった。
・うーん、トイレに行ったりしてる間にも何もわからなかった。
・準急が通してない時点でJは捨てた方が良さそう。
・Hを読む。
・結構ときやすそうな問題だった。
・条件を整理していくと流したくなった。
・結構辺の数が多い気がしたのでグラフを小さくする方法を考えていたけど小さくなりそうにない。
・残り時間も少なくなってきていたので、試しに書いてみることにした。
・書き上げた時点で残り1分にだったのでsubmitしてみたけどサンプルすらあっていなかった。
・絶望しながらコードを見たら明らかに変なところを見つけて書き換えてまたsubmitしたらACした。
・8完、普通に嬉しい
・辺の数については、フローの計算量について疎かっただけっぽくて、減らさなくても普通に間に合った。
・凍結こわい・・・
・omeさんがIを出していて、これがACなら時間差で負けていた。
・こういうコンテストでの優勝は初めてだったのでめっちゃ嬉しい。



各問題の感想

A「Lock」:サンプル入出力を5個書いてみて欲しかったw
B「n-th Points」:面倒なだけだけど、結構ユニークな問題で僕は少しだけ好き。
C「Regular Polygon」:数学系の用語を英語で何て言うかって結構知らないよね。
D「Maze」:復元つらい(◞‸◟)けど、AOJ-ICPCでの圧倒的成長によりあっさり倒せた✌︎
E「Game」:「if the difficulty of that stage was 2 or 3,」はなんか現実に合わせすぎて面倒くさくなるだけだったんじゃないかなぁ。サンプルで落とされないのはつらい。それがなければ結構面白い。
F「Yakiniku」:これは良問。さすが焼肉。
G「Ammunition Dumps」:問題文が分かりにくかったのは残念だけど、問題としては面白かった。意外と気付きにくいもんだなぁ。
H「Dungeon」:なんというか目新しさはない印象だけど、問題としてはなかなか面白く出来ていて好き。
I「Obstruction」:Lapin Noirを知っていると、Lapin Noirに対して「こういう解き方もアリだよね」って言っている風にも感じた。解法は結構違う。Lapin Noir的な解法でも解けそうだけど結構面倒そう。(そもそも誤読してたしね)
J「XORAND」:読んでません。(XOR RANDだと思ってたくらい)ホテルでantaさんにwavelet系のデータ構造に教えていただいた。分かりやすかった。wavelet面白い。


コンテストの運営様お疲れ様でした。
特に英語の問題文とか大変だったのではないでしょうか。
問題面白かったです^^(特に後半)
サンプルはちょっと弱かった気がするけど、リジャッジとか起こってなかったのはプロ。