2020-11-20から1日間の記事一覧
AtCoder
AtCoder700点
AGC-B
青色diff
パリティ
条件の言い換え
Greedy
必要条件を列挙したら十分条件になる
カッコ列
0と1の問題
最大スコア
二値パラメータ問題
非自明な比較関数でソートする
探索順序を工夫して解く
Greedy:条件を満たすまで大きい順に取っていく
最適化問題
めちゃくちゃ面白かった 問題へのリンク 問題概要 この問題では、"(", ")", "[", "]" からなる文字列を考える。 文字列 は,以下のいずれかの条件を満たすとき、良い括弧列と呼ぶ。 は空文字列である ある良い括弧列 が存在し、"(", , ")" をこの順に連結す…
AtCoder
AtCoder300点
AGC-A
緑色diff
文字列
Greedy
最小回数・最小個数を求める
操作
操作:swap
操作:隣接swap
辞書順
ある量を固定して考える
最適化テク:自明な上界が最適解
マルチテストケース問題
最適化問題
単純な探索でも解けるし、考察で計算量を減らすこともできそう。 問題へのリンク 問題概要 文字列 が与えられる。文字列 に以下の操作を最小回数行うことで、辞書順で > "atcoder" となるようにせよ。 中の連続する 2 文字を swap する (このテストケースが …
AtCoder
AtCoder1000点
AGC-D
橙色diff
数え上げ問題
DP
DP高速化
戻すDP
前処理
数列
グラフ・盤面・数列の個数の数え上げ
操作:区間に等差数列を足す
変数変換して扱いやすい同型な問題を見出す
個数重複も考慮したナップサックDP
ナップサックDP
累積和テク:左右両端からの累積和や累積結果を前処理
入力が定数個
平方分割
テク:総和がNになる整数組の種類数はO(√N)
制約条件:総和=K
最大値と最小値を求める
ダブルカウントを防ぐ場合分け
O(√N)まで考えれば十分
凸関数
K飛ばしで累積和
ジグザグ
階差数列
最初は二次元 FFT が必要な気分になっていて右往左往していた。個数制限なしナップサック問題になるのは面白かった! 問題へのリンク 問題概要 正の整数 が与えられる。長さ の非負整数列 であって という条件を満たすものの個数を、1000000007 で割ったあま…
Codeforces
グラフ
NP困難(特殊構造なので解ける)
クリーク
後退解析
queue
葉から考える
制約条件:グラフの次数列
Yes/No判定問題
復元
どれか1つ求める
定数倍高速化
部分グラフ列挙問題
見積り大事
O(√N)まで考えれば十分
CodeforcesDIV1-B
CodeforcesR2600
TLE が厳しくて話題になってた 問題へのリンク 問題概要 頂点数 、辺数 の単純無向グラフ [tex G] が与えられる。また、正の整数 が与えられる。 以下のいずれかの条件を満たすものが存在するかどうかを判定し、存在するならばそれを出力せよ。 type 1: の…