2023-09-03から1日間の記事一覧
AtCoder
ABC-E
緑色diff
3つのものの真ん中に着目する
3つ組(i<j<k)の問題
累積和
累積和テク:左右両端からの累積和や累積結果を前処理
indexベースで考える
数列
解説あとで詳しく書く
典型要素を詰め合わせた教育的問題
ある量を固定して考える
【問題集】累積和・二分探索法・しゃくとり法
AtCoder450点
色んな解法がありそう。今回は、あまり解説書かずに備忘録程度に。 問題へのリンク 問題概要 長さ の数列 がある。各要素は 以上 以下の整数値である。 制約 メモ 各値ごとに考えていった。つまり、 として、 について求めていった。 各 について、 となる添…
AtCoder
ABC-F
黄色diff
ギリギリ
最適化テク:探索候補を絞る
最適化テク:端点のみを考える
一直線上のN点の問題
数え上げ問題
座標圧縮
平面走査
Greedy
マッチング
二部マッチング
区間
固定長区間が制約条件を持ちながら左右に移動する問題
AtCoder575点
高速な解法もあるっぽいけど、愚直に解いた。 問題へのリンク 問題概要 一直線上に 個の宝が座標 に配置されている。一方、長さが である 本の棒がある。次の条件を満たす整数 の個数を求めよ。 各 に対して、座標 の点を始点とするように棒を置いたとき、棒…
AtCoder
ABC-G
黄色diff
グラフ
フロー
【問題集】フローのステップアップ
【問題集】フローの入門
最大パッキングを求める
パッキング
グラフのconnectivity
頂点に容量があるフロー
Yes/No判定問題
中堅以上の典型要素を詰め合わせた教育的問題
AtCoder575点
点素パスのパッキング系の問題、出ないな〜〜と思っていたら出た! 問題へのリンク 問題概要 頂点数 、辺数 の単純無向グラフが与えられる。3 頂点 が指定される。 2 頂点 を端点とする単純パスであって、頂点 を通るものが存在するかどうか判定せよ。 制約 …
AtCoder
ABC-Ex
橙色diff
多項式・FPS(形式的冪級数)
DP
順列を題材とした問題
順列の数え上げ
順列テク:巡回群の直積と見る
FFT
DP高速化
DP高速化:FFT
分割統治FFT
分割統治法
二項係数
包除原理:対称性
包除原理
数え上げ問題
解空間:O(N!)通りの選択肢
指数型FPS
メタアルゴリズム問題
なもりグラフ
入力が定数個
数珠
AtCoder650点
オンライン処理を実現する分割統治法
コンテスト終了から 8 秒後の AC で泣いた。でも、分割統治 FFT が自力で書けてよかった。想定解法は FPS だった。 問題へのリンク 問題概要 次の問題がある。 の順列 と が与えられる。 これらをもとに次のように、頂点数 、辺数 の有向グラフを作る。 頂点…