2018-09-06から1日間の記事一覧
ある量を固定して考える
ABC-C
AtCoder
AtCoder300点
緑色diff
N個からK個を選ぶ設定の問題
最適化テク:最適解の形を考える
ARC-C
一直線上のN点の問題
最小コスト
点が移動していく問題
最適化問題
問題概要 N 本のろうそくが一直線上に並んでいる。最初は原点にいて、N 本のうち K 本のろうそくに火をつけたい。ろうそくと同じ座標に到達すると火をつけることができる。火をつけるのに要する時間は 0 秒である。移動距離を最小化せよ。 解法 K 個の連続す…
クエリ処理問題
区間
区間ソート
平面走査
セグメント木
BIT
ABC-D
AtCoder400点
AtCoder
水色diff
クエリ:区間
区間の交差
N個の区間の問題
イベントソート
全部混ぜて解く
クエリ先読み
典型要素を詰め合わせた教育的問題
いろんな方法が考えられそう。 せっかくなので、敢えて、N が大きくても OK な方法でやってみる。hama_du さんの記事を参照。 問題概要 M 個の区間 [l_i, r_i] が与えられる。以下の Q 個のクエリに答えよ: 区間 [p, q] に完全に含まれる区間が何個あるかを…