え、今日1問しかといてないのか 絶句・N マス目のなんたらbitDP。普通に上から一つずつやると中央値の判定がうまくいかない。i行目の状態を表すbit列をbiとしたとき、bi-1、bi+1が存在する事がbiの成立条件となる。よって、dp[j][b]を、j行目まで見たときに…

眠すぎる 応用情報、勉強する時間があるのか謎。。。 ・N - 入れ替えと並び替え (atcoder.jp) 解説ACした。Q回のswapで増加する転倒数は最大でQであり、ソートクエリのときは合計高々Q回のswapを行うことにより計算量が抑えられるというもの。 A[x]>A[x+1] …

眠すぎる 応用情報の締め切りは来週までか～ ・M - 食堂 (atcoder.jp) 詰め切るのが難しかった。 メニューの周期はDであることと、好みの料理を食べる回数⇔食堂の利用回数の関係を利用したいので、ダブリングが有効であると考えられる（i日目とj日目のメニュ…

今日はめちゃんこおねむにゃん ぷらにゃをぷにゃぷにゃ ・O - 可変全域木 (atcoder.jp) 結局、並列二分探索で解けた。 最小全域木を最初に構成し、そこにi番目の辺(u, v)を加えることを考える。 すると、もともと最小全域木に含まれていたu - vパス上の辺の…

ねむねむにゃんこ PASTを進めていました ・K - 巨大企業 (atcoder.jp) 単純に親を辿ることを考えると、子が1つの頂点が連なっていた場合にO(N^2)とかになって難しいことが分かる。aとbのLCAがbであればいいので、これで解ける。 ・J - 地ならし (atcoder.jp)…