RUPC2019参加記 Day2

Posted on 4 mins read

1日目の続きです。
※この記事は問題のネタバレを含みます

コンテスト

@prd_xxxさん、@cider68760155さん、@medalotteさんと組みました。
問題は、会津大学の5時間のセットでした。
この日は振り返ってみると結構たくさん解いていたようです。

コンテスト中に合計3個の誤読をしましたが、チームメイトに指摘されたりして全て修正できてよかったです。

内容

C: Phone Number

ICPCにありそうな(?)全探索。

signed main() {
  int n; cin >> n;
  string ss; cin >> ss;
  vector<int> s(n); REP (i, n) s[i] = ss[i] - '1';
  vector<vector<int>> a(9, vector<int>(9));
  REP (i, n - 1) {
    int x = s[i], y = s[i + 1];
    if (x > y) swap(x, y);
    a[x][y]++;
  }
  vector<int> va;
  int ans = 1e18;
  vector<int> t(9); REP (i, 9) t[i] = i;
  do {
    int acc = 0;
    REP (i, 9) {
      REPI (j, i + 1, 9) {
        int x = t[i], y = t[j];
        if (x > y) swap(x, y);
        int dis = abs(i % 3 - j % 3) + abs(i / 3 - j / 3);
        acc += a[x][y] * dis;
      }
    }
    if (chmin(ans, acc)) {
      va = t;
    }
  } while (next_permutation(ALL(t)));
  REP (i, 3) {
    REP (j, 3) {
      cout << va[3 * i + j] + 1;
    }
    cout << endl;
  }
}

D: Tunnel

DはDPのD。

double eps = 1e-5;
double get(double a, double b) {
  if (a + b < eps) return 0;
  return (a * a + b * b) / (2.0 * (a + b));
}
signed main() {
  int n; cin >> n;
  vector<double> h(n); REP (i, n) cin >> h[i];
  const int K = 301;
  vector<vector<double>> dp(n + 1, vector<double>(K, 1e18));
  dp[0][1] = 0;
  REP (i, n) {
    REPI (k1, 1, K) {
      REPI (k2, 1, K) {
        double ad = dp[i][k1];
        if ((k1 < h[i] && k2 < h[i]) || (k1 > h[i] && k2 > h[i])) {
          ad += (abs(h[i] - (double)k1) + abs(h[i] - (double)k2)) / 2.0;
        } else {
          ad += get(abs(h[i] - (double)k1), abs(h[i] - (double)k2));
        }
        chmin(dp[i + 1][k2], ad);
      }
    }
  }
  double ans = 1e18;
  REPI (k, 1, K) chmin(ans, dp[n][k]);
  cout << setprecision(10) << ans << endl;
}

E: こたつがめを燃やさないで

辺を工夫して貼るとダイクストラに帰着されます。
周囲8方向全てに辺を貼ってしまえば、他の地点では爆破の影響を考えなくて良くなることがポイント。

vector<int> dx = {-1, 0, 1, 0};
vector<int> dy = {0, -1, 0, 1};
vector<int> ex = {-1, -1, 1, 1};
vector<int> ey = {-1, 1, -1, 1};

signed main() {
  int h, w, a, b; cin >> h >> w >> a >> b;
  vector<string> t(h); REP (i, h) cin >> t[i];
  ii s, g;
  REP (i, h) {
    REP (j, w) {
      if (t[i][j] == 's') s = {i, j};
      if (t[i][j] == 'g') g = {i, j};
    }
  }
  auto valid = [&](ii p) {
    return 0 <= p.fi && p.fi < h && 0 <= p.se && p.se < w;
  };
  auto around_bomb = [&](ii p) {
    bool ret = false;
    ret |= t[p.fi][p.se] == '*';
    REP (i, 4) {
      ii to = {p.fi + dy[i], p.se + dx[i]};
      if (valid(to)) ret |= t[to.fi][to.se] == '*';
    }
    REP (i, 4) {
      ii to = {p.fi + ey[i], p.se + ex[i]};
      if (valid(to)) ret |= t[to.fi][to.se] == '*';
    }
    return ret;
  };

  vector<vector<int>> d(h, vector<int>(w, 1e17));
  d[s.fi][s.se] = 0;
  priority_queue<pair<int, ii>, vector<pair<int, ii>>, greater<pair<int, ii>>> q;
  q.push({0, {s}});
  while (!q.empty()) {
    pair<int, ii> pii = q.top(); q.pop();
    ii p = pii.se;
    if (d[p.fi][p.se] < pii.fi) continue;
    bool bomb = around_bomb(p);
    REP (i, 4) {
      ii to = {p.fi + dy[i], p.se + dx[i]};
      if (!valid(to)) continue;
      int tmp = d[p.fi][p.se] + a;
      if (t[to.fi][to.se] == '#') {
        if (bomb) continue;
        tmp += b;
      }
      if (chmin(d[to.fi][to.se], tmp)) {
        q.push({tmp, to});
      }
    }
    REP (i, 4) {
      ii to = {p.fi + ey[i], p.se + ex[i]};
      if (!valid(to)) continue;
      int tmp = d[p.fi][p.se] + 2 * a;
      if (t[to.fi][to.se] == '#' || (t[p.fi + ey[i]][p.se] == '#' && t[p.fi][p.se + ex[i]])) {
        if (bomb) continue;
        tmp += b;
      }
      if (chmin(d[to.fi][to.se], tmp)) {
        q.push({tmp, to});
      }
    }
  }
  if (d[g.fi][g.se] == 1e17) {
    cout << "INF" << endl;
  } else {
    cout << d[g.fi][g.se] << endl;
  }
}

G: First Kiss

「どれか1つ」という条件の逆型のゲームは、1を引けば「全部」という条件の正型に帰着されるんですね。
あと、個数d個制限のNIMはmod (d + 1)を考えればよいです。

signed main() {
  int n, D; cin >> n >> D;
  int acc = 0;
  REP (i, n) {
    int a; cin >> a;
    acc ^= (a - 1) % (D + 1);
  }
  cout << (acc ? "First" : "Second") << endl;
}

H: Ghost

燃やす埋めるを知らなかったのですが、フローであることを問題文からエスパーしてググり力で解きました。
燃やす埋めるについてはnicoshindanninさんのスライドが分かりやすかったです。

@prd_xxxさんに実装してもらいました。
個人的には、デバッグを手伝っているときに@prd_xxxさんのPythonのDinic法ライブラリのバグを目で発見したのがハイライトでした。

コンテスト後に自分で書いたものを張っておきます。

// Max Flowは省略
signed main() {
  int n, m; cin >> n >> m;
  string u; cin >> u;
  DirectedGraph g(n + 2);
  int s = n, t = n + 1;
  REP (i, n) {
    int a; cin >> a;
    if (u[i] == 'R') {
      g.add_edge(s, i, a);
    } else {
      g.add_edge(i, t, a);
    }
  }
  map<ii, int> mp;
  REP (i, m) {
    int u, v, c; cin >> u >> v >> c;
    u--; v--;
    if (u > v) swap(u, v);
    g.add_edge(u, v, c);
  }
  cout << g.max_flow(s, t) << endl;
}

その他

  • 競プロer、予想の100倍ぐらい起床力が高かった。
  • 駅まで歩いて帰るときにけんちょんさん(@drken1215)とたくさんお話出来ました。燃やす埋めるの応用の講義をしてもらいました。

day3に続きます。