Codeforces Beta Round #29 (Div. 2, Codeforces format)

英語読解力が無い+コーディング能力がないということが証明されました。

A.Spit Problem

ラクダが唾吐きまくる。一直線上にラクダは並んでいて、自分の地点からちょうどdメートルの距離の地点に唾を飛ばせる。お互いに唾掛け合えるような組は存在するか。

ラクダって気持ち悪いな・・・と思った問題。最初英語読めなくて、「みんな唾はきまくるけど、全員に唾が掛かるかどうか」とか解釈してコーディングしてて色々混乱してた。

C問題で撃沈した後にもっかい英文読んで理解してコーディング。Accept.01:17提出とかいう意味分からん感じなので点数はクソ低い。

―346 Pt.

#include <iostream>
#include <vector>
using namespace std;
#define X(i) data[i].first
#define D(i) data[i].second
#define rep(i,n) for(int i=0;i<n;i++)

int main(){
	int n,x,d,flag;
	vector< pair<int,int> > data;
	cin >> n;
	rep(i,n){
		cin >> x >> d;
		data.push_back(make_pair(x,d));
	}
	
	flag = false;
	rep(i,n)rep(j,n){
		if(X(j)+D(j)==X(i) && X(i)+D(i)==X(j))
			flag = true;
	}
	cout << (flag?"YES":"NO") << endl;	
}

B.Traffic Lights

信号が赤と緑に切り替わるタイミングが与えられる。

交通ルールに則ったらどれくらい早く目的地点に着けるか。

Bを読んだのが終了15分前で、結構こういう問題数学でも苦手なので頭がパンクして撃沈。

ちなみに二回WA出した。

C.Mail Stamps

なんか経路出力問題。なんでもいいからルート一つ出力する。

とりあえず幅優先だなと思って書いてTLE。その後バックトラックで書いてTLE。入力がでかいから別の解法があるのかなあと思って必死に考えてかなり時間を無駄にした。

結局コンテスト後、知り合いに端は一回しか出ないからそれを始点にすればいいよと教えられ、やってみたら普通に間に合った。うわーーーーーーーー。読解力と気づきが欲しい。

#include <vector>
#include <map>
#include <iostream>
#include <algorithm>
using namespace std;
#define rep(i,n) for(int i=0;i<n;i++)

vector<int> now;
map<int,bool> done;
map<int,vector<int> > info;
int s,g;
int n;

void bt(int pos){
	if(now.size()==n){
		cout << s << " ";
		rep(i,now.size()){
			if(i)cout << " ";
			cout << now[i];
		}
		cout << endl;
		exit(0);
	}
	rep(i,info[pos].size()){
		if(done[info[pos][i]])continue;
		done[info[pos][i]] = true;
		now.push_back(info[pos][i]);

		bt(info[pos][i]);
		
		now.pop_back();
		done[info[pos][i]] = false;
	}
}
int main(){
	cin >> n;
	int a,b;
	map<int,int> freq;
	rep(i,n){
		cin >> a >> b;
		info[a].push_back(b);
		info[b].push_back(a);
		freq[a]++;freq[b]++;
	}
	map<int,int>::iterator it = freq.begin();
	while( it != freq.end() ){
		if((*it).second==1){
			s=(*it).first;
		}
		++it;
	}
	bt(s);
}

D,Eは見てません。