e869120さんの初中級者が解くべき過去問精選 100 問をC言語で全問解いてみた。
他の人に対するアドバイス的な感想は
にかいた。
ここで書くのは、もう少し個人寄りの感想&分析。
- 木に関する問題(特に全ての点で答えを導出するような問題) は苦手だということがわかった。全点での解の導出はまずワーシャルフロイド法が思い浮かぶが、N>=5000以上で太刀打ちできないから別途違うアルゴリズムを考える必要がある。
というより、自分が解いたグラフ問題のバリエーションがまだまだ足りない気がするので、もう少しいろんな問題に取り組んだほうが自信がつくかもしれない。
- 全方位木
区間DPが少し苦手(解き方に迷う)。区間のサイズの小->大にDPしていくので、
dp[size][start]のように取るとやりやすいと思う- 47問目 JOI 2015 本選 2 - ケーキの切り分け 2
- DPコン L - Deque .. 答えはここ
- 48問目 AOJ 1611 ダルマ落とし
- DPコン N - Slimes .. 一見すると、貪欲法で解けるが、
65254とかはWAになる。ダルマのやつと同じ発想で区間DP。
DPを「〇〇以上となる場合の数」というふうに定義して計算するのが苦手。例えば、
- DPL_1_B - 0,1ナップザック問題 はdp[N][W]の要素を「W以下の場合の」最大価値と定める
- D - サイコロ .. dp[N][p]を「積がピッタリpとなる確率」とすると、細かな小数点誤差でlong doubleでもWAになってしまう。dp[N][p]を「p以上になる確率」とすればD(divisor)の範囲内でDPすれば良いことになって、ACが取れる。
- 累積和で計算量を落とす手法は汎用的で便利。sumを計算する必要がある場面などは、累積和を用いて計算量を落とすのは定石な感じがする。
- 6問目 三井住友信託銀行プログラミングコンテスト 2019 D - Lucky PIN 三桁決め打ちで各々線形探索O(N)するのが模範解答だが、実は累積和を用いて各3桁のクエリについてO(1)でも解ける
- 52問目 JOI 2017 予選 4 - ぬいぐるみの整理
- 69問目 AtCoder Beginner Contest 084 D - 2017-like Number ..累積和を用いるとクエリの処理がO(1)になる。
- 71問目 Square869120Contest #1 E - 散歩 .. こちらはいもす法。
- 77問目 JOI 2010 本選 1 - 旅人 .. 経路の長さの累積和でも、経路の通った回数に関するいもす法でも。
- 79問目 AtCoder Beginner Contest 106 D - AtCoder Express 2 .. 二次元にして累積和
- 87問目 AtCoder Beginner Contest 120 D - Decayed Bridge .. 累積和というより、前までの合計値をkeepしておく
- 直近解いたのだと、
- abc017_4 D - サプリメント .. DPの計算量を落とすのに使用。
- ALDS1_4_D 割り当て .. 二分探索、各探索値で線形探索の解でも解けるが、二分探索、各探索値にて累積和の線形探索の解法でも解ける。累積和を出すと自然と単調増加列になるので、二分探索と相性が良い。下のバームクーヘンの問題もにた感じに見える。
- M - Candies .. idx番目までの数列で和がK以内のものを考える(dp[idx][K])。ループの中でsumがでてくるので、累積和を用いて計算量を落とす
- for文の中で配列の中で条件に合わなかったものをskipするような問題 が実装に時間がかかるのでやや苦手。
- 3問目 B - ATCoder ..連続したものをskipする
- 6問目 三井住友信託銀行プログラミングコンテスト 2019 D - Lucky PIN .. マッチしなかった場合skipする
- 18問目 ALDS_4_B - 二分探索 .. 想定解法は二分検索だが、query側の数列をソートして、queryが小さい限りqueryをskipする解き方がある。
- 100問の問題の他だと、しゃくとり法と呼ばれるアルゴリズムの実装がやや苦手。
- B - 細長いお菓子
- D - サプリメント .. しゃくとり法 + 累積和。答え。
- バームクーヘン(Baumkuchen) .. 最初の区間ぎめをしゃくとり法で。答えはここに
とか。
- ワーシャルフロイド法のひねった問題がとくのに時間かかった
ワーシャルフロイド法、https://gist.github.com/knknkn1162/3f04627fef38ab88fd4784fc8a3cf7cd のようにgraphの他に、viaという配列変数用意すると、その後再帰関数で経路を都度トレースできて、便利かもしれない(が役立てたことはまだない)
上級編のリンク見ると更に50問、問題が有りここまでなかなかたどり着けないだろうなぁ、と思った。
随時内容を足すかもしれない。
