ABC210の感想
A,B,Cの3問解いて600点という結果でした。
D問題には40分くらい残すことができましたが、解法が思い付きませんでした。
過去問でのC問題の打率は4割程度といった感じだったので自分としては上振れだと思っています。
N個並んでいるキャンディから連続したK個を持ってくる。キャンディにはそれぞれ色（番号）が振られていて出来るだけ多くの色のキャンディを持ってくるという問題。
「連続したK個を取り出し、重複要素を削除して種類数を求める」ことを繰り返すアルゴリズムを組んだ結果時間内に計算が終わらなかった。連続したK個のキャンディの種類を繰り返し求める際には、先頭要素と最後の要素のみを調べれば良いことに気づき解くことができた。
- 最小化するためにどの動作を繰り返せば良いのか分からなかった。
- 10^6の要素から異なる2つを選ぶことを全てのパターンに対して行った結果計算量が爆発して人生終了した。
自分としては満足した成果をあげることができたと思っています。
しかし、計算量を見積もる能力の低さや動的計画法はなんとなく知ってるけど実際に問題を解くときにはどうすればいいか分からなくなってしまうという自身の弱みが露呈してしまいました。次回に向けて動的計画法の問題を解きつつ、計算量の見積もりはいつか出来るようになると神に祈ることにします。
