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