ICPC Bangkok 2016

ICPCBangkokアジア地区に参加してきました

出発まで

  • なんか中間を休むために理由書が必要だった
  • ライブラリの準備に手間取った(25枚以内で、チーム名と通し番号が必要)(pdfに通し番号振るのが難しすぎた)

帰国した翌日が情報実験第四(組み込み)の製作物発表日で、 何も準備ができていないのでバンコクでの製作が決定する

飛行機の暇つぶしとしてラノベ2冊と去年一昨年の過去問を持ち込む。

木曜日

空港で迎えと会うのに苦労した。飛行機に乗ってる最中に迎えの場所のメールを送られていたっぽい 迎えのお姉さんがハチャメチャ可愛くてびっくりした。

到着してコーチhadroriオススメの飯屋へ行く

さすがに疲れてたのですぐ寝た

金曜日

深夜に朝7時にバスで出発するよ!メールが来てた。ハチャメチャ(今確認したが、2時33分。) 早起きしていたので間に合った。

チュラロン大学を観光

プラクティスは左右が東大チームでハチャメチャ あと問題がコーナーケースまみれでハチャメチャ

疲れで完全に僕は死んだので、夜ご飯いかずに寝た

土曜日

深夜に(ry (1時22分) 更に、CCで全員のメールアドレスを配布するという典型ミスが行われた。ロック

コンテストはだいたいpirozさんの見てもらえばOKです。 訂正すると、僕の解法は8問ではなく6問

去年一昨年はかなりひどいセットだったのが、今年は何が起きたのか。 重考察まみれで、要するに良問セットで、ひたすら解法生成をすることになった。 問題の質としてはUTPCクラスだと思う。 去年までの作問陣が作った問題は多分プラクティスに回されたんだと思う。(失礼)(でもH問題はreadforcesで去年までの面影が残っていた)

一方環境の方はちゃんとロックしていて、 紙が配布されなかったり、途中でパソコンが止まったりした。 vscode/atom/sublimeが使えた。全く準備をしてなかったため使わなかったが(コンテストページに書いて欲しかった)

あと左右はやっぱり東大チームだった

紙は無駄にライブラリを3部印刷していたため、実質裏紙が50枚あり、困らなかった (でも僕は紙を大量消費するので、35ページぐらい使ったと思う)

めっちゃ僅差で2位を逃した。WFに行ける確率は0ではないがかなり低い、って感じらしい でもここまでCxiv-Dxivと接戦に持ち込めるのは想定外だった。

日曜日

観光をした。ボラれた。タイマッサージをした。

コーチhadrori、そろそろエオルゼアが足りなくてヤバイっぽい

月曜日

朝五時にホテルを出て空港へ。 組み込みの進捗が爆発炎上していて、飛行機で組み込みをしていた。

朝四時まで組み込みをした。

火曜日

組み込み発表会。まさかの優秀賞を取った。

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を入力する。

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

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