2019-06-29から1日間の記事一覧
AtCoder
AtCoder300点
ABC-C
ソート
数列
中央値(メディアン)に関する問題
灰色diff
まずソートして考える
ソート:K番目を求める
ソート:要素の差について考えやすい形にする
【問題集】ソート
ソートして頑張る。 ソートすればいいと思い至りさえすれば、結構ソートするだけに近い感じの雰囲気の問題で、一瞬罠があるのかなと怖くなった。 問題へのリンク 問題概要 個の整数 が与えられる。 は偶数である。次の条件を満たすような整数 が何通りあるか…
AtCoder
AtCoder600点
ABC-F
平方分割
DP
DP高速化
DP高速化:累積和
累積和
数え上げ問題
ナップサックDP
最適化テク:探索候補を絞る
数列
グラフ・盤面・数列の個数の数え上げ
黄色diff
テク:総和がNになる整数組の種類数はO(√N)
入力が定数個
こういう風にルートが出てくるの、こどふぉだとよく見るね。 ありがちなのが、長さ の線分を整数長ごとに分割するとき、分割の中に登場する長さの種類は 通りしかないとか、そういう形でよく出てくる。 問題へのリンク 問題概要 整数 が与えれる。 長さ の正…
AtCoder
AtCoder900点
ARC-E
テク:45度回す
マンハッタン距離
前処理
二分探索
グラフの辺数を削減する
グラフ
DFS
連結成分
二次元平面上のN点の問題
setの上手な使い方
データ構造
二分探索:lower_bound
赤色diff
縦方向と横方向の情報を整理する
めるアイコン変換すると良さそうなのはすぐに思い至った。そこから繋げられずに editorial を見た。 問題へのリンク 問題概要 二次元平面上に 個の点がある。このうちの 2 点 が指定されている。その 2 点間のマンハッタン距離を とする。 この 点について「…
AtCoder
AtCoder700点
ARC-E
ゲーム
最適化テク:自明な上界が最適解
最適化テク:固定する変数を入れ替えて考える
数列
二値パラメータ問題
最適戦略を求める
最適化テク:最適解の形を考える
青色diff
ある量を、一方は最大化したくて、他方は最小化したいというゲーム。これは ゲーム DP で解けるなら楽 ゲーム DP で解けるほど探索領域が小さくないなら、ある値 が存在して、以下を示す 先手は少なくとも 以上を達成できること 後手は少なくとも 以下を達成…