コンテストでの時間切れや解けなかった過去問を振り返って供養していく 問題 Difficulty: 2187 (記事作成時点) 供養 解法 取り出し方が一意に定まるような長さ $k$ の部分列の添字列を $x_{1} \lt \dots \lt x_{k}$ としたとき、先頭と最後に $x_{0} = 0, x_…

コンテストでの時間切れや解けなかった過去問を振り返って供養していく 問題 Difficulty: 2350 (記事作成時点) 供養 解法 簡単のため多角形がすべて長方形の場合を考えると、長方形が $(x_{i, 1}, y_{i, 1}), (x_{i, 1}, y_{i, 2}), (x_{i, 2}, y_{i, 1}), (…

コンテストでの時間切れや解けなかった過去問を振り返って供養していく 8/2: AtCoder beginner Contest 174 F - Range Set Query 供養 問題 Difficulty: 1575 (記事作成時点) 解法 の順に見ていき、各色 について最後に登場した位置 を記録しておく BITを用…

コンテストでの時間切れや解けなかった過去問を振り返って供養していく 5/15: AtCoder Regular Contest 052 D - 9 供養 問題 Difficulty: 2355(estimated) (記事作成時点) 解法 十進表記した の各桁の和を としたとき、 より であればよい としたとき、 と表…

コンテストでの時間切れや解けなかった過去問を振り返って供養していく 4/22: DISCO presents ディスカバリーチャンネル プログラミングコンテスト2016 本選 C - 特別講演「括弧列と塗り分け」 供養 問題 Difficulty: 2162(estimated) (記事作成時点) 解法 …

コンテストでの時間切れや解けなかった過去問を振り返って供養していく 2/22: AtCoder Grand Contest 014 D - Black and White Tree 供養 問題 Difficulty: 2293 (記事作成時点) 解法 木 が完全マッチング可能な場合かつその限りにおいて後手が勝つ ある完全…

コンテストでの時間切れや解けなかった過去問を振り返って供養していく 2/1: AtCoder Regular Contest 074 F - Lotus Leaves 供養 問題 Difficulty: 2205 (記事作成時点) 解法 最小カットに帰着する方法と、 間の局所点連結度を求める方法がある 解法1: 最小…

コンテストでの時間切れや解けなかった過去問を振り返って供養していく 1/22: AtCoder Beginner Contest 152 F - Tree and Constraints 供養 問題 Difficulty: 1903 (記事作成時点) 解法 条件のどれか1つでも満たさないようなパターンを数える 条件 を満たさ…

コンテストでの時間切れや解けなかった過去問を振り返って供養していく 1/8: AtCoder Beginner Contest 140 F - Many Slimes 供養 問題 Difficulty: 2066 (記事作成時点) 解法 以下の条件を満たす完全二分木を考える 葉に の各要素の値を重複なく持つ 葉以外…

概要 要素の更新がありうる数列について、区間和の計算が高速にできる 同様に更新ありの任意区間の区間和を高速に計算可能なSegment Treeと比較して空間計算量が半分程度 ただしSegment Treeのように最小値などの計算に使うといったような応用力はない Segme…