複雑度がlogオーダー
AtCoder
AtCoder400点
ABC-D
ABC-like
水色diff
数学(整数問題)
各kに対して
N個のものうち1個を変更・削除したものを解く
クエリ処理問題
差分更新
前処理
ほとんどのところで値が一定値に決まる
複雑度がlogオーダー
各桁の和
0と1の問題
結構難しい!! 問題へのリンク 問題概要 正の整数 に対して、 := を二進法表現したときの各桁の総和を として を で割ったあまり := を で置き換える操作を繰り返したときに、何回で 0 になるか として定める。たとえば のとき、, より、 となる。 今、二進…
AtCoder
AtCoder1700点
AGC-F
フラクタル構造
再帰的構造に着目する
行列
行列累乗
係数を考える
連結成分
二次元グリッド
数え上げ問題
場合分け
ダブリング
数学的帰納法に基づく考察
複雑度がlogオーダー
銅色diff
頭がゴチャゴチャしてきて、詰め切るのがとても大変だった。 でも整理し切った後に出てくる性質は、至極単純なものだった。面白い。 問題へのリンク 問題概要 のグリッドが与えられ、各マスは白黒に塗られている。この盤面をレベル 1 のフラクタルとする。 …
初見時は証明なしに再帰的にやった... 問題へのリンク 問題概要 頂点の完全グラフがあたえられる。 このグラフの辺に、非負整数値を付けていく方法のうち 整数値が等しい辺のみからなる部分グラフが奇数長のサイクルを含まない という条件を満たす範囲内で、…
0と1の問題
AtCoder
AtCoder1000点
条件の言い換え
最適化テク:最適化する対象を入れ替える
AGC-D
行列
DP
区間
区間DP
しゃくとり法
再帰的構造に着目する
複雑度がlogオーダー
添字のとりうる範囲がlogオーダー
フラクタル構造
赤色diff
これを解けなかったのが強い敗北感。 DP 配列が巨大になりそうなときに、最適化する対象を入れ替えるテクは今までなんども見ているのにそれが思いつかない思考の硬さを思い知らされた。 問題へのリンク 問題概要 0 と 1 のみからなる行列の複雑度を すべて同…