2019-06-17から1日間の記事一覧
AtCoder
AtCoder400点
unrated公式コン
フロー
グラフ
二次元グリッド
二部グラフ
最大安定集合・最小点被覆・最小辺被覆
マッチング
二部マッチング
パリティ
市松模様・塗り分け
けんちょん本演習問題
最大安定集合問題
NP困難(特殊構造なので解ける)
そのまま覚えたい典型問題
【問題集】フローの入門
駒(コマ)や石やコインを扱う問題
「二部グラフの最大安定集合問題」について知っていれば典型問題ですね。 問題へのリンク 問題概要 のグリッドがあります。各マスは白黒に塗られています。今、白いマスにできるだけ多くのコマを置きたいものとします。 各マスに 1 個のみコマを置ける コマ…
AtCoder
AtCoder400点
AGC-B
テク:スタートを0としてよい
連結性に着目する
区間
条件の言い換え
Yes/No判定問題
数列
テク:移動可能区間を遷移していく
青色diff
考える整数が連続することに着目する
むむむ 問題へのリンク 問題概要 長さ の整数列 であって、 が 以上 以下の整数 となるものが存在するかどうかを判定せよ。 制約 考えたこと とりあえず , としてよい。 さて、 からスタートして、 ターン目にどんなのを作れるかを考察してみる。 1 ターン目…
AtCoder
AtCoder400点
ABC-D
しゃくとり法
二分探索
累積和
区間
数列
解空間:O(N^2)通りの選択肢
二分探索:lower_bound
緑色diff
【問題集】累積和・二分探索法・しゃくとり法
数え上げ問題
制約条件:総和<=K
連続部分列を扱う問題
解空間:O(N^2)個の区間
超典型的なしゃくとり法そのものだった!!! 問題へのリンク 問題概要 個の整数 があたえられる。 数列の連続した区間であって、その総和が 以上となっているものを数え上げよ。 制約 考えたこと しゃくとり法については以前に記事を書いた。 qiita.com こ…
長方形を直線で真っ二つに割る方法について 直線が長方形の対角線の交点を通る 直線が長方形を二等分する というのは同値だという話。結構、中学受験の算数では定番の話だったりする。 問題へのリンク 問題概要 二次元平面上で を頂点とした長方形と、その内…