2020-01-30から1日間の記事一覧
教育的だと思ったのでメモだけ。 問題へのリンク 問題概要 整数 が与えられる。 以上 未満の整数 であって を満たすものの個数を求めよ。 解法 の最大公約数を として のオイラー関数値が答え。 #include <iostream> #include <sstream> #include <cstdio> #include <cstdlib> #include <cmath> #include <ctime></ctime></cmath></cstdlib></cstdio></sstream></iostream>…
Codeforces
順列を題材とした問題
操作
データ構造
セグメント木
遅延評価
StarrySkyTree
差分更新
ある量を固定して考える
in-place DP
DP
最小コスト
CodeforcesR2200
EducationalCodeforces
遅延評価セグメント木
最適化問題
これを思い出して迷走してしまった (それでも通る解法には至ったけど恐ろしく煩雑なものとなってしまった)。 drken1215.hatenablog.com なぜもっとシンプルに考えられなかったのか... 問題へのリンク 問題概要 の順列 と、各要素 を動かすのに必要なコスト …
Codeforces
数え上げ問題
区間
DP
累積和
DP高速化:累積和
DP高速化
座標圧縮
二項係数
区間分割型ナップサックDP
確率
重複組合せ
包除原理
包除原理:DP
数列
グラフ・盤面・数列の個数の数え上げ
各区間から1点ずつとってくる問題
座標圧縮したグリッド上のDP
EducationalCodeforces
CodeforcesR2600
制約条件:xi<=ai
個人的要復習
そのまま覚えたいシンプル設定の中堅以上の典型問題
DP状態:最後の場所
座標圧縮をがんばる 問題へのリンク 問題概要 個の区間 が与えられる。それぞれの区間から一様ランダムに整数を選んでいく。 これが広義単調減少となる確率を求め、それを 998244353 で割ったあまりの形式で求めよ。 制約 考えたこと 区間の幅は大きいが、 …