kmjp's blog

競技プログラミング参加記です

技術室奥プログラミングコンテスト#4 Day1: K - 天使と宿題

考察が済めば実装は軽い問題。
https://atcoder.jp/contests/tkppc4-1/tasks/tkppc4_1_k

問題

N日分の宿題を他人から写すことを考える。
N日中、何回か友人宅を訪れたとする。
i日目に訪れた場合、友人からi日目含めi日目以前の宿題のうち、最大A[i]日分の宿題を写せる。

全部の宿題を写すのに、最大何日友人宅を訪れる必要があるか。

解法

P日目以前の宿題が手つかず、という状態からさかのぼって考えていこう。
初期状態でP=Nであり、Pが0以下になるまで以下を繰り返す。

P日目の宿題を行うには、P日目は必ず写させてもらわないといけない。
その際、過去A[P]日分は写すことができる。
よって、次の選択肢は(P-A[P]-1)日目~(P-1)日目のうち、もっとも写せる日数の多い日を選ぶ。
…ということを延々行う。

数値の集合のうち最大値を選ぶ処理を行うので、Priority Queueなど使おう。

int N;
int A[201010];

void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>N;
	FOR(i,N) cin>>A[i+1];
	int ret=0;
	priority_queue<int> PQ;
	int R=N;
	PQ.push(A[N]);
	
	while(R>0) {
		ret++;
		x=PQ.top();
		PQ.pop();
		if(x>=R) break;
		while(x--) PQ.push(A[--R]);
	}
	
	cout<<ret<<endl;
	
}

まとめ

天使が悪魔の宿題を写すのか…。