いろいろな記録

大学院生やってます

2020/05/15

研究

  • 1h

競プロ

E - Common Subsequence

解説AC : 60分

dpの定義の仕方が間違っていた。累積和を取って行って高速化する発想は面白い。dpを定義したら、ちゃんと式と場合分けを書いて考えること。

D - Patisserie ABC

自力AC : 30分

考察に時間がかかったが、よく考えたらパターン分けすれば終わり。昔の水diffっぽい。

E - Sequence Decomposing

解説AC : 60分

dpでLISに持ち込むところまではわかったが、LISをN\log Nに高速化する方法を知らなかった。勉強になった。

D - Good Grid

自力 AC : 30分

解説とは別の方法(各パターンに関して、変更コストが少なくなる色を小さい順から3つあげて、3パターンに対して27通り試す)で解いた。

色の種類に着目すると早い。着目する対象を変えて、探索のコストを下げるという常套パターン。

 

---

明日も頑張りましょう。