hos’ Xmas Contest 2010

ああ完全に負けたわ。昼の部に参加しました。

A: Christmas Trees

問題開く。サンプル図を見る。余りの取り方にかなり悩んだ挙句とりあえず書く→60%

っかしいな・・・何か見落としてるんじゃないか?(気づかないまま時間経過)

夜のコンテスト終わった後に c=d のケースだと距離0がありえないことに気づいた。orz

100%もらえるソース。

ll labs(ll a){return a<0?-a:a;}	

pair<ll,ll> solve(ll a , ll b , ll L){
	//cout << L << " {" << endl;
	ll maxRet = 0 , minRet = (1ll<<60);
	ll c = a+b;
	ll s1 = (L/c)*2+1;
	if(L%c >= a || L%c >= b){
		if(L%c >= a ^ L%c >= b){
			maxRet = max(maxRet , s1);
			minRet = min(minRet , s1-1);
		}
		s1++;
	}
	maxRet = max(maxRet , s1);
	minRet = min(minRet , s1-1);
	return make_pair(maxRet,minRet);
}
int main(){
	ll a,b,c,d;
	while(cin >> a >> b >> c >> d, a){
		ll mx = 0 , mi = (1ll<<60);
		pair<ll,ll> t = solve(a,b,labs(d+c) );
		mx = max(mx,t.first) , mi = min(mi,t.second);
		if(c != d){
			t = solve(a,b,labs(d-c) );
			mx = max(mx,t.first) , mi = min(mi,t.second);
		}
		cout << mi << " " << mx << endl;
	}
	
}

B: Simple Parsing

とりあえずAに時間掛けすぎたので読む。

足し算と引き算ならどういう順番でやっても、偶奇は変わんなくね?

→むしろ足し算と引き算って関係なくね。

→入力でかいのかー。それぞれの値の一桁目だけ見れば偶奇分かるくね?

書く。

無駄なものを消して足すだけのコード書く。

足す段階で偶奇とってもいいけどそれはしてない。

int main(){
	string get;
	while(getline(cin,get),get != "#"){
		rep(i,get.length()){
			if(!isdigit(get[i]))get[i] = ' ';
		}
		int ret = 0;
		stringstream ss(get);
		string s;
		while(ss >> s){
			ret += (s[s.length()-1]-'0');
		}

		cout << (ret%2?"ODD":"EVEN") << endl;
	}
}	

C: Connect The Decoration

完全に勘違いしたまま最小シュタイナー木だと思って解いて、とりあえず部分点だけもらう解法した。

1の時要らなくて、0の時要るのね。そこだけ気づいて修正して提出したので中途半端な問題把握のせいで効率的な解法が思いつかなかった。

まあ正しい解法でも、高速な全域最小木じゃないとTLEするっぽい。

本番で、ソースはspaghetti sourceから拾った最小シュタイナー木しか提出していない。

その後に書いたソース。spaghetti sourceのprim木を拝借。

現在の最小を越えたらreturnすることでやや枝刈 + 最初に全部枝を刈るところからはじめる。

でやっと最大ケースが1800msくらいでAcceptした。

typedef int Weight;
struct Edge {
  int src, dst;
  Weight weight;
  Edge(int src, int dst, Weight weight) :
    src(src), dst(dst), weight(weight) { }
};
bool operator < (const Edge &e, const Edge &f) {
  return e.weight != f.weight ? e.weight > f.weight : // !!INVERSE!!
    e.src != f.src ? e.src < f.src : e.dst < f.dst;
}
typedef vector<Edge> Edges;
typedef vector<Edges> Graph;

typedef vector<Weight> Array;
typedef vector<Array> Matrix;

#define REP(i,n) for(int i=0;i<(int)n;++i)
#define FOR(i,c) for(__typeof((c).begin())i=(c).begin();i!=(c).end();++i)
#define ALL(c) (c).begin(), (c).end()

int ret;

int minimumSpanningTree(const Graph &g, vector<int> &t) {
  int n = g.size();
  Weight total = 0;
  vector<bool> visited(n);
  int r = -1;
  rep(i,t.size())visited[t[i]] = true;
  rep(i,n)if(!visited[i]){r=i;break;}
  
  priority_queue<Edge> Q;
  Q.push( Edge(-1, r, 0) );
  while (!Q.empty()) {
    Edge e = Q.top(); Q.pop();
    if (visited[e.dst]) continue;
    total += e.weight;
    if(total >= ret)return INT_MAX;
    visited[e.dst] = true;
    FOR(f, g[e.dst]) if (!visited[f->dst]) Q.push(*f);
  }
	rep(i,n)if(!visited[i])return INT_MAX;
	return total;
}


int main(){
	int n,m;
	while(cin >> n >> m, n){
		vector<int> T;
		ret = INT_MAX;
		Graph table(n);
		rep(i,n){
			bool t; cin >> t;
			if(t)T.push_back(i);
		}
		
		rep(i,m){
			int a,b,c;
			cin >> a >> b >> c;
			a--,b--;
			table[a].push_back(Edge(a, b, c));
			table[b].push_back(Edge(b, a, c));
		}
		for(int bit = (1<<T.size())-1 ; bit >=0 ; bit--){
			vector<int> t;
			rep(j,T.size())	if(bit & (1<<j))t.push_back(T[j]);
			ret = min( ret , minimumSpanningTree(table,t) );
		}
		cout << ret << endl;
	}
}

D

DPっぽいけど思いつかなかった。

E

マジキチ

F

問題がよく分からなかった。

G

数列だけど、よく分からなかった。

多分大体のケースで0で、一部0じゃない時があったりするのかな?(適当な判断)

みたいな感じで見てたけど思いつかないのでやめました。

すべてのケースに対して0で提出するっていう欲が出るけど、それでWAさせるのを狙っているだろうなので未提出。

H

何だこの問題!?これがクリスマスプレゼントか。

入力の終わりを見たらAとGとD以外は判別できそう。

Dについては、2行目が3コかどうかで判定。

あとは、AとGの入力をどう判定するか。

最初Aかどうかの判定を入力ひとつ目にしか適用してなくて、

そのせいで部分点しかもらえなかった。

正直これが、

「どのテストケースにも当てはまらない場合は～」とか、

各問題の入力が「入力は0コ以上とします。」みたいな感じだったら、

難易度が異常に上がってた気がする。後者はそんなでもないけど前者はヤバイ。

vector<int> check(string line){
    stringstream ss(line);
    vector<int> ret; int tmp;
    while(ss >> tmp)ret.push_back(tmp);
    return ret;
}

string checker(vector<string> data){
    if(data.back() == "#")return "B";
    if(data.back() == "0 0")return "C";
    if(data.back() == "0")return "E";
    if(data.back() == "0 0 0")return "F";    
    if(data.size()>=2)if(check(data[0]).size() == 4 && check(data[1]).size() == 3)return "D";
    
    int a,b,c,d;
	rep(i,(int)data.size()-1){
		vector<int> da = check(data[i]);
		a = da[0] , b = da[1] , c = da[2] , d = da[3];
		if(a > 100000 || b > 100000 || c > a || d > a)return "A";
	}
    if(data.size() > 21)return "A";
    else return "?";
}
int main(){
    string line;
    while(1){
        vector<string> data;
        while(getline(cin,line)){
            if (line[line.size()-1] == '\n') line.erase(line.size()-1);
            if (line[line.size()-1] == '\r') line.erase(line.size()-1);
            if(line == "@@@@@@@@@@")break;
            if(line == "@@@@@@@@@@@@@@@@@@@@")return 0;
            //cout << line << endl;
            data.push_back(line);
        }
        cout << checker(data) << endl;
    }
}

結果

ペナ出しすぎた。 300点/1070分

A 60.0 / B 100.0 / C 40.0 / D 0.0 / E 0.0 / F 0.0 / G 0.0 / H 100.0

43位/95人くらい。悔しい。