RUPC2016

RUPC2015だと思ってました.

day1
家で出る.Eまでやった後Fが多方向木DPっぽいなあと思った後,Gに手を付けてしまいコンテストが終了した.
A:やる
B:前から1に→後ろから0に
C:やる(はじめ制約読んでなくて不可能ってなってた)
D:ひとつのscannerは50*ceil(50/3)=850秒くらいしか使わないので,bool dp[51][851][851]をやれば間に合う
E:ニコニコ数みたいに全探索するだけ.88=2*2*22みたいなのが無駄なのはすぐわかるけど他にも最長でない経路がある(14441=11^4 と思ったけど11じゃなくて22だからこれは例になってないし嘘かもしれない)
じゃあ大丈夫かも(適当)
Nから割っていったほうが圧倒的に状態数が少ない.
F:実は木DP一発でできるっぽい(直径求めるDPに加え,キーとして既に一本選んだか? みたいなやつ)
G:問題不備があったが,正しいバージョンだとにぶたん+グラフ遷移でできると思う.

day2:
(すぬけの)家で出る.sugimさんとチームを組んだ(ssuiggimma).13問あってびっくりした.
A:指の運動練習
B:やってない.面倒
C:unionfind,間違えてsample試さずに出しちゃってWA.
D:やってない.真ん中で切ってそれぞれlineか判定するだけ
E:やってない ちょっと動かす→回すを探索すればよさそう.
F:殴らないだけ.逆から見てどいつに注目すればいいか求めた後やるだけ.
G:使う順番とかは無視して,dp[i][A][B]=i人目まで見て,所持うまかA本,所持ふがしB本の時の最大ブタメソ所持数 とする.最終的にBがまともな値であれば途中で負になっても大丈夫(a,bの交換を全て先にやったとして良いので)なので,これでDPできる.
H:8C2本に対し,どのペアがつなげるかわかるので面倒な連結成分DPをした けど高々7本しか使わないので全探索(28C7)で間に合う.確かに.
I:接線試して2^16どれができるか確かめた後全部を埋めるのにいくら必要かDPでO(3^N)
J:オートマトンの最小化.aとbが違うという情報を伝播させていく.ちゃんと必要なとこだけ見れば全体でO(N^2).
K:差として表れる値の分布はFFTで求まる.それの差も同様にFFT.
L:suffixたちを始まる位置順でならべると[l,r)が指定できて,SA順で並べると文字列が存在するかどうかはこれも連続した区間になる(愚直ににぶたんで調べられる)ので,結局
2次元平面上にN点ある.クエリとして長方形が来る.長方形内の点の個数を求めよ. になる.2次元データ構造があれば出来そうだけどよくわからなかったので,クエリを先読みして左から順に点を追加していった時に下に何個あるか求めといて答えた.
M:各クエリに対して,重ならない長方形の数を数えられればよい.上,右,下,左にあるやつは簡単に数えられて,右上にあるやつとかが二重に数えられてしまうのでそれを引けば良い.それには,Lと同様に長方形内の点の個数が求められればいいんだけどこっちはクエリ先読みが出来ないのでしかたなくkyuridenamida法をsugimさんが実装していた.

コンテスト後にyosupo,snukeに聞くと2次元BITで出来たっぽい なるほど

day3:
day2のあとCF,SRMとあったので余裕で開始時睡眠していた.yosupoとチームを組む.チーム名悩んだけどsugim,snukeペアがin_the_houseにしていたのでinthishouseにする.眠いので意思疎通が取れずログインに時間がかかった.

yosupoが後ろのほう読んでる間に簡単なのを埋めた.
A:明らかにこのセットの中でHを除いて一番難しい 起床直後にやる問題ではない.
B:寝てたら誤読した
C:やるだけ 写経ミスった
D:yosupoが解いてた 左から全部聞くだけ+右からBITにぶたんでいいけどyosupoがAAtreeで殴っていた(こっちの方がわかりやすいらしい)
E:フロー yosupoが解いてた
F:反転して引き算しとくと全0か判定するだけ starryskyでminとmaxを持つとできる yosupoが一瞬で書いてた
G:累乗したい→出来る→おしまい
H:二次元上に点がN個あって,横方向でこの範囲にある点に+1 っていうのと, 縦方向でsum っていうのができればいい.無理やんけってなってた.結局平方分割してsegtreeを持つとかでコンテスト後に通していた.stackoverflowにO(Nsqrt(N))解が書いてあった.NlogN系じゃできないのかなあ

運営の人お疲れ様でした。

そんなに重いセットはなかったけどday2と3の間にこどふぉとSRMがあったので疲れた・・・