ARC084 D: Small Multiple

arc084.contest.atcoder.jp

解き方

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

ハマったところ

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

github.com

ABC079 D: Wall

D - Wall

解き方

  • iを1にするための最小コストをWarshall Floydで求めてから計算

github.com

ABC079 C: Train Ticket

C - Train Ticket

解き方

  • opの組み合わせをすべてやっても2^3=8通りなので、全探索

github.com

ABC079 B: Lucas Number

B - Lucas Number

github.com

ABC079 A: Good Integer

A - Good Integer

ハマったところ

  • 連続する、の条件を見落としていた

github.com

活動記録(2017/11/13-2017/11/19)

競技プログラミング

ABC079

結果 140th Aでしょうもないミスをしてペナルティ食らったが、概ね順調

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