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