閘門式運河: 上下に動く水面
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問題難しそうだったから他のチームもこれ解いてるとばかり。。
とりあえず、間に合ってとても嬉しかった。
そういえば閘門ってカンモンだとばかり思ってそう言ってたけどコウモンだったらしい。
ムーンライト牧場
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)」
最初の正答だったっぽい。やった！
ACM/ICPC模擬戦
なんだかんだで今年も出るよー！今年はチームImoで参戦。
今日はOB/OGの会の模擬国内予選で、4位でした！
結果はhttp://acm-icpc.aitea.net/index.php?2010%2FPractice%2F%CC%CF%B5%BC%B9%F1%C6%E2%CD%BD%C1%AA%2F%BD%E7%B0%CCに。
俺はB問題とF問題を解いた。
本番もこれぐらい調子よかったらいいなー。
Marathon Match 58参加記
http://topcoder.g.hatena.ne.jp/hasi_t/20100416/1271405387
TopCoder部に書いた。だらだらしてる間にMarathon Match 59が始まっちゃったよ＞＜
チンイツの待ちを出力するプログラム
あなたのスキルで飯は食えるか？ 史上最大のコーディングスキル判定 (1/2) - ITmedia エンタープライズ
麻雀の待ち判定って一回作りたいとは思ってたけど、まだ作ったことなかったなー。
というわけで良い機会だし楽しそうなので挑戦してみました。…これで合ってるのかな。
#include <iostream> #include <vector> #include <string> #include <algorithm> using namespace std; string anko(int n) { char buf[] = "(111)"; buf[1] += n; buf[2] += n; buf[3] += n; return string(buf); } string shun(int n) { char buf[] = "(111)"; buf[1] += n; buf[2] += n+1; buf[3] += n+2; return string(buf); } string atama(int n) { char buf[] = "(11)"; buf[1] += n; buf[2] += n; return string(buf); } string ryan(int n) { char buf[] = "[11]"; buf[1] += n; buf[2] += n+1; return string(buf); } string kan(int n) { char buf[] = "[11]"; buf[1] += n; buf[2] += n+2; return string(buf); } string shabo(int n) { char buf[] = "[11]"; buf[1] += n; buf[2] += n; return string(buf); } string tanki(int n) { char buf[] = "[1]"; buf[1] += n; return string(buf); } void piyo(const vector<int>& a, string s) { //りゃんめん・ぺんちゃん for (int i = 0; i < 8; ++ i) { if (a[i] && a[i+1]) { cout << s << ryan(i) << endl; } } //かんちゃん for (int i = 0; i < 7; ++ i) { if (a[i] && a[i+2]) { cout << s << kan(i) << endl; } } //しゃぼ for (int i = 0; i < 9; ++ i) { if (a[i]>=2) { cout << s << shabo(i) << endl; } } } void fuga(const vector<int>& a, string s) { //単騎 for (int i = 0; i < 9; ++ i) { if (a[i]) { cout << s << tanki(i) << endl; } } } void hoge(const vector<int>& a, int p, int men, string s) { if (men < 3) { // とりあえず適当に3面子作る //あんこ for (int i = p; i < 9; ++ i) { if (a[i]>=3) { vector<int> b = a; b[i] -= 3; hoge(b, i, men+1, s+anko(i)); } } //しゅんつ for (int i = max(0,p-9); i <= 6; ++ i) { if (a[i] && a[i+1] && a[i+2]) { vector<int> b = a; -- b[i]; -- b[i+1]; -- b[i+2]; hoge(b, i+9, men+1, s+shun(i)); } } } else { //単騎以外 for (int i = 0; i < 9; ++ i) { if (a[i] >= 2) { vector<int> b = a; b[i] -= 2; piyo(b, s+atama(i)); } } //あんこ for (int i = p; i < 9; ++ i) { if (a[i]>=3) { vector<int> b = a; b[i] -= 3; fuga(b, s+anko(i)); } } //しゅんつ for (int i = max(0,p-9); i <= 6; ++ i) { if (a[i] && a[i+1] && a[i+2]) { vector<int> b = a; -- b[i]; -- b[i+1]; -- b[i+2]; fuga(b, s+shun(i)); } } } } void func(string s) { vector<int> a(9,0); for (int i = 0; i < 13; ++ i) { ++ a[ s[i]-'1' ]; } hoge(a, 0, 0, ""); } int main() { string buf; while (getline(cin,buf)) { cout << buf <<endl; func(buf); } }
実行結果：
1112224588899 (111)(222)(888)(99)[45] 1122335556799 (555)(123)(123)(99)[67] (123)(123)(567)(55)[99] (123)(123)(567)(99)[55] 1112223335559 (111)(222)(333)(555)[9] (555)(123)(123)(123)[9] 1223344888999 (888)(999)(123)(44)[23] (888)(999)(123)(234)[4] (888)(999)(234)(234)[1] 1112345678999 (111)(999)(234)(567)[8] (111)(999)(234)(678)[5] (111)(999)(345)(678)[2] (111)(234)(567)(99)[89] (111)(234)(789)(99)[56] (111)(456)(789)(99)[23] (999)(123)(456)(11)[78] (999)(123)(678)(11)[45] (999)(345)(678)(11)[12] (123)(456)(789)(11)[99] (123)(456)(789)(99)[11]
時間：1時間弱
人材獲得作戦の試験問題
http://okajima.air-nifty.com/b/2010/01/post-abc6.html
なんか流行ってるからやってみた。ただの幅優先探索。30分弱。vectorにするのさぼって配列使うために適当に100x100以下と仮定。
#include <iostream> #include <vector> #include <string> #include <queue> using namespace std; class Maze { vector<string> maze; int W; int H; bool visited[100][100]; int prev[100][100][2]; public: pair<int,int> findStart() { for (int y = 0; y < H; ++ y) { for (int x = 0; x < W; ++ x) { if (maze[y][x] == 'S') return make_pair(x, y); } } throw 1; } pair<int,int> func() { queue< pair<int,int> > Q; pair<int,int> start = findStart(); Q.push(start); visited[start.second][start.first] = true; memset(visited, 0, sizeof(visited)); memset(prev, -1, sizeof(prev)); int dx[4] = {+1,-1, 0, 0}; int dy[4] = { 0, 0,+1,-1}; while (!Q.empty()) { pair<int,int> p = Q.front(); Q.pop(); for (int i = 0; i < 4; ++ i) { int x = p.first+dx[i]; int y = p.second+dy[i]; if (!visited[y][x] && maze[y][x] != '*') { prev[y][x][0] = p.first; prev[y][x][1] = p.second; if (maze[y][x] == 'G') { return make_pair(x, y); } else { Q.push(make_pair(x, y)); visited[y][x] = true; } } } } throw 1; } vector<string> solve(const vector<string>& m) { maze = m; W = (int)maze[0].length(); H = (int)maze.size(); pair<int,int> p = func(); for (;;) { p = make_pair(prev[p.second][p.first][0], prev[p.second][p.first][1]); if (maze[p.second][p.first] != ' ') break; maze[p.second][p.first] = '$'; } return maze; } }; int main() { char buf[1000]; vector<string> hoge; while (cin.getline(buf, sizeof(buf))) { hoge.push_back(buf); } static Maze m; vector<string> r = m.solve(hoge); for (int i = 0; i < (int)r.size(); ++ i) { cout << r[i] << endl; } }
あけましておめでとうございます
今年もよろしくお願いしますー
