ARC085 D: ABS

アルゴリズム/DP 競技プログラミング 競技プログラミング/AtCoder

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

ABC076 D: AtCoder Express

競技プログラミング 競技プログラミング/AtCoder

D - AtCoder Express

ハマったところ

  • cout << fixedしておかないと、浮動小数点数の表記が1e10みたいな表記になってWAになってしまう
    • templateを最初にcout << fixedするように修正済

github.com

ABC076 C: Dubious Document 2

競技プログラミング 競技プログラミング/AtCoder

C - Dubious Document 2

解き方

  • Tが1文字目から始まる場合、2文字目から始まる場合…をそれぞれ考える（埋まらない?にはaを入れると辞書順最小になる）
  • 全体で辞書順最小のものを選ぶ

github.com