最近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
- これも今なら解けるかな…。
- 座標上の点がランダムで指定されるなら、空間を分割すると検索対象を絞ることができる。
まとめ
今見てもさらっと解けなさそうなものもあるので反省。
今後この記事続けるかは気分次第です。
