日本情報オリンピック(JOI) 第11回予選 自分の提出した解答
kyuridenamida解と比較したので多分答えられた部分についてはあってる。
全体の感想としては、1-3は去年より一段ひねってあるというか、面倒な感じで、4は去年の4番のDPよりは少し難化していると思う。
5が去年の比でなく面倒だった。6はさっぱり分からなかった。6が解けている人が周囲にそれなりにいるので、そこは残念だが、4が解けてよかった。
問題1. ランチ (Lunch)
最も小さい物2つを選んで50を引くだけ。
#include <cstdio> #include <vector> #include <algorithm> using namespace std; vector<int> read(int n) { vector<int> v(n); for (int i = 0; i < n; ++i) scanf("%d\n", &v[i]); sort(v.begin(), v.end()); return v; } int main() { const vector<int> pasta = read(3); const vector<int> juice = read(2); const int res = pasta[0] + juice[0] - 50; printf("%d\n", res); return 0; }
問題2. サッカー (Soccer)
それぞれのチームの点数を計算して、順位をつけるだけ。
同じ点数のチームを同順にする、っていう操作がきれいに書けない。
ライブラリゲーとかのような気もしたがどうなんだろう。
#include <cstdio> #include <vector> #include <algorithm> using namespace std; int main() { int N; scanf("%d\n", &N); vector<int> scores(N, 0); for (int i = 0, l = N * (N - 1) / 2; i < l; ++i) { int A, B, C, D; scanf("%d %d %d %d\n", &A, &B, &C, &D); A--, B--; if (C > D) { scores[A] += 3; } else if (C < D) { scores[B] += 3; } else { scores[A]++; scores[B]++; } } vector<pair<int, int> > sorted(N); for (int i = 0; i < scores.size(); ++i) { sorted[i].first = scores[i]; sorted[i].second = i; } sort(sorted.rbegin(), sorted.rend()); vector<int> ranks(N); for (int i = 0; i < sorted.size(); ++i) { ranks[sorted[i].second] = i + 1; if (0 < i) { if (sorted[i - 1].first == sorted[i].first) { ranks[sorted[i].second] = ranks[sorted[i - 1].second]; } } } for (int i = 0; i < ranks.size(); ++i) { printf("%d\n", ranks[i]); } return 0; }
問題3. 最高のピザ (Best Pizza)
トッピングをして金額あたりのカロリーの最も高いピザを作る。トッピングの値段は全部同じなので、
トッピングを1個ものせない所からはじめて、カロリーの高い具から順にのっけていって、最大になる所で止める。
#include <cstdio> #include <vector> #include <algorithm> using namespace std; int main() { int N, A, B, C; scanf("%d\n%d %d\n%d\n", &N, &A, &B, &C); vector<int> D(N); for (int i = 0; i < N; ++i) { scanf("%d\n", &D[i]); } sort(D.rbegin(), D.rend()); int price = A, calorie = C; int res = calorie / price; for (int i = 0; i < N; ++i) { price += B; calorie += D[i]; int cur = calorie / price; if (res > cur) { break; } res = cur; } printf("%d\n", res); return 0; }
問題4. パスタ (Pasta)
見た瞬間多分DPだなと思ったけれども分からずに固まって、問題5にいった。
落ち着いて考えたら、
f(n, tomorrow、today) = 今日はtodayのソースのパスタを食い、昨日はtomorrowのソースのパスタを食った時のn日まで献立の組み合わせの数
という関数を再帰的に定義して、メモ化する事で解ける事に気付いた。
トップダウン式にコードが書けて満足している。というかはじめて本番でDP解けた。ので相当喜んでいる。
#include <cstdio> #include <vector> #include <climits> using namespace std; class Pasta { public: int N; vector<int> fixed; vector<vector<int> > dp; static const int MODULO = 10000; Pasta(int N) { this->N = N; fixed = vector<int>(N, INT_MAX); dp = vector<vector<int> >(N, vector<int>(1 << 4, INT_MAX)); return; } void set(int A, int B) { fixed[A - 1] = B - 1; return; } inline int f_impl(int n, int yesterday, int today) { if (fixed[n] != INT_MAX && fixed[n] != today) return 0; int res = 0; if (n == 1) { if (fixed[0] != INT_MAX && fixed[0] != yesterday) return 0; else return 1; } for (int i = 0; i < 3; ++i) { if (yesterday == today && i == today) continue; res = (res + f(n - 1, i, yesterday)) % MODULO; } return res; } int f(int n, int yesterday, int today) { int& cur = dp[n][(yesterday<<2) + today]; return (cur != INT_MAX ? cur : (cur = f_impl(n, yesterday, today))); } int start() { int res = 0; for (int i = 0; i < 3; ++i) for (int j = 0; j < 3; ++j) { res = (res + f(N - 1, i, j)) % MODULO; } return res; } }; int main() { int N, K; scanf("%d %d\n", &N, &K); Pasta pasta(N); for (int i = 0; i < K; ++i) { int A, B; scanf("%d %d\n", &A, &B); pasta.set(A, B); } const int res = pasta.start(); printf("%d\n", res); return 0; }
問題5. イルミネーション (Illumination)
ハニカム状の平面の問題。別にハニカムはライブラリゲーでもないと思うし、一度見た事があれば難しくないとは思うが、問題文の座標の振り方(の記述)が読みづらくて、結果的に2,30分ぐらい食ってしまった。
#include <cstdio> #include <vector> using namespace std; inline bool isValid(int x, int y, vector<vector<int> >& v) { return 0 <= x && x < v.size() && 0 <= y && y < v[0].size(); } int search (int x, int y, vector<vector<int> >& v) { const int dx[] = {1, (y % 2 ? 1: 0), (y % 2 ? 0 : -1), -1, (y % 2 ? 0: -1), (y % 2 ? 1 : 0)}, dy[] = {0, -1, -1, 0, 1, 1}; int res = 0; for (int i = 0; i < 6; ++i) { const int nx = x + dx[i], ny = y + dy[i]; if(!isValid(nx, ny, v)) continue; if (v[nx][ny] == 1) { res++; } else if (v[nx][ny] == 0) { v[nx][ny] = 2; res += search(nx, ny, v); } } return res; } int main() { int W, H; scanf("%d %d\n", &W, &H); vector<vector<int> > v(W + 2, vector<int>(H + 2, 0)); for (int i = 0; i < H; ++i) for (int j = 0; j < W; ++j) { scanf("%d", &v[j + 1][i + 1]); } const int res = search(0, 0, v); printf("%d\n", res); return 0; }
