テク:全体を2倍する
N個の区間の問題
全探索
全探索:for文
全探索:多重for文
区間
区間の交差
解空間:O(N^2)個のペア
解空間:O(N^2)通りの選択肢
NoviSteps4Q
数え上げ問題
AtCoder
AtCoder300点
ABC-C
灰色diff
テク:全体を2倍する
標準形を考える
これはちょっと整理が大変な問題。時々問題文に登場する 0.5 という数値がなんなのかを知れる問題とも言える。 問題へのリンク 問題概要 個の区間がある。各区間は 4 タイプあり、 タイプ 1：区間 タイプ 2：区間 タイプ 3：区間 タイプ 4：区間 となってい…
AtCoder
AtCoder400点
ABC-D
黄色diff
全探索
最適化テク:探索候補を絞る
ある値を固定して考える
計算幾何
重心を考える
凸包
多角形
ベクトルの集まりを外積を用いて符号化する
SをTにすることが目的の操作の問題
Yes/No判定問題
偏角ソート
そのまま覚えたいシンプル設定の中堅以上の典型問題
コーナーケース
テク:全体を2倍する
二次元平面上のN点の問題
操作
操作を好きな回数だけ行える
最適化テク:操作の流れを単純化する
連続最適化
連続量問題
数学(代数)
逆操作もvalid
NoviSteps2D
すごくシンプルだけど詰まる部分もたくさんありそうな問題 問題へのリンク 問題概要 二次元平面上に、2 組の 個の点集合 、 がある。 に含まれる 個の点に対して、一律に 原点を中心とした回転をする (角度は任意) 平行移動をする (移動量は任意) を実施する…
AOJ
RUPC
有志コン
クエリ先読み
平面走査
データ構造テク：全体に反映させる値を別にもつ(遅延評価)
セグメント木
データ構造
区間の連結関係に関する問題
エレベータ
クエリ処理問題
テク:全体を2倍する
区間
N個の区間の問題
グラフのconnectivity
Yes/No判定問題
遅延評価セグメント木
【問題集】遅延評価セグメント木
昔はこういうの苦手だったけど、今ならできる！ 問題へのリンク 問題概要 階建ての建物があって、後述するエレベータの建設をなくしては、下への移動は自由にできるが、上への移動は自由にできない。 個のエレベータ建設計画がある。 番目の計画では、 日目…
AtCoder
AtCoder600点
ARC-D
黄色diff
DP
数え上げ問題
入力が定数個
2^K
DP高速化
DP高速化:累積和
賢い漸化式
制約条件:総和=K
対象を一意に定める操作列を数え上げる
テク:全体を2倍する
いろんな DP が考えられそう！ 問題へのリンク editorial 問題概要 正整数 が与えらる。以下の条件を全て満たす有理数の多重集合は何種類存在するか、998244353 で割ったあまりを求めよ。 多重集合の要素数は 多重集合の要素の総和は 多重集合の要素は全て (…
