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