Same Integers [AtCoder Beginner Contest 093 C]

atcoder.jp

・長さ N 数列のうち，連続した K個の要素を選ぶ．その後，選んだ要素それぞれの値を，選んだ要素の中の最小値で置き換える．

という操作で与えられた数列の要素を全て等しくするとき、その値は "1" にしかなりません。なぜなら、仮に2に等しくしようと思って操作しても、必ずどこかの区間が1になってしまい、結局はそれに合わせて1に等しくしなければならないからです。

ということはつまり、この問題は、

・長さ N の数列から長さ K の区間を選び、その区間に 1 が含まれているなら、区間内の要素を全て 1 に置き換える。数列の全ての要素を 1 にするためには、この操作を何回おこなう必要があるか。

という問題に置き換えられます。こうなれば簡単です。

1回の操作につき、最大で K-1 の要素を 1 にすることができます。また、置き換えなければならない要素の総数は 1 を除いた N-1 個です。よって、答えは (K-1)*(N-1) を切り上げたものとなります。

import java.util.*;

class Main {
	static Scanner sc = new Scanner(System.in);
	public static void main(String[] args) {
		
		int n = sc.nextInt(), k = sc.nextInt();
		int[] ar = new int[n];
		for (int i=0; i<n; i++) ar[i] = sc.nextInt();
		
		System.out.println((int)Math.ceil((double)(n-1)/(double)(k-1)));
		
	}
}