まず黒の連結成分の個数で場合分けする。これを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が出来るようになる。やったね。
実はこの区間DPにはこういう名前がついている
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)では解析できないということである
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を入力する。
なんかこれらが複数同時に起こると衝突する。
これらを再帰関数でやるのは大変なので、スタックを直接操作する。表とかを作るのだが、集合を列挙することからもわかるように人間のやるものではない
まず転置をします。
すると、数列が与えられます。隣あう要素の差が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)本になる。
赤色を1, 白色を0とする。すると4種類のコマは
0 0 1 1 0 1 1 0 0 1 0 1 1 1 0 0
となる。要するに、左右と上下は独立。
ここで、線がつながってることに注目。すると、とある列/行だけ取り出した時の値は
0 1 1 0 0 1 1 0 0 1 ... みたいになってる。つまり最初が0か1かでその列は一意に決まる。
よって、本質的には長さHの数列 a_i とWの数列 b_i だけを考えれば良い。値は0か1だけである。
よって、サイクルがあるとNGという条件を無視すると、答えは 2H+W.
ここで、"サイクルがある"と"長さ4のサイクルがある"は同値であることに注目。証明は略。
そして、"長さ4のサイクルがある" と "a_i = a_i+1, b_j = b_j+1, ((a_i) + j) % 2 == ((b_j) + i) % 2, なるi, jが存在"は同値であることが示せる。
あとはちょっと実装が重いDP。
大反省。
チームとしての性能がヤバかった。今回で言えば、うまく動けば7問は解けていた(そもそもG以外は正しい解法が出ていた)のに、-2問、もちろん完璧に動くのは無理だけど、それでも許せるのはせいぜい-1問だと思う。
僕個人の話だけど、なぜかDEを連続で実装して、バグらせた。(そもそもCを任せたのもpirozさんに連続実装させていて意味不明すぎる。何をやりたかったんだろう。意味不明。pirozさんごめん。)
自画自賛みたいになるけど、チームとして出来てくれば相当強いチームになるとは思う、3ヶ月あるのでボチボチ頑張りたい。
なんかチーム練習でもそうだったんだけど、実装力<<解法力っぽくて、常に実装待ちキューに数問溜まっている。ただ実装するべき問題をうまく選べていない感はある。これを直せば実力急上昇↑↑
今回激ビエしたので、激ビエポイントを使い果たした→つまりアジアは？？？
