kmjp's blog

競技プログラミング参加記です

高難易度帯ポイントおさらい : ARC001~ARC010

最近AtCoder系の成績が振るわないので、過去問の解法ポイントをおさらい。
対象はARC最終問題およびAGC1000pt以上が中心だけど、900pt以下でも苦戦したものは取り上げる。


ARC001 D - レースゲーム

  • 凸包むに近い感じで次の到達点を決めていく。
  • 通過点が一意に確定する点に着目する。

AtCoder ARC #002 : D - ボードゲーム - kmjp's blog

  • これは今なら解けそう。
  • 必敗条件を考え、そこまでの猶予ターン数の差を最大化することを考える。

ARC003 D - シャッフル席替え

  • 許容誤差をちゃんと見よう。許容誤差が大きければ乱択も選択肢に入る。
  • でもこういう問題今後出そうな気しないな…。

ARC004 D - 表現の自由 ( Freedom of expression )

  • 整数を複数の整数の積で表す場合は、まず素因数分解と重複組み合わせを考える。
  • これ当時は変な解き方したけど、今なら簡単に解けそう。

ARC005 D - 連射王高橋君

  • 限られた条件のもと、複数の整数の和で何かの値を表現するとき、下の桁から1桁ずつ合わせていくことを考える。
    • その際、適宜キャリーも含めて考えていく。

ARC006 D - アルファベット探し

  • これは本番も解けてたし特にいうことないかな…。

AtCoder ARC #007 - kmjp's blog

  • 多倍長整数が使える言語を抑えておくといいですね。

AtCoder ARC #008 : D - タコヤキオイシクナール - kmjp's blog

  • SegTreeに一次式を載せ合成していく。これも今なら簡単に解けそう。

AtCoder ARC #009 : D - 覚醒ノ高橋君 - kmjp's blog

  • これは丁寧に実装しましょうって感じかな。

AtCoder ARC #010 : D - 情報伝播 - kmjp's blog

  • これも今なら解けるかな…。
  • 座標上の点がランダムで指定されるなら、空間を分割すると検索対象を絞ることができる。

まとめ

今見てもさらっと解けなさそうなものもあるので反省。
今後この記事続けるかは気分次第です。