2019-02-18から1日間の記事一覧
AtCoder
AtCoder300点
unrated公式コン
マンハッタン距離
Greedy:各要素について独立に考えてよい
中央値(メディアン)に関する問題
二次元グリッド
差分更新
K番目を求める
絶対値やminを扱う問題
二次元平面上のN点の問題
縦方向と横方向の情報を整理する
前処理
典型要素を詰め合わせた教育的問題
駒(コマ)や石やコインを扱う問題
N個からK個を選ぶ設定の問題
最小回数・最小個数を求める
x軸とy軸について独立に考えてよい
最適化問題
こういうのを爆速で書けるようになりたい。問題としては マンハッタン距離に関する問題では x 軸方向と y 軸方向とで独立に考えればよいことになるケースが多い (マンハッタンに限らず、各要素ごとに独立にならないかを考察することは重要) の最小値を与える…
数式が一見ややこしいけど難しくなくて、k 進法についての理解を問う感じ 問題へのリンク 問題概要 2 つの整数が 進法表記で与えられる。どちらの方が大きいかを判定せよ。 1 個めは 桁で、最高位から順に 2 個めは 桁で、最高位から順に 考えたこと 日経コ…
AtCoder
AtCoder200点
unrated公式コン
累積和
各kに対して
クエリ処理問題
数列
区間
前処理
解空間:O(N^2)通りの選択肢
解空間:O(N^2)個の区間
累積和テク:区間の総和を累積和で高速に求める
そのまま覚えたい典型問題
【問題集】累積和
【問題集】累積和・いもす法
連続部分列を扱う問題
最大スコア
最適化問題
累積和の練習 問題へのリンク 問題概要 個の整数 が与えられる。 各 に対して、数列の 個の連続する区間の値の和の最大値を求めよ。 制約 考えたこと 愚直にやると計算量は の値が 通り考える必要があって 各 に対して 個の区間があって 各区間に対して 個の…