2019-09-15から1日間の記事一覧
Codeforces
最適化テク:解を変形していく(最適性を失わずに)
DP
O(3^N)
bitDP
Greedy
前処理
行列
最適化テク:探索候補を絞る
グラフの辺数を削減する
操作
操作:circular_shift
操作後の結果の最適化問題
CodeforcesCombined
CodeforcesR2400
指数探索系問題
マルチテストケース問題
最大スコア
操作を好きな回数だけ行える
最適化問題
すんごく横長な行列に関する問題だけど、実は横の長さを縦の長さ以下にできるというタイプ。 そうすれば の問題に帰着できて、。あとは の bit DP...なのだが、TLE がとれなかった。微妙に詰めが甘かった。。。 問題へのリンク 問題概要 の行列があたえられ…
Codeforces
Union-Find
グルーピング(算数)
グラフ
順列を題材とした問題
順列の最適化問題
算数と数学
グルーピングの最適化
CodeforcesCombined
CodeforcesR1700
面白かった! 問題へのリンク 問題概要 組の 2 整数 () があたえられる。 を満たす。この 組の 通りの順序すべてを考えたときの以下のように定義される「悲しみ」の最小値を求めよ。 「これまでに登場した整数」を表す集合を とする 各 i について、 がとも…
ちょっとややこしかった 問題へのリンク 問題概要 '0' 〜 '9' からなる 文字の文字列があたえられる。各文字を白黒に塗る。 どの黒く塗られた数も、あらゆる白く塗られた数以上である 白く塗られた数を元の文字列の順序で抜き取ったとき、数値は単調非減少で…
Codeforces
グルーピング(算数)
Greedy
Greedy:今が良いほど未来も良い
Greedy:交換しても悪化しない
最適化テク:解を変形していく(最適性を失わずに)
数列
数学(整数問題)
最大値や最小値に着目する
グルーピングの最適化
CodeforcesCombined
CodeforcesR1500以下
誤読して大きく出遅れた... 問題へのリンク 問題概要 個の整数 があたえられる。これを何個かのグループに分けて、各グループについて「グループ内のすべての整数がグループ内の最小値で割り切れる」という条件を満たすようにしたい。 これを実現するための…