ABC199 感想 - 文学徒が競プロをするブログ

456位の1887パフォで1年ぶりに過去最高パフォを更新！しかも今回はまぐれではなく、解くべき問題を詰まらずに解けた結果だったので、非常にうれしい成果でした！
これからこういった成功を増やしていきたいですわね。

ところで、bitDPを扱う問題のパフォが妙に高く出ている気がします。ナップサック以外の典型DPは得意でない人が多いのかもしれませんね。EDPCを埋め直すとABCでお得に立ち回れるかもしれませんから、要検討です。

A問題

問題文を見て過去のPanasonicコンのトラウマがよみがえりましたが、今回は普通に式をべた書きするだけで良くて、I got a kotonaki.

$x$ について全部試せばよい。

普通に実装難しかったと思うんですが、23分時点で3完緑パフォで死ぬほどびっくりしました。やっぱり私は実装が苦手みたいですね。もっと下埋めして、茶、緑パフォの問題を詰まらずに実装しきる力をつければ安定しそうです。

ところで、これってポインタをswapすれば2のクエリも $O(1)$ で処理できたりしませんかね -> できました

更にいうと、C++のstringは参照型なので、普通にswapしても $O(1)$ らしいです。diffが妙に低い要因の一つはこれかも？

Eの方ができそうな見た目をしていたので、後回しにしたまま解けませんでした。

連結成分ごとにやると、最初の頂点以外は高々2回程度しか探索しないため解ける。なるほど良い問題だなあという感じです。ただ同じ頂点を通らないようにDFSしながら探索するのはかなり面倒でした。解説にある通り、連結成分の頂点を過不足なく列挙してから探索していくと実装が楽だったと思います。

これが青diffなの、ありがたいです。この前のBFSとbitDPを合わせる問題もそうでしたが、妙に皆さん解けていない気がしますね。bitDPは遷移がワンパターンだし、制約で察することができるのでかなり楽に方針が立つタイプの典型だと思います。式変形なども必要ありませんし。

順列の状態をまとめるのは明らかにbitDPの使いどころで、巡回セールスマンしかり非常に有名な状態の持ち方だと思います。一度WAを出しはしましたが、かなりスムーズに解くことができました。

期待値ゲーはコンテスト中に解けると思っていません。別記事でまとめます。

とにもかくにも、いい結果が出せて良かった......。何とか青に辿り着けるよう、努力を続けます