ARC085 D: ABS

D - ABS

解き方

  • 本来は2パターンだけ考えれば良いらしい
    • この手の「何個か取り除いてなくなったら終わり」系のゲームってそういうの多い気がする
  • DPを使った方法
    • Yがa_iを持ってXに手番が回ってきたときの最大値、Xがa_iを持ってY似て番が回ってきたときの最小値、をそれぞれ後ろからDPで埋めていけば解けた

ハマったところ

  • DPの構成に手間取った
    • 最初はXがa_i, Yがa_jで手番がX or Yの3次元のDPをしていて、TLEする解法になっていた
  • (そもそもDPじゃなくても解けた)

github.com