kmjp's blog

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

Codeforces #377 Div2 C. Sanatorium

割といい成績でした。
http://codeforces.com/contest/732/problem/C

問題

あなたは何日か観光地で過ごし、朝食・昼食・夕飯をA,B,C回ずつ食べた。
観光地を出入りするタイミングは、日の境目とは限らない。
あなたは何回か食事を食べ逃した可能性がある。
最小何回食べ逃した可能性があるか求めよ。

解法

出入りのタイミングによって、朝食・昼食・夕飯の食事回数が1回ずれる可能性がある。
ずれ方を2^3通り総当たりし、それぞれ条件を満たす最小滞在日数を求め、そこから食べ逃した回数を求めればよい。

ll A,B,C;

ll dodo(ll a,ll b,ll c) {
	ll d=max(0LL,max(A-a,max(B-b,C-c)));
	return (d+a-A)+(d+b-B)+(d+c-C);
}

void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>A>>B>>C;
	ll mi=1LL<<62;
	FOR(i,8) mi=min(mi,dodo(i/4,i/2%2,i%2));
	cout<<mi<<endl;
}

まとめ

今回と前回は実装軽めだね。