AtCoder Beginner Contest 206（Sponsored by Panasonic）参加記（～D問題）

引退

A - Maxi-Buying

計算して $206$ と比較するだけ。なんか三項演算子の強化版で、「より小さい」「等しい」「より大きい」の3パターンそれぞれの値を返してくれる演算子か関数が欲しくなる。計算結果を整数値で持たないとダメ。計算量は $O(1)$ 。

B - Savings

公差 $1$ の等差数列の $k$ 項目までの和は $\dfrac{k^2 - k}{2}$ で求まる。これより解の最大値は $\sqrt N$ 程度と予測できるので、一日ずつシミュレーションしていくら溜まっているか確認していけばよい。計算量は $O(\sqrt N)$ 。

「ではない」の条件があるときはその条件を否定してみると数えやすくなることがある。 $i \lt j, A_i = A_j$ となるような $(i, j)$ の組を数えたい。配列 $A$ の中に整数 $x$ が $k$ 個ある場合、そのような組は $\dfrac{k^2 - k}{2}$ 組ある。これをすべての $x$ について数え上げ、全体の $(i, j)$ の組の個数から引けば答えが求まる。配列 $A$ の中に整数 $x$ が何個あるか数えるときはmapを使う。計算量は $O(N\log \max(A_i))$ 。

D - KAIBUNsyo

$(A_1, A_N), (A_2, A_{N-1}), \dots$ という $\dfrac{N}{2}$ 個の組を考える。それぞれの組について、二つの数のどちらかに統一しなければならないが、置き換え操作はすべての組に影響する。ある整数 $x$ が含まれるすべての組を同時に考える必要がある。
ここで、組の表現をグラフに落とす。各整数を頂点、置換する価値のある2整数の繋がりを辺とする。（これはつまり、各組に含まれる2整数をつないだものになる。）連結成分ごとに独立に考えて良い。一度の操作で隣接する2頂点を1つの大きな頂点にできる。この連結成分が回文の条件を満たすとき、辺が存在するなら自己ループしかありえない。連結成分が $k$ 個の頂点で構成されているなら、 $k-1$ 回操作を行って頂点を $1$ 個にするのが最適である。連結成分の頂点数はDFSで求められる。
これを各連結成分ごとに計算する。式を整理すれば、（頂点の個数）-（連結成分の個数）が答え。計算量は $O(N)$ 。