2020/06/08
久方ぶりにラボに行ったら研究が捗った.
研究
- 文献 3h
- 実装,データ整理 5h
競プロ
- AtCoder : 4AC
E - Balanced Path
解説AC : 60分
ベルマンフォードとか考えてたけど,普通に違った.最短距離の場合の数が多すぎるので不可能ですね.
こういう,出てくる値やコストなどがそこまで大きくない場合,それを添字に持ったDPをやるっていう発想はもっとスムーズに出てくるようにしたい.
D - Menagerie
自力AC : 25分
最初をSS, SW, WS, WWと決め打って,順番に見て行く.最後に矛盾がないか確認する.boolをもっと上手く使えばオシャレに解けそう.
D - Simple Knapsack
自力AC : 30分
普通のナップサックにするため,全ての重さからまずを引いてしまう.その後,取った個数もカウントしたDPをして,最後にその個数だけの重みを足して可能かを判定する.こういうのがさばけるようになってきたのは良い.
---
明日も頑張りましょう.