KUPC 2018

たまには記事を書きます,優勝したし(イキリ)

最初

何はともあれ木や数列にクエリを投げている100,000を探します。2題もありました。

M

実家のような安心感

クエリ3は見たことない気がします,有名?

最初に実装を間違えてWA+MLEを貰いました。 理由はわからないんですが,なぜかbetaだとコンテスト中でもどのぐらいTL / MLを使ったか見えた(これバグじゃない?)ので,あとちょっとメモリを減らせば通ることを確信しました(不正か?)。

なのでバグを直して,TrieのNodeのサイズを2/3にしたら通りました。

f:id:yosupo:20181001150522p:plain (これはコンテスト後のスクショですが,コンテスト中もこういうふうに見えていた)

I

ちょっと考えたらlogたくさん解(SegtreeのNodeに2次元BITを乗せる)がわかったんですが,どう考えても間に合わないのでもう少し考えると,区間をsetで管理すればオーダーが落ちることがわかったので書きました(setが嫌いなのでsegtreeでごまかそうとしがち)。

解かれてるニム?に取り掛かりました。今考えると戦略を間違えていたと思います。

J

ただし、互いに 2 回目以降の手番では、 直前の自分の手番で宣言した整数よりも大きい x を宣言してはいけない。 と誤読して時間を溶かしました。これで実験すると規則性がありそうでなさそうでありそうなテーブルが作れます。

相手より大きい数を一度宣言してしまったらもう殆ど負けみたいなものじゃないか?と気づくと解けます。

順位表で前半からやってる人のスピードと後半の重さから考えて,後半を4題解く人は出ないだろうと予想しました。 400 500 500解く人が出たらどうしようもないのでその場合は諦めることにして,前半を始めることにしました。

A

うんうん

B

DP書いちゃった

C

全探索系で出そうだな〜と思いながら紙で考えて解いた

D

だいたい半分にできそうなことはわかったが,クエリをきっちり30回で抑えられる証明ができなかった。書いて実験したら30回ぴったりっぽかったので投げた

E

普通のDP,バグりそうだなーと思いながら書いたらバグらなかった,すごいので

F

グラフを2色に塗り分け + 辺に重み付き,というのは見たことがあった,確かIPSC

G

結構悩んだ結果,logを入れれば良くない?と気づいた。でも$2 \times 4 \times 8 \geq 16$だから$a_{16}$の値が負になるなあと悩んでいた(どういうハマりかた?)

順位表を眺めるとあと1個解かないと負けそう & 500を解かれると300取っても同点 ということでHとKのどっちに行くか悩む。

順位表を眺めるにHなら時間内に通せそうだったので,Hに行くことにする。今思うとKのほうが良かった気がする

H

ほうじょっぽい見た目をしていたのでほうじょをする。

大体実家DPっぽい?同色がなければ実家DPだね。

同色で完全に覆う区間があるとDPが破滅することでかなり悩んだ結果,よく考えるとそもそも抹消できたため解けた。と思ったら実装がなんかバグりまくってしまい…

運良くギリギリで通せたので良かったです。