読者です 読者をやめる 読者になる 読者になる

Codeforces GYM 2014-2015 ACM-ICPC, Asia Mudanjiang Regional Contest J

数日掛けても全く解けなかった、提出コードも嘘っぽいものしかなくて、想定解っぽいものを得るために片っ端から読む必要があった

解法は知るとそんなに難しくないのだが、なんか異常に難しい。

問題概要

Dashboard - 2014-2015 ACM-ICPC, Asia Mudanjiang Regional Contest - Codeforces

長さNの文字列Sが与えられる。ただし文字の種類はN種類あることもある(各文字はcharではなくintで表される)

全ての部分文字列について、ABBA型となるか判定する。ただし、A or Bは空文字列でもよい。

N <= 5000

解法

ABB | A ←この縦棒を固定する。

| ABB | A ←そのつぎに左端を動かして調べていく

この固定方法のキモは、Aとしてありえる文字列長が区間となること。

追記

嘘です。まともな解法ないのでは?

ARC 059 F バイナリハック

math, tokoharu, n_vip(と僕)の集合知によりmagicを使用しないO(N)解が錬成されました。

はじめに

解説のとおりに"なんでもいいので最終的な長さがM"となる操作の仕方を考えています。

操作列の条件

0add, 1add, delの3種類がありますが、とりあえずaddを1種類で考えます。

長さNのadd, delの列が、最終的に長さMの数列を生成する条件はなんでしょうか?

これは、逆から見てmax(今までのadd - 今までのdel) = Mが条件です。

つまり、addを+1, delを-1として数列 a_1, a_2, ..., a_N を作ると、

max(a_i + a_{i+1} + ... + a_N)が最終的な長さになります。

経路へ

逆から見るとシンプルな条件になったので、経路で考えます。

addを上移動(y+=1), insを右移動(x+=1)とすると、最終的な数列の長さは経路上のmax(y-x)となります。

よって最終的な長さがM以下 ←以下です!!!!ぴったりMじゃないですよ!!!!!!!!!!❕❕❕❕❕❕❕❕ となる操作列は

  • (0, 0) からスタートして、y - x <= M を満たしながらN回移動

と対応します。

N回移動した後の目標地点は高々O(N)個しかないので、それぞれについて経路数を求めて足せばよいです。

これでM以下が出せたので、M以下-(M-1)以下を求めればよいです。

addを2種類へ

y+=1するときに2倍されるようになりますが、あんまり変わりません(投げ槍)

New Year Contest お絵かき

まず黒の連結成分の個数で場合分けする。これをKとする

連結成分ごとに、a1, a2, .., amを使うとすると長さ[max(a1,a2, .., am), a1+a2+..+am]の連結成分が作れることに注目する。

すると、塗れる範囲というのはK次元平面上の長方形たちの和集合で表せることがわかる。

座圧をして根性をすると、これを長方形に分解できるので、長方形ごとに考えれば良い。

これはN個を[0, INF), [a, b), [1, INF), [c, d), [1, INF), [e, f), [0, INF)に割り当ててくださいという問題になる(K=3の場合)

これは包除なので、包除をすると解ける

コンパイラ, 自分用まとめ

はじめに

文脈自由文法, LL(1), SLR(1) について書く

自分なりの理解を書きなぐってあります、間違ってたら教えて下さい。

文脈自由文法

A : B, C, d, e, F

みたいなのが並んだやつ, ただし大文字は非終端記号(自分で定義した記号)で、小文字は終端記号(文字列に含まれる記号)

また、空文字としてはεというものが一般的に使われる。これasciiに含まれてないから不便だと思うんですけど

重要なのは、左辺は非終端記号が1個ということ。右側はなんでもいい。

また、スタートを表す非終端記号を決めておく(大体S)。これ1個からスタート。

これをパースする方法を学ぼう!というわけ。

あとなんか計算量では記号の種類とかの構文のサイズ諸々は定数として扱われるっぽい。

また、解析した結果のものを構文木と呼ぶ。もちろん構文と入力によっては複数種類できることもある。

チョムスキーの標準系

これを解析する一番思考停止な方法は

dp[左][右][非終端記号] = [左, 右]を非終端記号にパースできるか

という区間DPである、計算量O(N3)で解析できるような気がする

が、よく考えたら

A : B
B : A

とかで遷移にループが出来る。もちろんこのケースならどうせ何も入力できないので問題はないが、DPにおいてループが発生すると大体不幸なことになるので多分爆発炎上ケースが作れる。

なので、もうちょっと構文を制限したい。それがチョムスキーの標準系。

これは

A : BC
A : a
S : ε

の3種類に制限したもの。

実はどんな構文もこれに変換できる。

A : BC
A : a
A : ε

に変換するのは簡単。で、ここから変換するのはなんかεになりうる物を列挙してうまいことやれば除去できる。

で、チョムスキーの標準形にすると、ループが消えて区間DPが出来るようになる。やったね。

CYK法

実はこの区間DPにはこういう名前がついている

LL(1)

ICPCで普通に行う構文解析を一般化したもの。

ICPCで普通に行う構文解析構文解析 Howto · GitHub がわかりやすい。

これは例えば

A : B c D

という規則があったら

void parse_A() {
    parse_B();
    consume('c');
    parse_D();
}

という関数を作って、parse_S()を呼び出せば全部パースできてハッピーという話である。

ここで問題になるのが、

A : B C | D E

みたいにあった時に、どちらの生成規則を使うか決定する方法である。

ICPCだと、だいたいad-hocになんとか出来てしまう。

ここで、例えば

A : B | C
B : "abc"
C : "def"

だとすれば、次の文字を見て"a"だったらB、"d"だったらCとすればよい。

つまり、各生成規則ごとに"次に到達しうるconsumeで消費する文字の集合"を見て、次の文字が入ってるものをパースすれば良い。

これがLL(1)で、計算量はO(N)

なお、この集合はdirectorと呼ばれて、これの計算のためにfirst/followという関数が定義される

また、複数候補が生まれうるならばそれはLL(1)では解析できないということである

SLR(1)

LL(1)はつよいが、

A : B | C
B : "abb"
C : "abc"

という規則ですら解析できない。なのでLL(1)をちょっと強化したSLR(1)という物を考える。

やることは単純で、LL(1)で複数候補があるならば、全部試せばよい、という方法(だと思った)。

もちろん計算量が増大しては意味が無いため、O(N)で解析できるぐらいに留める。

具体的には、"次に使いうるconsume関数の集合"をもってparseする。

文字が入力されたら、その文字に対応するconsume関数を列挙して取り出して、それらを進め、また集合を再計算する。これはshift動作と呼ばれる。

もしparseの最後に到達しているものがあり、かつそのparseのLeftのfollow集合が入力された文字ならその関数は解析成功とする。入力された文字は消費せず、そのparseのLeftを入力する。

なんかこれらが複数同時に起こると衝突する。

これらを再帰関数でやるのは大変なので、スタックを直接操作する。表とかを作るのだが、集合を列挙することからもわかるように人間のやるものではない

AGC 001 F Wide Swap

まず転置をします。

すると、数列が与えられます。隣あう要素の差がK以上ならswap出来ます。転置した時に辞書順最小になるようにしてください。となる。この数列をa_iとします。

ここで、abs(a_i - a_j) < kならこの2つの位置関係がひっくり返ることはない。逆に考えると、この関係を満たすペアすべての間に有向辺を貼ると、このグラフでのトポロジカル順を考えれば良いことがわかる。

実は、後ろから考える(Nから確定させていく)と非常に見通しが良くなり、priority_queueを使用すればO(N2 logN)で解ける。

辺の貼り方を考えると、a_iについて、"a_iより左側で、値が(a_i - k, a_i + k)の中にあるもの"全てについて辺を貼れば良い。

だが、実はO(N2)本も辺を貼る必要はない。a_iについて、"a_iより左側で、値が(a_i - k, a_i)であるもののうち最も右側"と"a_iより左側で、値が(a_i, a_i + k)であるもののうち最も右側"の高々2つにのみ辺を貼れば十分。これでO(N)本になる。