PCKバチャは今年初めてなので、計測のためにThistleとは別々に走りました。
結果
ooooo oooox 9完85点 ペナルティ5 予選4位相当
A問題
PCKのAってABC-Aより簡単ですよね p+m+cです
B問題
序盤の早解き競争で問題文が読みにくいとイライラするのでやめてくれません？ まあこれもやるだけです ヤマメ20匹を10匹と間違えて1WA (敗退)
C問題
戻れないので楽勝 ペナ出すとヤバいので一応見返しはしました
D問題
vjudgeを使っていたので画像が出力されず、自分で図を書かなければならなかった...
bitで管理するのがやりやすいと思います
E問題
! やさしい！(1e5でも解けるが...)
制約に甘えましょう
F問題
この辺から実装がだるくなってくる頃です 四つ折りにして差分更新がいいですかね？
G問題
どこで違反が起こるかを二分探索します。違反が起きるかの判定は以下の様に行えます。
- UnionFindで生徒の頂点や部活の頂点を併合する。
- K操作終了後に、2つの部活が同じ親を持っていたらNG(辺の貼られ方より、同値性が担保される)
二分探索の境界間違えて1WA(おい...)
H問題
初見でTrie必要に思えてすっ飛ばしたのですが、よく考えるとロリハだけで十分でした。AGCでロリハ使う問題が出たばかりなので解けたのだと思います。
?の個数は高々1なので、?があった場合はそこに入る文字を全探索することで?のない場合に帰着できる。
まず*が無い場合は普通に一致判定をすればよい。これはunordered_mapが便利
また、word群の前から/後ろから文字取ったもののロリハを計算しておき、それらをunordered_mapに突っ込む。最後尾に
*が付いている場合は前から取ったハッシュ値と、先頭についている場合は後ろからのハッシュ値を計算することでマッチする個数が得られる。
メモリがかなりギリギリなので注意
I問題
二分探索をする。その中での部分で全ての円に含まれるような点が存在するか判定するが、これは適当にやっても問題ない。
J問題
見た目がフローだったので捨てて夕食に行ってしまった。
まとめ
85分でここまで解けたのは良かったと思います。同校制限に負けたくない...!
