AtCoder abc244 参加メモ

AtCoder Beginner Contest 244 - AtCoder の参加メモ

C - Yamanote Line Game

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

int main() {
  int n; cin >> n;
  vector<bool> used(2005);

  int cur = 1;
  while(1) {
    while(used[cur]) cur++;
    cout << cur << endl;
    used[cur] = true;

    int x; cin >> x;
    if (x == 0) break;
    used[x] = true;
  }
  return 0;
}

D - Swap Hats

10¹⁸ は偶数なので、sとtのそれぞれを比較して偶数回の操作で一致させることができるかどうかを調べる。

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

int main() {
  vector<char> s(3),t(3);
  REP(i,3) cin >> s[i];
  REP(i,3) cin >> t[i];

  int same = 0;
  REP(i,3) if (s[i] == t[i]) same++;

  bool ok = same == 0 || same == 3;
  cout << ( ok ? "Yes" : "No") << endl;
  return 0;
}

E - King Bombee

DP。DP配列を dp[ 何回目の遷移か ][ 頂点番号 ][ xを通った回数が偶数か奇数か ] と置いて計算する。最終的に dp[ k回目の遷移 ][ 頂点T ][ xを通った回数が偶数 ] が答えとなる。

#include <bits/stdc++.h>
#include <atcoder/all>
using namespace atcoder;
using namespace std;
#define REP(i,n) for(int i=0;i<(n);i++)
using mint = modint998244353;

int n,m,k,s,t,x;
vector<vector<int>> g(2005);
mint dp[2005][2005][2];

void solve() {
  dp[0][s][0] = 1;

  REP(i,k) REP(j,n) {
    for(auto v: g[j]) {
      dp[i+1][v][v == x ? 1 : 0] += dp[i][j][0];
      dp[i+1][v][v == x ? 0 : 1] += dp[i][j][1];
    }
  }

  cout << dp[k][t][0].val() << endl;
  return;
}

int main() {
  cin >> n >> m >> k >> s >> t >> x;
  s--; t--; x--;

  REP(i,m) {
    int u,v; cin >> u >> v;
    u--; v--;
    g[u].push_back(v);
    g[v].push_back(u);
  }

  solve();
  return 0;
}