AGC-F
AtCoder
AtCoder1700点
AGC-F
フラクタル構造を解く
再帰的構造に着目する
行列
行列累乗
係数を考える
連結成分
グリッド
数え上げ問題
場合分け
ダブリング
数学的帰納法
複雑度がlogオーダー
銅色diff
頭がゴチャゴチャしてきて、詰め切るのがとても大変だった。 でも整理し切った後に出てくる性質は、至極単純なものだった。面白い。 問題へのリンク 問題概要 のグリッドが与えられ、各マスは白黒に塗られている。この盤面をレベル 1 のフラクタルとする。 …
AtCoder
AGC-F
数え上げ問題
操作後の結果の数え上げ
操作
条件の言い換え
二項係数
DP
区間分割型ナップサックDP
探索順序を工夫して解く
選択肢が広い方か狭い方から決めていく
トポロジカルソートの数え上げ
挿入DP
DP高速化
DP高速化:累積和
AtCoder1600点
ダブルカウントを防ぐ場合分けのテクニック
操作によって作れるものの集合を考える(判定関数を考える)
個数のみわかれば遷移が作れるDP
銅色diff
すごく楽しかった。 問題へのリンク 問題概要 色 のボールがそれぞれ 個ずつあります。 個のボールを好きな順序で並べ、各色について最も左側にあるボールを色 へと塗り替えました。 最終的な色の並びとして考えられる個数を 1000000007 で割ったあまりを求…
AtCoder
AtCoder2000~点
AGC-F
順列
操作:隣接swap
操作:swap
操作
逆順列を考える
条件の言い換え
変数変換して扱いやすい同型な問題を見出す
分割統治法
辞書順
探索候補を絞る
グラフ問題
グラフの考えるべき辺数を減らす
トポロジカルソート
priority_queue
Greedy
難しいGreedy
二次元平面上に可視化する
縦に見るものを横に見る
ソートすることが目的の操作の問題
操作後の結果の最適化問題
これも自力で解けたの、嬉しい!!!!! 問題へのリンク 問題概要 正の整数 が与えられる。 からなる順列 に対して、以下の操作を好きな回数だけ行ってできる順列のうち、辞書順最小のものを求めよ かつ を満たす に対して、 と を swap する 制約 まずは逆…
パリティ
DP
二分探索
ゲーム
条件の言い換え
DP値を利用して状態復元
AtCoder
AGC-F
AtCoder2000~点
区間
区間分割型ナップサックDP
DP高速化
DP高速化:オンラインオフライン変換
最大値の最小化
数列
操作
操作木を考える
銀色diff
ふと考えてみた。区間 DP っぽく にはなるな...なんて思っていたけどそこから落とせなかった...いやこれ何を食べたらこんな二分探索思いつけるようになるの!?!?!?!??? なにかこういう場面で二分探索すると上手く行くよ、というパターン的なものが…