ソート:要素の差について考えやすい形にする
AtCoder
AtCoder400点
ABC-D
式変形
解空間:O(N^2)通りの選択肢
考察：ソート
数列
累積和
絶対値やminを扱う問題
考察：一部の変数を固定して考える
個別の要素の動きに注目する
係数を考える
茶色diff
典型要素を詰め合わせた教育的問題
そのまま覚えたい典型問題
まずソートして考える
考察：主客転倒・寄与分解
解空間:O(N^2)個のペア
累積和テク:累積和や累積結果を前処理しておく
ソート:要素の差について考えやすい形にする
いろんな方法が考えられそう！ 問題へのリンク 問題概要 個の整数 が与えられる。 を満たすすべての の組に対する の総和を求めよ。 制約 考えたこと 絶対値のままだと厄介。ちょっと工夫する。まず、数列 の並びを入れ替えたとしても答えが変わらないことに…
AtCoder
AtCoder500点
ABC-E
緑色diff
N個のものうち1個を変更・削除したものを解く
データ構造テク：前処理
累積和テク:左右両端からの累積和や累積結果を前処理
累積和
最適化の考察：最適解の形を考える
最適化の考察：変形しても悪化しない
データ構造テク：差分更新
クエリ処理問題
二分探索:lower_bound
二分探索
数列
累積和テク:累積和や累積結果を前処理しておく
ソート:要素の差について考えやすい形にする
頭整理が大変だけど、考え方はわかる。 問題へのリンク 問題概要 は正の奇数である。 個の整数 が与えられる。以下の 個のクエリに答えよ。 各クエリでは整数 が与えられる 個の整数 を 2 個ずつペアにして 組のペアを作る それぞれのペアの「数値の差」の総…
AtCoder
AtCoder300点
ABC-C
データ構造
集計処理
考察：ソート
灰色diff
【問題集】ソート
ソート:各要素の個数の分布を求める
ソート:要素の差について考えやすい形にする
NoviSteps5Q
そのまま覚えたい易しい教育的典型問題
Yes/No判定問題
易しいYes/No判定問題
連想配列(setやmap)
setやmap:検索や削除が速いこと
計算量改善：setやmapの活用
数列
こういう「どの値が何個ありますか」的な処理方法は典型パターンが 2 つあると思う std::set や std::map などの連想配列を用いて管理する ソートしてソート順に処理していく 問題へのリンク 問題概要 個の整数 が与えられる。この整数列のどの 2 つの要素も…
AtCoder
AtCoder300点
ABC-C
考察：ソート
数列
中央値(メディアン)に関する問題
灰色diff
まずソートして考える
ソート:K番目を求める
ソート:要素の差について考えやすい形にする
【問題集】ソート
ソートして頑張る。 ソートすればいいと思い至りさえすれば、結構ソートするだけに近い感じの雰囲気の問題で、一瞬罠があるのかなと怖くなった。 問題へのリンク 問題概要 個の整数 が与えられる。 は偶数である。次の条件を満たすような整数 が何通りあるか…
AtCoder
AtCoder300点
ABC-C
考察：ソート
数列
考察：順序を工夫して解く
最大値と最小値の差を扱う問題
N個からK個を選ぶ設定の問題
灰色diff
【問題集】ソート
ソート:要素の差について考えやすい形にする
そのまま覚えたい易しい教育的典型問題
最小コスト
最大スコア
最適化問題
最適化の考察：最適解の形を考える
今の 300 点に比べると少し易しめで、でも 300 点っぽくていい感じだなと。 問題へのリンク 問題概要 個の整数 が与えられる。ここから 個の整数を選ぶ。 「選ばれた数の最大値と最小値の差」の最小値を求めよ。 制約 < 考えたこと すごく 300 点問題っぽく…
