問題概要
$N$ 頂点 $M $ 辺の単純無向グラフ $G = ( V, E )$ がある．このグラフをクリークで被覆するときの最小のクリーク数を求めよ*1．
制約
- $1 \leq N \leq 18$
- $0 \leq M \leq \frac{ N ( N - 1 ) } 2$
*1:原文と変わっていますが，結局，連結成分内の任意の 2 頂点が連結ならばその連結成分は元のグラフのクリークということになります
AtCoder Beginner Contest 186, D : Sum of difference
問題概要
$N$ 項からなる正整数列 $\{ A_i \}_{ i \in [ 0, N ) }$ が与えられる．$$\sum_{ i = 1 }^{ N - 1 } \sum_{ j = i + 1 }^N | A_i - A_j |$$ を求めよ．
制約
- $2 \leq N \leq 2 \times 10^5$
- $| A_i | \leq 10^8$
- $A_i \in \mathbb Z$
AtCoder Beginner Contest 186, E : Throne
問題概要
正整数 $N, S, K$ が与えられる．$S + xK \equiv 0 \pmod N$ となる最小の $x$ を求めよ．
$T$ ケース処理せよ．
制約
- $1 \leq T \leq 100$
- $2 \leq N \leq 10^9$
- $1 \leq S \leq N$
- $1 \leq K \leq 10^9$
AtCoder Beginner Contest 185, E : Sequence Matching
問題概要
長さ $N$ の正整数の列 $\{ A_i \}_{ i \in [ 0, N ) }$ と長さ $M $ の正整数の列 $\{ B_i \}_{ i \in [ 0, M ) }$ が与えられる．これらからいくつかの要素を取り除き（，残った要素を元々の順序を保ったまま連結することで），新たな列 $A', B'$ を作る．このとき，$| A' | = | B' |$ となるようにする（絶対値の記号で列の長さを表す）．
ある取り除き方について，
- 取り除いた要素一つあたりコスト $1$
- $A'_i \neq B'_i$ なる $i$ 一つあたりコスト $1$
がかかる．すべての取り除き方の内，コスト最小なもののコストはいくらか？
制約
- $1 \leq N, M \leq 1{,}000$
AtCoder Beginner Contest 185, D : Stamp
問題概要
$N$ 個のマスが一列に並んでいる．これらの $N$ 個のマスははじめ，白または青で塗られている．青色のマスは $M $ 個あり，それらの座標は数列 $A_i$ で与えられる（位置 $J$ について，$A_i = j$ なる $i$ が存在するとき，位置 $j$ のマスは青色である）．
この状況で，正整数 $k$ を一つ選び，幅 $k$ の判子を作る．判子を使うことで，連続する $k$ マスの色を赤に塗り替えることができる．ただし，このとき元々青色だったマスの色を塗り替えてはいけない．また、マス以外のものを塗ってもいけない（はみ出してはいけない）．
すべての白マスを赤マスに変えるとき，必要な判子の使用回数の最小値はいくらか？
制約
- $1 \leq N \leq 10^9$
- $0 \leq M \leq 2 \times 10^5$
- $1 \leq A_i \leq N$
- 各 $A_i$ は相異なる