カードや山札を扱う問題
言われた通りの操作を愚直に実行するのが、何も考えなくてよくて楽だと思う！ 問題へのリンク 問題概要 箱 A, B, C に、それぞれ数 の書かれたカードを入れる。 箱 A, B の中身を入れ替える 箱 A, C の中身を入れ替える これらの操作を順に実行したあとの、…
AtCoder
AtCoder600点
ABC-F
橙色diff
2-SAT
制約:数値が10^6以下
密グラフ
グラフの辺数削減テク:スーパー頂点を用いてsparseに
グラフの辺数を削減する
2-SATの密を解消する累積OR
スラック変数
二値パラメータ問題
解空間:O(2^N)通りの選択肢
カードや山札を扱う問題
数学(整数問題)
見積り大事
Yes/No判定問題
互いに素
各素因数ごとに考える
そのまま覚えたいシンプル設定の中堅以上の典型問題
f(i,j)をiとjとに分離する
線形性に着目する
SAT
スーパー頂点を用意する
2-SAT の「密」を解消する累積 OR テクを学んだ！ 問題へのリンク 問題概要 枚のカードがあり、表には 、裏には が書かれている。各カードについて、表を上にするか、裏を上にするかを選択していく。 上手く選択することで、上を向いている数値がどの 2 つも…
AtCoder
AtCoder500点
ABC-D
ゲーム
ゲームDP
選べる手が実質的に1通り
最適化テク:自明な上界が最適解
DP
青色diff
ARC-D
得点差最大化ゲーム
カードや山札を扱う問題
数列
典型要素を詰め合わせた教育的問題
何も考えずにゲーム DP 毎ターン「実質的に取れる選択肢が二通りしかない」というパターン という包畜を含む教育的問題。 問題へのリンク 問題概要 先手と後手は初期状態で と と書かれたカードを持っている。 枚の山札があってそれぞれ の数値が書かれてい…
