集合族に関する問題
AtCoder
AtCoder600点
ABC-G
赤色diff
しゃくとり法
45度回す
変数変換して扱いやすい同型な問題を見出す
ハニカム
クリーク
数え上げ問題
グラフ問題
マンハッタン距離
ダブルカウントを防ぐ場合分けのテクニック
差分更新
集合族に関する問題
部分集合を数える問題
条件の言い換え
二次元平面上のN点の問題
最大値や最小値に着目する
場合分け
ハニカムにそんな性質があるなんて!!! 45 度回転する技術のアナロジーが炸裂する。 あと、x 座標が最小となる点で場合分けする際に、同一の x 座標を持つものに対してダブルカウントを除去する工夫が大変だった。 問題へのリンク 問題概要 2 次元平面上に…
AtCoder
AtCoder900点
ARC-E
数え上げ問題
包除原理
包除原理:対称性
スターリング数
DP
補集合を考える
「選ぶ」と「選ばない」の一対一対応
二項係数
前処理
特殊なmod
集合族に関する問題
グルーピングの数え上げ
入力が定数個
グルーピング
赤色diff
部分点がなければ CE 2 完でも赤パフォ出たのに... それはともかく、この手の包除で絶対に解けるという安定感をもって解けるようになりたい! 問題へのリンク 問題概要 ラーメンに 種類のトッピングを自由に組み合わせて乗せることができます。トッピングの…
AtCoder
AGC-C
AtCoder800点
数学的帰納法
構築
グレイコード
0と1の問題
操作
パリティ
N次元空間
2^K
不変量
順列
スタートを0としてよい
集合族に関する問題
黄色diff
数列の構築
Yes/No判定問題
順列の最適化・数え上げ・求解
証明はできるし、その証明に基づいた構成を数学的に与えることまではできるけど、それを実装に落とすのがすごく大変な問題。。。 問題へのリンク 問題概要 整数 が与えられます。 の順列 であって、 次の条件をすべて満たすものが存在するかどうか判定してく…