この区間、１度も本番にDを通せていない…。
AtCoder ARC #021 : D - だいたい最小全域木 - kmjp's blog
- 許容される解の範囲が広いので、なんとか近似解を求める問題。
- 次元数が多いから大体正負だけ考えればよい。
- これ今見たら近似度がベクトルの角度で定義されていて距離は関係ないので、だからこの解法が成り立つんだな…。
AtCoder ARC #022 : D - スプリンクラー - kmjp's blog
- ARCで実装難度最難なんじゃないかという問題。
- 最近のAtCoderは幾何すくないので、こういうの今後出てこなさそう…（でても企業コン最終問題とか？）
AtCoder ARC #023 : D - GCD区間 - kmjp's blog
- これは今なら苦労せず解ける気がする。
- 数列において片方の端点を固定した状態で、もう片方の端点を動かしつつ区間内の数字のGCDを取ると、そんなにバリエーションは無い。
AtCoder ARC #024 : D - バス停 - kmjp's blog
- 10000≒1000*log(1000)ってのがミソ。
AtCoder ARC #025 : D - コンセント - kmjp's blog
- 一時期yukicoderで行数が非常に小さく、列が大きなグリッドに関するDPを何問もやったので、今なら迷わない気がする。
- (2^n)要素からなる数列を、行列累乗とかSegTreeで掛け合わせていくのはだいぶ抵抗がなくなった。
AtCoder ARC #026 : D - 道を直すお仕事 - kmjp's blog
- コストを2分探索で仮置きする問題。
- これ系苦手なんだよな…。
AtCoder ARC #027 : D - ぴょんぴょんトレーニング - kmjp's blog
- 区間の一部を更新するクエリで、周りへの影響がわずかである場合、SegTreeや平方分割を検討しよう。
AtCoder ARC #028 : D - 注文の多い高橋商店 - kmjp's blog
- いわゆる戻すDP。
- 「DPの結果から１つだけ除く」というときはこれを考えよう。
AtCoder ARC #029 : D - 高橋君と木のおもちゃ - kmjp's blog
- これも今ならあまり迷わないかな。
- 一見O(V^3)に見えて実はO(V^2)になるタイプの木DP。
AtCoder ARC #030 : D - グラフではない - kmjp's blog
- データ構造ゲーなので今のAtCoderだとあまりでなさそうだな…。
- これを永続データ構造と呼ぶのは違和感があるタイプです。分野における単語の違いなので、いい悪い・正しい正しくないではないんだけどね。
まとめ
こう見てみると、当時解けなかったけど今なら普通に解けそうな問題もある。
そういう意味では、たまにこのように見直すのは成長を実感できていいのかもしれない。
