いろいろな記録

大学院生やってます

2020/06/08

久方ぶりにラボに行ったら研究が捗った.

 

研究

  • 文献 3h
  • 実装,データ整理 5h

 

競プロ

E - Balanced Path

解説AC : 60分

ベルマンフォードとか考えてたけど,普通に違った.最短距離の場合の数が多すぎるので不可能ですね.

こういう,出てくる値やコストなどがそこまで大きくない場合,それを添字に持ったDPをやるっていう発想はもっとスムーズに出てくるようにしたい.

D - Menagerie

自力AC : 25分

最初をSS, SW, WS, WWと決め打って,順番に見て行く.最後に矛盾がないか確認する.boolをもっと上手く使えばオシャレに解けそう.

D - Simple Knapsack

自力AC : 30分

普通のナップサックにするため,全ての重さからまずw_0を引いてしまう.その後,取った個数もカウントしたDPをして,最後にその個数だけw_0の重みを足して可能かを判定する.こういうのがさばけるようになってきたのは良い.

 

---

明日も頑張りましょう.