問題文 atcoder.jp 概要 '.'と'#'からなるグリッドが与えられる。 以下のルールの元で出来るだけ多くの'.'を選択する時、選んだ'.'の個数を出力する。 隣り合う'.'の両方を選ぶことはできない 解法 まずグリッドをグラフとみなすと、二部グラフの最大独立集…

全完やったああああ！（初めてかもしれない） AGCも頑張るぞおおお（白目） 問題 beta.atcoder.jp 多次元バーガーは以下のようなものです。 レベル0バーガーとは、パティ1枚である。 レベルバーガーとは、バン1枚、レベルバーガー、パティ1枚、レベルバーガ…

問題 beta.atcoder.jp 解法 ある人とある人の間に辺が貼ってあるか、ある人とある人が連結であることがわかればよい。ここで、UnionFindを使いたい気持ちになるので、どうにか使えないか考える。ここでは、問題の入力例1を元に考えることにする。 この図を縦…

備忘録。 解説AC 問題 beta.atcoder.jp 考察 マンハッタン距離が等しい点をとると、菱形のような形になる。これは解説の図がわかりやすい(12ページ)。https://www.slideshare.net/chokudai/arc047-57126901 arc047 from AtCoder Inc. www.slideshare.net 問…

備忘録です。 問題文 C - 嘘つきな天使たち 解法 二部グラフかどうかを判定すれば良い。 次の性質を用いることができる。 二部グラフ奇数長の閉路を部分グラフとして持たない 証明はここ。 #include <bits/stdc++.h> #define rep(i,a,b) for(int i=a;i<(b);++i) #define ere</bits/stdc++.h>…

問題文 C - 積み重ね 解法 Greedy. 重ねられるところまで重ねてあげて、無理だったら地面（？）に置く。できるだけ重ねてあげれば山の個数を最小にできる。 #include <bits/stdc++.h> #define rep(i,a,b) for(int i=a;i<(b);++i) #define erep(i,a,b) for(int i=a;i<=(int)(</bits/stdc++.h>…