こんばんは、ゴドーです。
昨日のAtCoder Beginner Contest 267はA~Eの５完でした。
F問題も解説を読むと方針自体は合っていたのですが、どうしても最後まで正答を出すことができず、ちょっと悔しかったですね。
A問題は非常にシンプル。
B問題は、B問題レベルでグラフが出てくるのが驚きでしたが、隣接リストをつくれるようにしようという解説の意図を読んで納得でした*1。
C問題はC++erなのでprev_permitation() を使ってごまかしましたが、真面目に処理を実装しようとすると結構手こずったかも。
D問題は最初の数を２や３で割った値を使ってそれに揃えられるかという方針で実装しましたが、効率の面ではあまりよくありませんでしたね。
解説にあるように最大公約数を考えてから進める方が明らかにスマートですし、もう少し問題に対する考察を重ねてから実装に入った方がよかったですね。
E問題は要は閉路判定すればいいんでしょ？という風に解きましたが、始点を含む閉路判定をDFSで実装するのにちょっとだけ手間取りました。
解説にあるように始点の横の２点を結ぶ経路があるかどうかを探す方が明らかにスマートで、D問題の反省とも共通しますが、ひとつ解法を思いついても、もう少し楽にできる方法がないか少しだけ考えてみるようにすべきかもしれません。
F問題はこれまでの計算結果を使って次の結果を求められるということには気付いており、解説にある通りの漸化式は早々に立てていたのですが、実装に手間取りましたね。
次元圧縮（これは不要だったみたいですが）した後、これまでの総和をセグメント木で管理しようとしていましたが、よくよく考えたらフェニック木だけで十分でした。
AtCoderのライブラリを利用してフェニック木を使っており、いくつかの問題はそれで正答を出せていますが、自分でイチから実装したことがないので理解が足りず、応用ができていないように感じました。
一度、自分でクラスを書いてみるべきでしょうね。
それでは、また。
/ゴドー
*1:ただ、よくあるグラフ問題は隣接リスト以降の処理がとにかく難しいので、リストをつくれるだけでは結局歯が立たないのですが。
