問題 atcoder.jp 解法 これと同じ感じでやる。 atcoder.jp ある数が2番目に大きい区間はどういう特徴があるか考える。 よく考えるとはより大きい数をちょうど1つ含んでいる区間である事がわかる。 より大きく、かつより右側にあるもののうち一番左側にあるも…

このAGCは引越の疲れで参加できてなかった... 問題 atcoder.jp 解法 手で実験してみるとDPぽいな〜と思ったのでDPを考えます. に対する塗り方の個数 とします. 色が切り替わるときに注目します. いま，j+1番目の石を見ているとしましょう. さらにj+1番目の石…

問題 atcoder.jp 解法 連結無向グラフから枝を取り除いていったときに非連結な頂点のペアの個数を答える問題.一般に，グラフから枝や頂点を取り除くという操作は難しいです. 逆に枝や頂点を追加するという操作は比較的かんたんです.今回の場合，枝を後ろから…

問題 atcoder.jp 解法 まずT,S,Z型は使えません. また，O型はそれ単体で横の長さが2の長方形になので必ず求めたい長方形に含めることができます. 結局I,J,L型の組み合わせを考えればいいです.同じ型を２つ組み合わせることで横の長さが4の長方形ができます.(…

問題 atcoder.jp 解法 まずとの色は一致するので入力のをとしていいです.黒色の正方形の左下をどこにするかで平面の色の塗り方は決まります. 塗り方の周期性から黒色の正方形の左下の座標の候補はとしていいです.したがって個の塗り方全てに対して叶えられる…

問題 atcoder.jp 解法 最大クリークを求める問題 (無向グラフGのクリークとはGの完全部分グラフ(の頂点集合)のこと). 頂点数が少ないので全ての部分グラフを見てあげることができる. 全列挙にはbitを使うのが便利. #include <iostream> #include <vector> #include <set> using name</set></vector></iostream>…