ABC275F 解法 \(a_{i}\) を残すとき 0, 消すとき 1 として，01 列を考える． 1 が連続している区間の個数を最小化する問題となる． 区間を数える代わりに，[01] の並びを数えると考えるとよい． [11], [00], [10] は数えないとする． つまり，01 列において …

ABC309F 解法 平面走査． 2次元 segtree は，1次元を 2方向にとる． まず回転が 6通りあるが，これは直方体のどの面を一番下にするかが 6通りあって， それらに 1対1 対応する． つまり，回転するということは，自由に辺の長さを並び変えることに対応する． …

ABC271F 解法 半分全列挙． 最短ルートで移動したとき，右上から左下の対角線 \(l\) を一度だけ通る． \(l\) で正方形を 2分割して，それぞれで計算した結果をつなげる． 左上から \(l\) への移動方法は，雑に見積もって \(2^{n}\)通り． 点 \(\,(x,y\,)\) …

ABC270F 超頂点を用いる． \(a,b\) が空港同士とする． \(a,b\) を直接結ぶのではなく，超頂点 \(\tilde{v}\) を経由して， \(a\) - \(\tilde{v}\) - \(b\) とする． これにより， 頂点 \(a,b\) が空港であるという情報を 辺に移すことができた ので， 連結…

ABC269F 解法0 左上基準で長方形を調べる． 解法1 \(1\)-indexed で考える． 市松模様をさらに2種類に分ける． \(a,c\) の偶奇で場合分けしていくが， まずは簡単のため \(a,c\) が共に奇数の場合だけ考える． 等差数列の和の公式を使えばよい． 使っている…