2019-05-14から1日間の記事一覧
気づけばすぐな感じかな 問題へのリンク 問題概要 本のロープがあってそれぞれの長さは で与えられる。最初、ロープ の右端とロープ の左端が結ばれている。今、 長さが 以上のひとつながりのロープを選び、その中に結び目があればどれか 1 つ選んでほどく …
うまくシミュレーションする系 問題へのリンク 問題概要 N 個の箱があります。 箱は 1 から N まで番号が振られています。 最初、1 番目の箱には赤いボールが 1 個入っています。 また、2~N 番目の箱には白いボールが 1 個ずつ入っています。 高橋君は M 回…
AtCoder
AtCoder600点
AGC-C
数列
順列を題材とした問題
操作
条件の言い換え
操作:swap
操作:隣接swap
不変量
パリティ
最適化テク:自明な上界が最適解
ソートすることが目的の操作の問題
最小回数・最小個数を求める
最小コスト
水色diff
順列テク:順列は互換(swap操作)の積として表せる
最適化問題
楽しかった 問題へのリンク 問題概要 長さ の数列 が与えられる。どの 2 要素も互いに相異なることが保証される。これに対し 隣り合う 2 要素を swap する 連続する 3 要素を反転する という操作を行ってソートしたい。ただし、1 の使用回数を最小にしたい。…
AtCoder
AGC-F
数え上げ問題
操作後の結果の数え上げ
操作
条件の言い換え
二項係数
DP
区間分割型ナップサックDP
探索順序を工夫して解く
選択肢が広い方か狭い方から決めていく
トポロジカルソートの数え上げ
挿入DP
DP高速化
DP高速化:累積和
AtCoder1600点
ダブルカウントを防ぐ場合分け
操作によって作れるものの集合を考える(判定関数を考える)
DP状態削減テク:全部分集合でなく個数のみ持つ
銅色diff
高度典型
すごく楽しかった。 問題へのリンク 問題概要 色 のボールがそれぞれ 個ずつあります。 個のボールを好きな順序で並べ、各色について最も左側にあるボールを色 へと塗り替えました。 最終的な色の並びとして考えられる個数を 1000000007 で割ったあまりを求…