ICPC模擬国内&国内予選参加記

はじめに

stoq(@stoq_)くんとhanyu(@hanyu_kyopro)くんとチームharaharaを組んでICPCの模擬国内と国内予選に参加してきたので、参加記を描こうと思います。

模擬国内

前日早起きだったし余裕だろって寝て起きたら13:41でびびる。

なんかstoqくんもご飯食べ損ねてた。

ごはんぬき模擬国内開始。
A:やった
B:はにゅくんがやってくれた
C:stoqくんがやってくれた（すごい）

D:構文解析だからやります！をして嘘解法2ペナだしたりする戦犯をする。（(())())))みたいなのを落とす。）
左側に対応できるカッコの範囲を持った状態で左からみてく。
左が足りなくなったらたす。
最後まで見ても右側がたりなかったらたす。
これでO(N)でできるんだけど、左右独立で書いたり、にぶたんしたりするともっとあっさりかけたなってなってました。

E:はにゅくんがやってくれた（すごい）

Dをペナらせてる間にCE通っててすげーってなってた。
模擬国内は5完27位で通過ライン！

国内予選

ゼミで早起きしたあと昼寝を試みるも寝られず、寝不足のまま国内予選へ。
チームメイト二人もなんか眠そうにしてた。

開始した瞬間、ページがうまく表示されなくて焦る。
慌ててコーチに連絡してたけど、連絡つかず>

ので、定期的にリロードしてがんばった。

A:つながらない時間があったのでめっちゃharaharaしながら解いた。
順位表的に他チームも見れてなかった時間がありそうで安心する。
B:はにゅくんがやってくれた
C:stoqくんがやってくれた

D:構文解析だからやります！をして、ぺなださずになんとか通す。
n=16で、n!だと間に合わないので、bitDPにあたりをつける。
→状態を0,1でおきたい
→式が値xになるかを判定したい時、xより順序が早いか遅いか(1,0)の情報があればいい
→(x,xより早い文字の集合)ごとに計算して、O(n*2^n*(|S|+|T|))でとける

これ構文解析じゃないパートが結構面白かった。
D通した時点でharahara10位に躍り出る（やばい）