Hatena::ブログ(Diary)

107143955443560

2011-08-06 (Sat)

KUPC 2011

KUPC(http://atcoder.jp/contest/17/detail)に参加しました。

後回しにすると何も書かないままになりそうなのでソースコードだけでも公開しておく。

A: http://ideone.com/ySY5b

B: http://ideone.com/Gx0Ds

C: http://ideone.com/3uxAs

D: http://ideone.com/5lZHq

G: http://ideone.com/q77S6

Gのローカルテスト: http://ideone.com/dmGWC

2011-06-17 (Fri)

2010-10-24 (Sun)

JAPLJ Contest

久しぶりの日記。ICPC国内予選で6位だったとか、JAG夏合宿行ったとか書いてなかった。。まあいいや。

JAPLJ Contest昼の部に参加。

夜の部と合わせた結果は http://judge.imoz.jp/page.php?page=view_stand&cid=9

12位でした!

JAPLJ Contest A: Anemone - 107143955443560

JAPLJ Contest B: Banksia - 107143955443560

JAPLJ Contest C: Cosmos - 107143955443560

JAPLJ Contest D: Dianthus - 107143955443560

2010-06-27 (Sun)

ACM/ICPC模擬戦

なんだかんだで今年も出るよー!今年はチームImoで参戦。

今日はOB/OGの会の模擬国内予選で、4位でした!

結果は有効なWikiNameではありません - ACM-ICPC Japanese Alumni Groupに。

俺はB問題とF問題を解いた。

本番もこれぐらい調子よかったらいいなー。

ムーンライト牧場

B問題。

なにこの入力めんどそう。。って最初は思ったけど、問題読んでみる。

ああ、アレですね。わかります。

まあpairをsortすればいいよね、ということで以下のコード書いて実行して提出して無事通った。

#include <iostream>
#include <sstream>
#include <vector>
#include <string>
#include <algorithm>
#include <set>
#include <map>
#include <queue>
#include <functional>
#include <numeric>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <cmath>
#include <iomanip>
using namespace std;
typedef long long ll;
#define fs first
#define sc second

int main() {
	for (;;) {
		int n;
		cin >> n;
		if(!n) break;
		vector< pair<double, string> > v;
		for (int i = 0; i < n; ++ i) {
			string name;
			int p,a,b,c,d,e,f,s,m;
			cin >> name >>p>>a>>b>>c>>d>>e>>f>>s>>m;
			double hoge = f*s*m - p;
			hoge /= a+b+c+m*(d+e);
			v.push_back(make_pair(-hoge,name));
		}
		sort(v.begin(), v.end());
		for (int i = 0; i < n; ++ i) {
			cout << v[i].second << endl;
		}
		cout << "#" << endl;
	}
}

実は誤差とかで危うげだったらしい。

そして講評読むと「最初の正答 : 17 mins (Imo)」

最初の正答だったっぽい。やった!

閘門式運河: 上下に動く水面

F問題。

C問題とD問題はほかの二人が頑張ってるのでE問題を読んでみる。…無理ぽ。

次にF問題を読む。シミュレーション…だよね?問題にもシミュレーションって書いてあるし。

考えることないような。。

えーと、priority_queueで動かしていけばいいのかな。いや、めんどくさすぎるー!間に合う気がしない!

とか言ってる間にCとDが解けてコーディング開始。

位置の配列用意して、キューにイベント入れていって、んで、えーっと。…あ、無理があるわ。

まあなんか、あとの二人がE問題頑張ってるのでがんばれーと思いつつ閘門の動きを考える。

あれ、よく考えたら1kmごとに到達時間考えればいいのかな…?っていうか先頭から順番に動かせばいいじゃないか。

適当に組んでみる。よくわからんけど違う。印刷して確認する。ああ、明らかにおかしい。

修正。なんか計算が足りてない。適当に2倍。とりあえずサンプル通ってるっぽい!

えーと、どうやって桁数変えるの?桁数変える。うん、合ってると思う!

データDLして実行。segmentation fault。適当に2000だったのを3000に書き換え。実行してとりあえず提出。通った!!



…という経緯でできたソースがこれです。時間かかったわりに、こんだけ?って感じではあるなあ。。

#include <iostream>
#include <sstream>
#include <vector>
#include <string>
#include <algorithm>
#include <set>
#include <map>
#include <queue>
#include <functional>
#include <numeric>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <cmath>
#include <iomanip>
using namespace std;
typedef long long ll;
#define fs first
#define sc second

int main() {
	for (;;) {
		int N, M, K;
		cin >> N >> M >> K;
		if (!N&&!M&&!K) break;
		vector<int> X(N), L(N), F(N), D(N), UD(N), V(M);
		for (int i = 0; i < N; ++ i) cin >> X[i] >> L[i] >> F[i] >> D[i] >> UD[i];
		for (int i = 0; i < M; ++ i) cin >> V[i];
		
		double kstart[3000], kt1[3000], kt2[3000];
		for (int i = 0; i < 3000; ++ i) kstart[i] = -1;
		for (int i = 0; i < N; ++ i) {
			int x = X[i] + M;
			if (UD[i] == 0) {
				kstart[x] = 0;
				kt1[x] = (double)L[i]/F[i];
				kt2[x] = (double)L[i]/D[i];
			} else {
				kstart[x] = (double)L[i]/F[i];
				kt1[x] = (double)L[i]/D[i];
				kt2[x] = (double)L[i]/F[i];
			}
		}
		
		double times[3000][100];
		for (int s = 0; s < M; ++ s) {
			double t = 0;
			for (int pos = M-s; pos <= M+K*2; ++ pos) {
				if (s > 0) t = max(t, times[pos+1][s-1]);
				times[pos][s] = t;
				if (kstart[pos] >= 0) {
					t = max(t, kstart[pos]);
					t += kt1[pos];
					kstart[pos] = t + kt2[pos];
				}
				t += 1.0/V[s];
			}
		}
		cout << setiosflags(ios::fixed) << setprecision(10) << times[K+M][M-1] << endl;
	}
}

この問題解いたのは3チームだけだったらしい。E問題難しそうだったから他のチームもこれ解いてるとばかり。。

とりあえず、間に合ってとても嬉しかった。

そういえば閘門ってカンモンだとばかり思ってそう言ってたけどコウモンだったらしい。

2010-04-16 (Fri)