第4回PASTお疲れさまでした

記憶が新しいうちに投稿です。

リアルタイム受験ではありませんでしたが、お金を払って土曜の朝から受けました。

午後はHTTFがあったので、気合の7時起きをして臨みました。

うおお、上級！！！ pic.twitter.com/iqXInEVsX9

— かいけー (@KaikeyPro) November 7, 2020

ようやく上級になれました！

半年前に短期間で2回受けてどっちも76点だったのですが、今回は12点上がって上級になれてよかったです。

さてさて、各問題に対する感想解説をやっていきます。

A - 中央値

ソートして2番目を出力で終了～～～でサンプルを試さずに提出したらWAが出ててビックリ。問題を読むと何が中央値だったかを出力するらしい。一問目からずっこけるのは少し不吉。

B - 電卓

Bが0ならエラー、そうでないなら100倍してから少数の方を0埋めして出力。

C - 隣接カウント

愚直に4方向見るだけでOK. こういう実装問題があると競プロ初心者にとってかなり教育的なセットになりそうだなぁと思った。

D - 分身

左分身の必要条件が左端の'.'の数、また右分身の必要条件が右端の'.'の数、両方の和の必要条件が'.'の最大連続数以上であることになる。

E - アナグラム

場合分けっぽいなーと思って|S|<=2, もしくは全て同じ文字列ならfalse みたいなのを書いたらなかなか通らなくて焦る。

よく見ると制約がN<=5なので愚直に5!でいいことに気づく。コンテストじゃなくてよかった。

F - 構文解析

ここらへんで若干実装に工夫が必要になってくる。

とりあえず各文字列に対して出現回数をカウント、そして出現回数でソートする。

そして前からK番目に該当するやつを見て、それの前後に同じ出現回数のやつがあるかを確認、あったらダメ。

G - 村整備

これも愚直っぽい。

2重for文で壁を崩す→bfs→壁がないところを全部訪問してるかどうか→壁を戻すという感じでやった。

H - マス目のカット

これも愚直。

nが小さいので条件を満たすnを線形探索して、長さnの正方形を切り出したときにある数がn * n - K 以上あるならOK.

そう考えるとにぶたんするような制約でもいけそう。

I - ピザ

ここらへんで少し難しくなってくる。

尺取りしようと思ったが、バグったらめんどくさいしlower_boundでやることにした。

合計値 - 累積和を計算して半分くらいに分割する場所をlower_bond, その近辺のindexが答えになりうるのでそれを探していった。

J - ワープ

難しい。方針がすぐには立たなかった。

ワープ可能であるなら辺を貼る、ということを考えたがどうしても辺が多くなりすぎる。

そこで、ワープの性質について考えてみると、2回同じワープをするのは無駄ということに気が付いた。

もっと言うと、A→B→CをA→C, A→C→AをA→Aとみなすことで高々1回のワープをするのが最適ということもわかった。

このことから、まず各ワープの疲労度をワーシャルフロイドで最適化しておいて、

始点と終点からそれぞれ最も近いA, B, Cまでの距離を計算してそれぞれに対して最も小さいものを取ればいいことがわかった。かなり面白い問題。

なぜか僕のダイクストラが遅く、地獄のような高速化を求められてしまったが、、、

地獄の高速化

ダイクストラをちゃんとライブラリ化しようと思った。

K - 転倒数

転倒数に関する典型問題を解いていたらかなり見通しが立ちやすかった。

数列内の数字は20以下なので各数列内の各数字の出現数を記録、あと各数列の転倒数も記録。

そしてBITを使って出現数から転倒数と、その数列自体の転倒数を計算する。

サンプル2が一発で合ったからそのまま提出。時間的には10分くらいで解けた気がする。

L - マンションの改築

これは少し難しかった。

いまいち方針が立たなかったので、とりあえず色々シミュレーションしてみると、

とりあえず各マンション間の差分を管理するとよさそうなことに気づいた。

さらに偶数番目の加算は差分の偶数番目を+, 奇数番目を-, 奇数番目の加算はその逆……みたいなこともわかり、これをmapで管理するとよさそうなことに気づいた。

というわけで各差分の出現回数を記録したmapと、偶奇の操作の和を記録してそれでうまいことやるとできた。

大体17分くらいで解けた。上の考察がかなり流れるようにできた上に全くバグらなかったのでうれしかった。

M - 筆塗り

わからず。

後ろから操作するとよさそうだとは思ったが、それ以上がわからなかった。しっかり復習案件。

N - マス目の穴埋め

難しい。1つ上と2つ上の情報が現在に作用されるのでその2つの情報をbitで持ちながらdp。

これ。実はICPC-Eで似た問題が出ていて、解法に感動していたためすぐにわかってしまった。(実装は初めてやったからそれなりに時間かかったけど。)

O - 宝箱

難しい。なんだこれ。

累積和を引いたセグ木でdpしようとしたけど答えが一生合わず。無念。

というわけで、結果はこんな感じでした。

解けた問題数が増えたのは当然嬉しかったけど、それよりもめちゃくちゃ早解きができるようになったと感じています。

次はエキスパートを狙います。