torus711 のアレ

主に競技プログラミングの問題について書きます

AtCoder Beginner Contest 187, F : Close Group

問題概要

 $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$ は相異なる
続きを読む