結果
C問題とD問題の2完。C問題で4WA出しながら45分以上かかって無茶苦茶焦ったけれど、なんとか落ち着きを取り戻してD問題まで通せたのは良かった。
C問題
最初は貪欲法とかでできるのかといろいろ考えていたけど、場合分けが難しすぎて断念。それぞれの入力値がそこまで大きくないので全探索で解けるだろうと判断したが、愚直な全探索ではまともに実行が終わらなかった。値を出力して観察すると、waterやsugarが同じものを何度も訪れているっぽいので訪問フラグを付けてみると高速になってACできた。
#include <bits/stdc++.h> #define REP(i,n) for (int i=0;i<(n);i++) #define RREP(i,n) for (int i=(n)-1;i>=0;i--) using namespace std; long long A, B, C, D, E, F; long long ans_water = 0, ans_sugar = 0; //0で初期化するとwater = 0がそのまま残り1つだけWAとなる double max_percentage = -1; bool visit[3001][3001]; void DFS(long long water, long long sugar) { //F以下でないとダメ if (water + sugar > F) return; //溶け残ったらダメ if (water / 100 * E < sugar) return; //訪問フラグを確認 if (visit[water][sugar]) return; //作った砂糖水の濃度 if (water != 0) { //0除算を避ける double tmp = 100.0 * sugar / (100.0 * water + sugar); if (tmp > max_percentage) { max_percentage = tmp; ans_water = water; ans_sugar = sugar; } } visit[water][sugar] = true; //操作1 DFS(water + 100 * A, sugar); //操作2 DFS(water + 100 * B, sugar); //操作3 DFS(water, sugar + C); //操作4 DFS(water, sugar + D); } int main() { cin >> A >> B >> C >> D >> E >> F; DFS(0, 0); cout << ans_water + ans_sugar << " " << ans_sugar << endl; }
D問題
問題の把握をしてNの大きさからいって3重ループは大丈夫だろうというところでワーシャルフロイド法が思い浮かんだ。
まず最初に与えられた2次元配列Aの和を保持しておいて、そこから要らないものを削除していけばいいだろうと発想。
元の2次元配列Aを3重ループで開始点、経由点、終端点と迂回する順と比較していって、より短いものがあったら最短としておかしいので-1を出力して終わり、等しかったら直接行く道は削除できるのでその分を和から引く、という方針でやったところ、半分くらいがACとなったので大まかな方針としてはあっているんじゃないかと思った。
サンプルは全部通ってしまうので残りのWAを取るためには自分で間違っているケースを考える必要があったが、最初に正方形のように辺が張っている状態を考えて
4
0 1 1 2
1 0 2 1
1 2 0 1
2 1 1 0
というのを試してみると答えが4になるべきところを0にしていて、まさにこれが残りの間違いだった。これはたとえば1から4へ行くルートは2を経由するのと3を経由するので2パターンあり、その2回の両方で直接ルート分を引いてしまっていたので答えがおかしくなっているということだった。よってあるノードからあるノードへの辺をすでに削除しているかを2次元配列で保持していくことでACとなった。
#include <bits/stdc++.h> #define REP(i,n) for (int i=0;i<(n);i++) #define RREP(i,n) for (int i=(n)-1;i>=0;i--) using namespace std; bool flag[301][301]; int main() { int N; cin >> N; vector<vector<long long> > A(N, vector<long long>(N, 0)); long long sum = 0; REP (i, N) { REP (j, N) { cin >> A[i][j]; sum += A[i][j]; } } //同じ辺を2回カウントしているので2で割る sum /= 2; REP (i, N) { //経由 REP (j, N) { //開始 for (int k = j + 1; k < N; ++k) { //終端 if (i == j || i == k) continue; if (A[j][i] + A[i][k] < A[j][k]) { //より短く行けたらおかしい cout << -1 << endl; return 0; } if (A[j][i] + A[i][k] == A[j][k]) { //同じコストでいけたら直接辺は削除できる if (flag[j][k] == false) { //直接辺を削除するのは1回だけだからフラグを持つ sum -= A[j][k]; flag[j][k] = true; } } } } } cout << sum << endl; }
E問題
問題文を把握したくらいで時間切れ。700点問題とはいえちょっと解ける気はしなかった。
