ARC087 D: FT Robot

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

arc087.contest.atcoder.jp

解き方

  • 以下の2つを前計算する
    • x方向に動ける距離：x_0, x_1, ..., x_n
    • y方向に動ける距離：y_0, y_1, ..., y_n
  • 以下のdpを埋める
    • dp[a] := x座標の絶対値をaとすることができる最大の移動回数
  • 同様にyも埋めて、dp[x] = n, dp[y] = nとなるかで判定
  • 移動は正方向、負方向どちらにも動いてよいが、最初のx_0だけは正方向にしか動けないので、座標変換する

github.com

ARC087 C: Good Sequence

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

arc087.contest.atcoder.jp

解き方

  • 各数字が何個含まれるか調べて、条件を満たさない数字を条件を満たすように取り除く
    • nがm個ある時、n > mならn-m個除き、n < mならn個除く

procon-workspace/c.cc at master · HiroakiMikami/procon-workspace · GitHub

COLOCON 2017: C すぬけそだて――ごはん――

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

colopl2018-qual.contest.atcoder.jp

解き方

  • 同時に選択してはいけないペアn, mを事前に列挙しておく
  • カードn (A <= n <= B)について、入れるかどうかを場合分けしながら（再帰関数で実装）個数を数え上げ

procon-workspace/c.cc at master · HiroakiMikami/procon-workspace · GitHub