2020-01-29から1日間の記事一覧
AtCoder
AtCoder1100点
DP
DP状態削減テク:全部分集合でなく個数のみ持つ
挿入DP
探索順序を工夫して解く
包除原理
数え上げ問題
被覆する方法の数え上げ
区間
ナップサックDP
選択肢が広い方か狭い方から決めていく
調和級数
見積り大事
二項係数
被覆
ARC-like
赤色diff
ARC-E
区間の連結関係に関する問題
高度典型
思わず解きたくなる興味深い良問
個人的要復習
固定長区間が制約条件を持ちながら左右に移動する問題
N個の区間の問題
すごく面白かった！！！！！！！ 問題へのリンク 問題概要 長さ のマス目があって、長さがそれぞれ の 個の区間を配置していきたい。 個の区間がすべてのマスを被覆するような配置方法は何通りあるか、1000000007 で割ったあまりを求めよ。 制約 考えたこと …
AOJ
JAG
AOJ-ICPC250点
マンハッタン距離
Greedy:各要素について独立に考えてよい
二次元平面上のN点の問題
区間
AOJ-ICPC
JAG夏合宿
伝播していく様子をテーマにした問題
x軸とy軸について独立に考えてよい
面白かった 問題へのリンク 問題概要 二次元平面上に 個の点がある。これらの各点 に対し、 を満たす点 に電波が届く。 から までの長方形区間全体に電波が届くかどうかを判定せよ。 制約 考えたこと 全体を覆っているとき、以下のいずれかは成立しているこ…
AtCoder
AtCoder400点
場合分け
最適化テク:最適解の形を考える
最大値と最小値の差を扱う問題
最適化テク:解を変形していく(最適性を失わずに)
二次元グリッド
ABC-C
緑色diff
ARC-C
均等に分ける
区間分割の仕方を走査する問題
典型要素を詰め合わせた教育的問題
ある量を固定して考える
パリティ
最適解の形を丁寧に場合分けして考える系 問題へのリンク 問題概要 の板チョコレートを 3 つの長方形に割りたい。そのときの 3 つの長方形の面積の最大値と最小値の差の最小値を求めよ。 制約 考えたこと まず思ったのは、 のうちの少なくとも一方が 3 の倍…
AtCoder
AtCoder800点
ARC-F
フロー
グラフ
二次元グリッド
最小カット
頂点に容量があるフロー
グラフの辺数削減テク:スーパー頂点を用いてsparseに
グラフの辺数を削減する
最小コスト
黄色diff
【問題集】フローのステップアップ
【問題集】フローの入門
グラフのconnectivity
スーパー頂点を用意する
最適化問題
見るからに最小カットだけど、こういうの意外と詰め切るのに時間がかかるイメージがある... 問題へのリンク 問題概要 の二次元グリッドが与えられる。各マスは 'S' のマス：カエルがいる 'T' のマス：カエルがそこにいきたい 'o' のマス：葉っぱがある '.' …
