yukicoder : No.91 赤、緑、青の石、No.92 逃走経路

92はちょっと実装に手間取った。
http://yukicoder.me/problems/200
http://yukicoder.me/problems/149

No.91 赤、緑、青の石

赤・緑・青の石を１個ずつ集めると１個アクセサリができる。
また、同じ色の石２個から他の色の石を１個生成できる。
３色の石の数が与えられるので、作れる最大アクセサリ数を求めよ。

先にアクセサリ数を決める。
各色における(余剰分/2)の和が、不足分の和以上であればその分のアクセサリが作れる。
あとは線形探索か二分探索で作れる数の最大値を求めればよい。以下は二分探索解。

ll V[3];

bool ok(ll v) {
	ll left=0;
	ll hu=0;
	if(V[0]>=v) left+=(V[0]-v)/2;
	if(V[1]>=v) left+=(V[1]-v)/2;
	if(V[2]>=v) left+=(V[2]-v)/2;
	if(V[0]<v) hu+=v-V[0];
	if(V[1]<v) hu+=v-V[1];
	if(V[2]<v) hu+=v-V[2];
	return left>=hu;
}

void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>V[0]>>V[1]>>V[2];
	
	ll ret=0;
	for(i=40;i>=0;i--) if(ok(ret+(1LL<<i))) ret+=1LL<<i;
	cout<<ret<<endl;
	
}

No.92 逃走経路

N個の町とそれを双方向につなぐM個の道路が与えられる。
また、各道路の移動には料金C[i]がかかる。
最近通ったK本の道路の料金履歴D[i]が与えられる。
現在いる可能性のある町を列挙せよ。

初期状態でN個すべての町にいる可能性があるとする。
後はi回目の移動でC[x]==D[i]となる道路を通るとして、存在する可能性のある町の集合を順次求めていけば良い。
O(M*K)かかるが、MもKも大きくないので十分間に合う。

int N,M,K;
int A[1001],B[1001];
vector<pair<int,int> > E[101];
ll C[1001],D[1001];
int vis[2][101];

void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>N>>M>>K;
	FOR(i,M) {
		cin>>x>>y>>j;
		E[x-1].push_back(make_pair(j,y-1));
		E[y-1].push_back(make_pair(j,x-1));
	}
	
	FOR(i,N) vis[0][i]=1;
	
	FOR(i,K) {
		int cur=i%2,tar=cur^1;
		cin>>D[i];
		ZERO(vis[tar]);
		FOR(x,N) if(vis[cur][x]) {
			FOR(y,E[x].size()) if(E[x][y].first==D[i]) vis[tar][E[x][y].second]=1;
		}
	}
	x=0;
	FOR(i,N) if(vis[K%2][i]) x++;
	_P("%d\n",x);
	FOR(i,N) if(vis[K%2][i]) {
		_P("%d",i+1);
		if(--x) _P(" ");
		else _P("\n");
	}
}

まとめ

No.092は最初0番の町にいるものと無用な前提を置いてしまい、タイムロスした。