こんばんは、ゴドーです。
昨日のAtCoder Beginner Contest 281はA~Eの5完でした。
相変わらずF問題に手がかかりそうで解けなかったのが悔しいところ。
レートは微妙に上がってハイスコアを更新しましたが、青帯に入るにはもう一声、やはりFまで解き切る実力が要りそうです。
D問題は解説通りの動的計画法。
たぶんどこかで解いたことがあるタイプの問題でした。
E問題について、最初はM個のうちのK個を管理する方法として、K個目とK+1個目を記録する方法を考えてみましたが、実験してみるとすぐに時間オーバーすることが分かり。
そもそも出し入れする数を含む含まないの判定さえ取れればいいので、順序集合で実装すればいいと気づき、かつK個とそれ以外とをそれぞれ別の集合にすればいいと気付いてからはそれほど難しくありませんでした。
部分和の問題だと捉えると難しいですが、要は２つの集合の出し入れだと考えると難しくない。
こういう本質的な読み替えが重要ですね。
そういう意味だと、F問題もかなりの部分まで読み替えできていたのですが、あと一歩で洞察が及びませんでした。
なんとなく楽できそうな道が見えて実装したものの、正解が得られず、何が間違っているのか考えているうちにタイムアップでした。
安易な発想にハマって時間切れになるのはよくある負けパターンの一つなので、そもそも別に道はないか戻って考える戦略を選べればよかったのかも。
回答にある２つの集合に分けていく解法は、発想自体は序盤にできていたので、あとは実装をちゃんと考えていけば解けていたかもしれません。
来週のAtCoderもハイスコア更新を目指して頑張りたいと思います。
それでは、また。
/ゴドー
