AtCoder abc274 参加メモ

AtCoder DP 巡回セールスマン DFS

キーエンスプログラミングコンテスト2022（AtCoder Beginner Contest 274） - AtCoder

B - Line Sensor

二重ループでカウント

#include <bits/stdc++.h>
using namespace std;
#define REP(i,n) for(int i=0;i<(n);i++)
#define endl '\n'

int main() {
  int h,w; cin >> h >> w;
  vector<string> c(h);
  REP(i,h) cin >> c[i];

  REP(j,w) {
    int x = 0;
    REP(i,h) { if (c[i][j] == '#') x++; }
    cout << x << " ";
  }
  cout << endl;
  return 0;
}

C - Ameba

グラフにしてdfsで親からの距離を計算

#include <bits/stdc++.h>
using namespace std;
#define REP(i,n) for(int i=0;i<(n);i++)
#define endl '\n'
const int INF = numeric_limits<int>::max();

int n;
vector<int> a(2e5);
vector<vector<int>> g(4e5+1);
vector<int> dist(4e5+1,INF);

void dfs(int i, int p) {
  for(int v: g[i]) {
    if (v == p) continue;
    dist[v] = dist[i]+1;
    dfs(v,i);
  }
  return;
}

int main() {
  cin >> n;
  REP(i,n) cin >> a[i];

  REP(i,n) {
    g[a[i]].push_back((i+1)*2);
    g[a[i]].push_back((i+1)*2+1);
  }

  dist[1] = 0;
  dfs(1,-1);

  for(int k = 1; k <= 2*n+1; k++) cout << dist[k] << endl;
  return 0;
}

D - Robot Arms 2

x方向とy方向を独立して考えるDP。

#include <bits/stdc++.h>
using namespace std;
#define REP(i,n) for(int i=0;i<(n);i++)
#define endl '\n'

int main() {
  int n,x,y; cin >> n >> x >> y;
  vector<int> a(n);
  REP(i,n) cin >> a[i];

  set<int> sx,sy;
  sx.insert(a[0]);
  sy.insert(0);
  for(int i = 1; i < n; i++) {
    set<int> t,p;
    i % 2 == 0 ? swap(p,sx) : swap(p,sy);
    for(int v: p) {
      t.insert(v+a[i]);
      t.insert(v-a[i]);
    }
    i % 2 == 0 ? swap(t,sx) : swap(t,sy);
  }

  cout << (sx.count(x) && sy.count(y) ? "Yes" : "No") << endl;
  return 0;
}

E - Booster

巡回セールスマン問題の応用。(参考問題: C - 巡回セールスマン問題)

  • dp[n][i] := すでに訪れた集合が n であって、最後にいる場所が i であるときの、合計コストの最小値
  • 宝箱も巡回する場所の一部として一緒に考えて良い。
#include <bits/stdc++.h>
using namespace std;
#define REP(i,n) for(int i=0;i<(n);i++)
#define endl '\n'
using ll = long long;
const ll LINF = numeric_limits<ll>::max();

int main() {
  int n,m; cin >> n >> m;
  n+=1; // 原点分を追加
  int w = n+m;
  vector<int> x(w),y(w);
  for(int i = 1; i < w; i++) cin >> x[i] >> y[i];
  vector dist(w,vector<double>(w)); // dist[i][j] := iからjへの距離
  REP(i,w) REP(j,w) dist[i][j] = sqrt(powl(x[i]-x[j],2) + powl(y[i]-y[j],2));

  // dp[n][i] := すでに訪れた集合が n であって、最後にいる場所が i であるときの、合計コストの最小値
  vector dp(1<<w, vector<double>(w,LINF));
  dp[0][0] = 0;

  REP(bit, 1<<w) {
    int cnt = 0; // bitの状態で取得している宝箱数
    REP(i,m) if (bit>>(n+i) & 1) cnt++;

    // 各bitの状態でiからjへの遷移を考える
    REP(i,w) {
      if (dp[bit][i] == LINF) continue;
      REP(j,w) {
        if (bit >> j & 1) continue;
        int nb = bit | 1<<j;
        dp[nb][j] = min(dp[nb][j], dp[bit][i] + dist[i][j]/(1<<cnt));
      }
    }
  }

  double ans = LINF;
  int t = (1<<n)-1;
  REP(bit,1<<w) if ((bit&t)==t) ans = min(ans,dp[bit][0]);
  printf("%.10f\n",ans);
  return 0;
}