AtCoder abc270 参加メモ

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;
}