スイッチ
AtCoder
AtCoder625点
ABC-G
橙色diff
最小カット
フロー
【問題集】フローのステップアップ
マトロイドと劣モジュラ関数
グラフ
スイッチ
最小カット:K値変数をK-1個の0-1変数で表す
最小カット:PSP(燃やす埋める)
最小コスト
最小カット:すべてがTrueまたはFalseのときの利得を表す
最適化問題
2 変数劣モジュラ関数の和の最小化を最小カットにするやつ! 問題へのリンク 問題概要 種類のスキルがある。それぞれ初期状態のスキルレベルは 1 であるが、最大で 5 まで上げられる。スキル のスキルレベルを 1 上げるのに必要なコストは 円である。 種類の…
AtCoder
JOI
JOIG
JOI難易度4
累積和
前処理
累積和テク:左右両端からの累積和や累積結果を前処理
最適化テク:最適解の形を考える
場合分け
0と1の問題
条件の言い換え
盤面を予め変更する
操作
SをTにすることが目的の操作の問題
最小コスト
最小回数・最小個数を求める
スイッチ
【問題集】累積和
累積和テク:累積和や累積結果を前処理しておく
累積和テク:条件を満たすものの個数を累積和で表す
AOJ
最適化問題
落ち着いて整理して考えましょう。問題自体は「累積和」が使える良い問題ですね! 問題へのリンク editorial 問題概要 個の電球を一列に並べていて、オンオフ状態が であるような状態を作りたいとします。ただし は 番目の電球をオンにしたいことを表し、 は…
AOJ
JAG
3-SAT
SAT
ランダムウォーク
操作
全探索
応用的な探索
スイッチ
盤面を予め変更する
復元
二次元グリッド
枝刈り
パズル
計算量が本質的に改善する枝刈り
JAG模擬地区
AOJ-ICPC
AOJ-ICPC900点
指数探索系問題
マルチテストケース問題
(定数)×Nのグリッド
枝刈り探索が根本的に計算量改善することを示せることがある!!! 有名な例は最大独立集合問題に対する のアルゴリズムかなと。 指数時間アルゴリズム入門 from Yoichi Iwata www.slideshare.net 問題へのリンク 問題概要 下図 (公式解説より) のように な…
AtCoder
AtCoder300点
ABC-C
連立一次方程式
0と1の問題
全探索:ビット全探索
全探索
方程式
パリティ
Gauss-Jordanの掃き出し法
スイッチ
緑色diff
指数探索系問題
全探索:再帰関数
bit 全探索 問題へのリンク 問題概要 個のスイッチがある。スイッチによって 個の電球が点いたり消えたりする。 電球 は 個のスイッチに繋がっており、スイッチ のうち on になっているスイッチの個数を 2 で割った余りが に等しい時に点灯します。 全ての電…