2020-01-29から1日間の記事一覧
AtCoder
AtCoder1100点
DP
個数のみわかれば遷移が作れるDP
連結性を管理するDP
挿入DP
探索順序を工夫して解く
ソート
包除原理
数え上げ問題
被覆する方法の数え上げ
区間
ナップサックDP
選択肢が広い方か狭い方から決めていく
調和級数
見積り大事
二項係数
被覆
ARC-like
赤色diff
ARC-E
区間の連結関係に関する問題
すごく面白かった!!!!!!! 問題へのリンク 問題概要 長さ のマス目があって、長さがそれぞれ の 個の区間を配置していきたい。 個の区間がすべてのマスを被覆するような配置方法は何通りあるか、1000000007 で割ったあまりを求めよ。 制約 考えたこと …
面白かった 問題へのリンク 問題概要 二次元平面上に 個の点がある。これらの各点 に対し、 を満たす点 に電波が届く。 から までの長方形区間全体に電波が届くかどうかを判定せよ。 制約 考えたこと 全体を覆っているとき、以下のいずれかは成立しているこ…
最適解の形を丁寧に場合分けして考える系 問題へのリンク 問題概要 の板チョコレートを 3 つの長方形に割りたい。そのときの 3 つの長方形の面積の最大値と最小値の差の最小値を求めよ。 制約 考えたこと まず思ったのは、 のうちの少なくとも一方が 3 の倍…
AtCoder
AtCoder800点
ARC-F
フロー
グラフ問題
グリッド
最小カット
頂点に容量があるフロー
denseなグラフをスーパーノードでsparseにする
グラフの考えるべき辺数を減らす
最小コスト
黄色diff
見るからに最小カットだけど、こういうの意外と詰め切るのに時間がかかるイメージがある... 問題へのリンク 問題概要 の二次元グリッドが与えられる。各マスは 'S' のマス:カエルがいる 'T' のマス:カエルがそこにいきたい 'o' のマス:葉っぱがある '.' …