こんばんは、ゴドーです。
昨日のAtCoder Beginner Contest 297はA～Eの5完でした。
レーティングも自己ベストまで戻ってきており、もしかしたら来週でベスト更新できるかもです。
A問題は文字数を数えるだけ。
B問題は文字列長が小さいので、すべてのマッチングパターンを試せばよし。
C問題は縦列のパターンを比較すればOK。
いずれもそこまで難しくはありませんでした。
D問題について、解説では三分探索が使われていますが、これは思いつかなかったですね。
物理の問題チックに極値を求めて近傍を探索する方法で行いました。
実装時に数式を間違えてだいぶタイムロスしてしまいましたが、難易度的には易しかったかなと。
E問題は問題文が複雑でしたが、例題を見ながら実験することで内容把握。
全操作からひとつだけ操作を抜いたパターンをすべて求めろということで、各パターンは小さな計算量で求めなければならないということが明らか。
また、問題の性質から全操作からの差分でなにか簡単に各パターンの答えを求められそうというのは直観できました。
あとは実験内容をよく見れば、各操作での入れ替えを最後に戻すことですぐに答えが出ることに気づけました。
F問題は回答には至らなかったのですが、Union Find Tree を使うというのはイメージできていました。
代表だけを考えていけばいいというのも発想できていましたが、各クエリに対応できる使い方まで至りませんでしたね。
ややこしさはありますが、D問題でタイムロスした分がなければ難易度的には回答できていた気がします。
この問題については、あとでちゃんと解き切って置きたいと思います。
それでは、また。
/ゴドー
