ABC187F - Close Group
解答：Submission #19455050 - AtCoder Beginner Contest 187
解法：元のグラフをG = (V, E)とする。S ⊂ Vに対し、f(S)を誘導部分グラフ(S, Es)に対する元の問題の答えとすると、f(S)はSが完全グラフ（すべての頂点間に辺が張られたグラフ）であれば1、そうでなければmin{f(T) + f(S / T) | T ⊂ S}である。よってbitDPが適用できる。
計算量は要確認…。部分集合の遷移をO(3^N)でできないと間に合わないらしく、これはfor(int t = (s - 1) & s; t > 0; t = (t - 1) & s)のようなfor文で実現できる。
ABC188F - +1-1x2
解答：Submission #19454159 - AtCoder Beginner Contest 188
解法：解説どおりに逆から考える。下記が言える。
- 「+1, -1」、「-1, + 1」は意味がない
- 「+1,+1,/2」よりも「/2, +1」の方がお得
- 「-1,-1,/2」よりも「/2, -1」の方がお得
よって+1や-1の後は/2が来た方がお得である。ただし、+1や-1を続けてXに到達する場合もある。 これらを考慮し、メモ化再帰でシミュレーションするとよい。
ARC111 B - Reversible Cards
解答：Submission #19370578 - AtCoder Regular Contest 111
解法：解説通り、カードに書いてある数字を頂点、カードの数字の組み合わせを辺とするグラフを考えるのがミソ。すると問題は各辺のうち片方の頂点に色付けし、色のついた頂点の個数の最大値を求める問題になる。これは連結成分ごとに辺と頂点の個数の関係性を考えてゆくとよい。なお、グラフには多重辺（2枚以上の同じカード）や自己ループ（表と裏が同じ数字のカード）も含まれることに注意が必要。
各連結成分において辺の数が最も少ないのは連結成分が木である場合である。このときは頂点数をNとすると辺数はN-1になるので、色のついた頂点は最大N-1個である。これより辺が多い場合は全ての頂点の色付けが可能である。よって連結成分ごとに頂点の数と辺の数を比較して色付け可能な頂点数を答えに足し上げてゆけばよい。
AOJ Courses GRL_5_E Range Query on a Tree II
JOI 2018/2019 予選 D - 日本沈没 (Japan Sinks)
解答：Submission #19057982 - JOI 2018/2019 予選 過去問
解答：まずは初期状態の島の個数を数える。これは「i = 0かつa[i] > 0」もしくは「i > 0かつa[i-1] == 0かつa[i] > 0」の時にカウントアップすることで求まる。
その後は標高の低い土地から順番に水に浸すシミュレーションを行う。このとき両脇の土地がどちらも水に浸っていなければ島の数が1つ増え、両脇の土地がどちらも水に浸っていれば島の数が1つ減る。またそれ以外の状態での島の数の変動はない。
なお、標高が同じ土地のシミュレーションは同時に行わなくてはならないのは注意が必要である。
JOI 2019/2020 本選 B - JJOOII 2 (JJOOII 2)
解答：Submission #19057001 - JOI 2019/2020 本選 過去問
解法：まず、Oの選び方を考える。最初に用いるOを選んだとき、それ以降のOはそこからなるべく近くにあるOを選んでいったほうが良い。すると、使用するOが決まる。さらにJの選び方を考えるが、これは最初のOより左側のJでかつこれもなるべく近くにあるJを選んでいった方がよい。Iも同様である。よって、最初に用いるOを選ぶと、どのJ, O, Iを選ぶかが決まることになる。
あとは3の操作の回数を求める。使用するJ, O, Iの個数はそれぞれK個であることはあらかじめ決まっているので、「一番前のJ」「一番後のJ」「一番前のO」「一番後のO」「一番前のI」「一番後のI」のそれぞれの添字が分かれば計算で求めることが出来る。これらの添字管理は最初に用いるOを変えるに伴い動的に更新してゆけばよい。
JOI 2019/2020 本選 B - JJOOII 2 (JJOOII 2)
解答：Submission #19057001 - JOI 2019/2020 本選 過去問
解法：まず、Oの選び方を考える。最初に用いるOを選んだとき、それ以降のOはそこからなるべく近くにあるOを選んでいったほうが良い。すると、使用するOが決まる。さらにJの選び方を考えるが、これは最初のOより左側のJでかつこれもなるべく近くにあるJを選んでいった方がよい。Iも同様である。よって、最初に用いるOを選ぶと、どのJ, O, Iを選ぶかが決まることになる。
あとは3の操作の回数を求める。使用するJ, O, Iの個数はそれぞれK個であることはあらかじめ決まっているので、「一番前のJ」「一番後のJ」「一番前のO」「一番後のO」「一番前のI」「一番後のI」のそれぞれの添字が分かれば計算で求めることが出来る。これらの添字管理は最初に用いるOを変えるに伴い動的に更新してゆけばよい。
