TOYOTA MOTOR CORPORATION Programming Contest 2022(AtCoder Beginner Contest 270) - AtCoder
B - Hammer
- 場合分けをする
- ゴールが正の場合と負の場合を両方考えるのは面倒なので、負の場合は正に置き換えてやると楽
#include <bits/stdc++.h> using namespace std; int main() { int x,y,z; cin >> x >> y >> z; if (x < 0) { x = -x; y = -y; z = -z; } int ans = x; if (0 < y && y < x) ans = z < y ? abs(z) + x - z : -1; cout << ans << endl; return 0; }
C - Simple path
- xからスタートしyを見つけるDFSで経路を記録して出力
#include <bits/stdc++.h> using namespace std; #define REP(i,n) for(int i=0;i<(n);i++) int n,x,y; vector<vector<int>> g(2e5); vector<int> ans; bool dfs(int i, int p) { if (i == y) { ans.push_back(i); return true; } for(int v: g[i]) { if (v == p) continue; if (dfs(v,i)) { ans.push_back(i); return true; } } return false; } int main() { cin >> n >> x >> y; x--; y--; REP(i,n-1) { int u,v; cin >> u >> v; u--; v--; g[u].push_back(v); g[v].push_back(u); } dfs(x,-1); reverse(ans.begin(),ans.end()); for(int v: ans) cout << v+1 << " "; return 0; }
D - Stones
- 反例がパッと思い浮かばなかったが、
貪欲に最も多い石の数を取り除く方法
では不正解になる - それぞれの手番で最良の手を打つ(ミニマックス法)ことを考える
- 高橋の場合は石を最大化、青木の場合は高橋が取る石を最小化、というのをメモ化再帰する。制約は大きくないのでこれで間に合う
#include <bits/stdc++.h> using namespace std; #define REP(i,n) for(int i=0;i<(n);i++) const int INF = numeric_limits<int>::max(); int n,k; vector<int> a(100); // memo[i][j] := 山の残りの石の数がi、手番がj(0:高橋,1:青木)のときの高橋が取り除ける最大の石の数 vector memo(10001, vector<int>(2)); int f(int x, int t) { if (abs(memo[x][t]) != INF) return memo[x][t]; if (x == 0) return memo[x][t] = 0; REP(i,k) { if (x - a[i] < 0) break; if (t == 0) { memo[x][t] = max(memo[x][t], a[i] + f(x-a[i],1)); } else { memo[x][t] = min(memo[x][t], f(x-a[i],0)); } } return memo[x][t]; } int main() { cin >> n >> k; REP(i,n) cin >> a[i]; REP(i,n+1) { memo[i][0] = -INF; memo[i][1] = INF; } cout << f(n,0) << endl; return 0; }