ICPC 国内予選 2015 参加記
こんばんは, kagamiz です。
今日は @tanishi345 と @orisano と一緒に ICPC の国内予選に参加しました。
まだ確定した順位ではありませんが, ABCD の 4 問を解いて全体の順位は 22 位でした。
4 問のうち, C と D が僕の担当でした。
去年やらかした件もあって今年も心配でしたが, 無事通過できていそうで良かったです。 筑波でお会いできる方はよろしくお願いします。
以下, 解いた問題の感想や, 良かった点と反省などです。
感想
- A 問題
後輩が解いていた。 めちゃくちゃ Better-C なコードだ。。。(std::max 使ってくれ〜)
#include <cstdio> using namespace std; int a[1000000]; int max(int a, int b) { if (a < b){ return (b); } return (a); } int main() { int m, nmin, nmax; while (scanf("%d %d %d", &m, &nmin, &nmax), m){ for (int i = 0; i < m; i++){ scanf("%d", &a[i]); } int maxi = 0; int ans = -1; for (int n = nmin; n <= nmax; n++){ if (maxi <= a[n - 1] - a[n]){ ans = n; maxi = a[n - 1] - a[n]; } } printf("%d\n", ans); } return (0); }
- B 問題
先輩が爆速で解いた。スッキリしていていいと思った(こなみ)。
#include <string> #include <iostream> #include <vector> #include <cstdio> using namespace std; const int INF = (1 << 28); bool is_valid(const vector<string>& W, int l, int r){ int task[] = {5, 7, 5, 7, 7, INF}; int tid = 0; for (int i = l; i < r; i++){ task[tid] -= W[i].size(); if (task[tid] == 0){ tid++; } else if (task[tid] < 0){ return false; } } return tid == 5 && task[5] == INF; } int main() { int N; while (cin >> N, N){ vector<string> W; for (int i = 0; i < N; i++){ string w; cin >> w; W.push_back(w); } for (int x = 0; x < N; x++){ for (int y = N; y > x; y--){ if (is_valid(W, x, y)){ printf("%d\n", x + 1); goto END; } } } END:; } return 0; }
- C 問題
後輩が A 問題を解いている間に問題文を斜め読みして, 大体題意をつかむ。
再帰をして実装したほうが綺麗に書けそうだと思ったが, 再帰による実装が思いつかなかったため, (演算子/値の深さ, 演算子/数) という2つの状態を pair で持ち, 深いところからマージしていくという実装を行って解いた。 他の人のものより実装が長いが, 再帰で書かなかったトレードオフ(?)かな。
#include <string> #include <iostream> #include <vector> #include <cstdio> #include <algorithm> typedef __int64 Int; using namespace std; int main() { int n; while (scanf("%d", &n) && n){ char s[128][1024]; vector< pair<int, Int> > v; for (int i = 0; i < n; i++){ scanf("%s", s[i]); int len = strlen(s[i]); if (s[i][len - 1] == '+'){ v.push_back(make_pair(len, -1)); } else if (s[i][len - 1] == '*'){ v.push_back(make_pair(len, -2)); } else { v.push_back(make_pair(len - 1, s[i][len - 1] - '0')); } } for (int i = 20; i >= 1; i--){ vector< pair<int, Int> > nv; for (int j = 0; j < v.size();){ if (v[j].first != i) nv.push_back(v[j++]); else { if (v[j].second == -1){ j++; Int tmp = 0; while (v[j].first == i && v[j].second >= 0 && j < v.size()){ tmp += v[j].second; j++; } nv.push_back(make_pair(i - 1, tmp)); } else { j++; Int tmp = 1; while (v[j].first == i && v[j].second >= 0 && j < v.size()){ tmp *= v[j].second; j++; } nv.push_back(make_pair(i - 1, tmp)); } } } v = nv; } printf("%I64d\n", v[0].second); } return (0); }
- D 問題
3 人で話をしていく中で DP をするとよさそうという案があがる。
考察の中で,
1. 500 円未満のお釣りの硬貨の種類には意味があまりない(500 円未満の硬貨の額の総和が 500 を超えるのであれば, そのなかから 500 円を作り出せるから)
2. お釣りから 500 円を生成する遷移は大量にあるが, お釣りが少なくなって嬉しい事は何ら無いので, それらのうち必要な金額が最も小さいものを取る
ということがわかった。
最初は DP[何番目の店][お釣りの総和] = 500 円の枚数の最大値, という DP をしようするが, 金額の復元ができずに破綻。
代わりに, DP[何番目の店][お釣りの総和] = pair{500 円の枚数の最大値, 値段の最小値} という DP をすれば復元に悩む必要がないということに気づき, 実装し AC。
書いたコードが短かったのと, D を書き終えた時点で残り 30 分強しかなかったので, 今年も厳しいかな... と思っていたが, 思いの外 4 完が少なくて圏内に入ることができていた。 (競技中に順位表をみると精神がやられるので見ないことにしていた。)
#include <string> #include <iostream> #include <vector> #include <cstdio> #include <algorithm> typedef __int64 Int; typedef std::pair<int, int> P; using namespace std; const int INF = 1001001001; template<typename T> void maxe(T& a, T b){ a = max(a, b); } P dp[110][110 * 1000]; int main() { int n; while (scanf("%d", &n) && n){ for (int i = 0; i < 110; i++){ for (int j = 0; j < 110 * 1000; j++){ dp[i][j] = P(0, -INF); } } P ans; dp[0][0] = P(0, 0); for (int i = 0; i < n; i++){ int p; scanf("%d", &p); for (int j = 0; j < 110 * 1000; j++){ if (dp[i][j].second == -INF) continue; maxe(dp[i + 1][j], dp[i][j]); int x = (1000 - p % 1000) % 1000; if (j + x % 500 < 110 * 1000){ maxe(dp[i + 1][j + x % 500], P(dp[i][j].first + x / 500, dp[i][j].second - p)); } if (j >= 500 - x && j - 500 + x < 110 * 1000) maxe(dp[i + 1][j - 500 + x], P(dp[i][j].first + 1, dp[i][j].second - p)); } maxe(ans, *max_element(dp[i + 1], dp[i + 1] + 110 * 1000)); } printf("%d %d\n", ans.first, -ans.second); } return (0); }
チームでよかった点
- 必ず回答を提出する際に 1 人立ち会った
焦っても良いことはないので, 必ず回答提出は 2 人体制以上で行った。結果, 一度も提出ミス無しで 4 完できた。
- チームで話をする時間をもてた
これまではたいてい黙々とコーディングや思考を行う機会が多かったが, 議論形式で D 問題などを考えられたのが良かった。
反省点
- コーディングが突っ走り気味
まだ解法が固まっていない時点で D 問題などをコーディングしたせいで, 一度コードを書き直す羽目になった。 (具体的には, DP の結果を持つ配列を pair で持たないコードをそのまま消してしまって大きな時間ロスになった。)
これは去年もそうだったので, 今後も気をつけていきたい。
- 演習室の PC に gcc が入っていなかった(大事故)
爆速 gcc インストールバトル
— Jayson Sho Toma (@kagamiz) June 26, 2015今日のハプニング : 使う演習室の PC に gcc が入っておらず、ライブラリが破綻した(そんなにライブラリは使わなかったけど)
— Jayson Sho Toma (@kagamiz) June 26, 2015去年使っていた演習室がたまたま使えず, 別の演習室で予選に参加したが, 確認をしていなかったためにこういうことが起きてしまった。 環境をきちんと調べておかないと大変。。。 (結局 bcc をつかって頑張りました。)
まとめ
地区予選までに練習を重ね, 本番も頑張っていきたいと思います。
