AGC030

A - Poisonous Cookies (200)

A - Poisonous Cookies

概要

解毒剤入りの美味しくないクッキーが枚、解毒剤入りの美味しいクッキーが、毒入りの美味しいクッキーが枚ある。
毒入りクッキーを２枚連続で食べないという条件のもと、最大何枚の美味しいクッキーを食べることができるか。

制約

方針

毒入りクッキーを食べた後、解毒剤入りクッキーを食べることを繰り返す。
解毒剤が足りなくなった場合でも、最後の1つとして毒入りクッキーを食べることができる。

感想

入力例2のサンプルでだいぶ助かった。
高橋君がお腹の調子を壊して終わるケース、かわいそう。

解答

Submission #3898066 - AtCoder Grand Contest 030

#include <bits/stdc++.h>
 
#define FOR(i,a,b) for(int i=(a);i<(b);i++)
#define rep(i,n) FOR(i,0,n)
#define RFOR(i,a,b) for(int i=(a)-1;i>=(b);i--)
#define rrep(i,n) RFOR(i,n,0)
 
using namespace std;
 
typedef long long ll;
typedef unsigned long long ull;
 
int main()
{
	cin.tie(0);
	ios::sync_with_stdio(false);
 
	ll a, b, c;
	cin >> a >> b >> c;
 
	ll ans = min(c, a);
	c -= min(c, a);
 
	ans += 2 * min(b, c);
	ll t = min(b, c);
	b -= t;
	c -= t;
	ans += b;
	if(c > 0) ans++;
 
	cout << ans << endl;
}

B - Tree Burning (800、部分点300)

B - Tree Burning

概要

長さの円周上に木が本生えており、木は円周上の原点からの位置に生えている。
この木をすべて燃やすことを考える。円周上の原点から以下の行動を繰り返す。

• すべての木を燃やし終えている場合、終了する。
• 時計回りまたは反時計回りの向きを指定する。
• 初めてまだ燃やしていない木のある座標に到達するまで、指定した方向に高橋湖の周上を歩き続ける。
• 木のある座標に到達したら、その木を燃やしてその場に立ち止まり、最初に戻る。

全ての燃やし方のうち、最大の移動距離を求めよ。

制約

• （部分点300の制約）

方針（部分点）

ある点まで１方向に進んで燃やし続けた後は、
向きを変えながら燃やし続ける。

どの点まで燃やすか、また最初を時計回りで始めるかを決めて
それぞれシミュレーションする。

感想

証明はできていなかったので証明する。
満点解法はシミュレーション部分をにするらしい。

解答

Submission #3898123 - AtCoder Grand Contest 030

#include <bits/stdc++.h>
 
#define FOR(i,a,b) for(int i=(a);i<(b);i++)
#define rep(i,n) FOR(i,0,n)
#define RFOR(i,a,b) for(int i=(a)-1;i>=(b);i--)
#define rrep(i,n) RFOR(i,n,0)
 
using namespace std;
 
typedef long long ll;
typedef unsigned long long ull;
 
const ll max_n = 2005;
ll l, n;
ll x[max_n];
 
ll sim(ll y, bool clock){
	// cout << "sim:" << y << " " << clock << endl;
	ll lp = 0;
	ll rp = n+1;
 
	ll ret = 0;
	if(clock){
		lp += y;
		ret += x[lp];
	}else{
		rp -= y;
		ret += l - x[rp];
	}
 
	// cout << lp << " " << rp << " " << ret << endl;
	while(rp > lp + 1){
		if(clock){
			rp--;
		}else{
			lp++;
		}
		ret += x[lp] + l - x[rp];
		clock = !clock;
 
		// cout << lp << " " << rp << " " << ret << endl;
	}
 
	return ret;
}
 
int main()
{
	cin.tie(0);
	ios::sync_with_stdio(false);
 
	cin >> l >> n;
	x[0] = 0;
	rep(i, n) cin >> x[i+1];
	x[n+1] = l;
 
	ll ans = 0;
	rep(i, n){
		ans = max(ans, sim(i+1, true));
		ans = max(ans, sim(i+1, false));
	}
 
	cout << ans << endl;
}