ARC084 D: Small Multiple

アルゴリズム/最短経路 データ構造/グラフ 競技プログラミング 競技プログラミング/AtCoder

arc084.contest.atcoder.jp

解き方

  • +1、*10の2つの計算を辺、自然数を頂点としてグラフを作る
    • 自然数全体を頂点にはできないのでmod Kする
    • コストは各桁の和の変化量(それぞれ1, 0)
  • 01BFSで1 mod Kから0 mod Kまでの最短距離を求める

ハマったところ

  • 自然数の関係をグラフに落とし込む発想ができなかった
  • 01BFSを知らなかった
    • そろそろutil拡充（グラフ関連）をしたい

github.com

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