2020-04-07から1日間の記事一覧
Codeforces
最適化テク:探索候補を絞る
遷移先が限られる
コーナーケース
解空間:O(N^2)通りの選択肢
ランレングス圧縮
見積り大事
CodeforcesDIV2
CodeforcesR2100
変化・遷移が限られる
方針立ってからも、ちょっと実装辛い ^^; 問題へのリンク 問題概要 長さ の正の整数列 と、正の整数 が与えられる。 正数列の連続する部分列であって、その積が、和の 倍となっているものが何通りあるかを求めよ。 制約 考えたこと パッと思うことは、積の中…
AtCoder
AtCoder400点
AGC-B
操作
最小コスト
ある量を固定して考える
ある量を決めるとGreedy
データ構造
数列
テク:循環するものを二週させる
数珠
差分更新
操作:2つのものを1つにマージ
青色diff
スライムやその合体をテーマとした問題
最適化問題
実装を柔軟にしたい 問題へのリンク 問題概要 体のスライムがあって、初期状態では、それぞれの色は となっている。以下の操作を繰り返すことで全てスライムを消滅させたい。そのために必要なコストの最小値を求めよ。 色 のスライムを消滅させる (コストは …
Codeforces
文字列
パリティ
転倒数
順列を題材とした問題
不変量
場合分け
操作
Yes/No判定問題
操作:reverse
操作を好きな回数だけ行える
SをTにすることが目的の操作の問題
操作:区間
逆操作もvalid
必要条件を列挙したら十分条件になる
CodeforcesDIV3
CodeforcesR2200
誤読したーーーーーー操作は 1 回しか行えないものと思って悩んでた 問題へのリンク 問題概要 長さ の文字列 が与えられる。以下の操作を好きな回数だけ行うことで、 と とが一致する状態にすることが可能かどうかを判定せよ。 1 以上 以下の整数 を定める …
Codeforces
DP
区間分割型ナップサックDP
復元
探索順序を工夫して解く
最適化テク:解を変形していく(最適性を失わずに)
グルーピング(算数)
グルーピングの最適化
算数と数学
CodeforcesDIV3
CodeforcesR2200
区間分割の仕方を走査する問題
最大値と最小値の差を扱う問題
DP 復元非本質>< 問題へのリンク 問題概要 人のコンテスタントを 3 人以上を 1 チームとしたいくつかのチームに分割したい。コンテスタント のスキルは である。 チーム分けの良さを、各チームごとの「メンバーのスキルの最大値と最小値の差」の合計値とす…