交差数に関する問題
AtCoder
ARC-E
AtCoder700点
黄色diff
NoviSteps2D
stack
操作をstackを用いて高速化する
交差数に関する問題
ギリギリ
最適化テク:端点のみを考える
二次元平面上のN点の問題
Yes/No判定問題
そのまま覚えたいシンプル設定の中堅以上の典型問題
面白かった！ 交差数に関する問題に帰着される。 問題へのリンク 問題概要 座標平面上に、4 頂点の座標が であるような長方形があり、その長方形の周上または内部に、 とラベルのついた 個の点がある（どの 2 点も相異なる）。 について、同じラベル の 2 点…
AtCoder
AtCoder500点
ABC-E
緑色diff
NoviSteps1Q
stack
シミュレーション:stackの活用
操作をstackを用いて高速化する
交差数に関する問題
Yes/No判定問題
入れ子構造
弦が交わるかどうかを判定するという、スタックの典型問題！ 問題へのリンク 問題概要 次の図のように、円周上に 個の点 があり、 本の弦がある（図は のとき）。 弦に交差があるかどうかを判定せよ。 制約 考えたこと この問題は stack で解けることで有名…
Codeforces
CodeforcesCombined
CodeforcesR1800
交差数に関する問題
最大回数・最大個数を求める
ギャグ要素高め
Greedy
Greedy:交換しても悪化しない
マルチテストケース問題
解空間:O(N!)通りの選択肢
グルーピングの最適化
最大スコア
グルーピング
最適化問題
企業合コンで解いた。ギャグ系だった。 問題へのリンク 問題概要 円周上に 個の点があって、2 個ずつ 組のペアを作って線分で結ぶ。 すでに 組のペアができていて、線分が結ばれている。残りの点についてペアを作って線分を作っていったときの交差数の個数の…
Codeforces
CodeforcesCombined
CodeforcesR2900
数え上げ問題
入れ子構造
変数変換して扱いやすい同型な問題を見出す
ワイルドカード問題
二項係数
DP
解空間:O(N^2)通りの選択肢
数珠
「選ぶ」と「選ばない」の一対一対応
期待値
0と1の問題
多項式・FPS(形式的冪級数)
カッコ列
交差数に関する問題
ぷよぷよみたいに 2 つ揃うと消えるような対象物の数え上げ問題。これを思い出した drken1215.hatenablog.com 問題へのリンク 問題概要 (意訳) "B", "W", "?" のみからなる長さ の文字列が与えられる ( は偶数)。"?" に "B", "W" を割り当てる方法のうち、"B…
