2018-09-17から1日間の記事一覧
共通接線ライブラリの整備 問題へのリンク 問題概要 互いに重ならない円が N 個ある。 直線を考えたとき、そのスコアは 各円に対して、その円と共有点を持たず、その円との距離がある一定 (円に依存して決まる値) 以下であるとき 1 を加算、そうでないとき 0…
3 次元幾何の練習 問題へのリンク 問題概要 円錐を平面によって切断するとき、分離された2つの部分の体積を求めよ。 解法 ちょっと複雑だが、2次元に射影して考える。 そのためには、3次元幾何の正射影が必要になる #include <iostream> #include <vector> #include <cmath> #include <iomanip></iomanip></cmath></vector></iostream>…
文字列
部分列
部分列DP
DP
数え上げ問題
テク:区間ごとに分割する
不変量
パリティ
操作
条件の言い換え
DP高速化
AtCoder
AtCoder1300点
AGC-E
ダブルカウントを防ぐ場合分け
操作後の結果の数え上げ
操作:2つのものを1つにマージ
銀色diff
「次の要素」へのポインタを求める
対象を一意に定める操作列を数え上げる
2 日目:AGC 027 E - ABBreviate (1300 点)https://t.co/mvWcvtxfRz3 で割った余りについて不変量であることは既出。重複を除くために「文字列の部分文字列の数え上げ」的な考え方をするのも恐らく典型。自力で詰め切るのはまだ辛いけど「赤くならないうちは…