AtCoder abc272 参加メモ

B - Everyone is Friends

人iが参加した舞踏会を隣接行列で持っておいて全探索。O(N³)

#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,m; cin >> n >> m;
  // t[i][j] := 人iが舞踏会jに参加していればtrue
  vector t(n,vector<bool>(m));
  REP(i,m) {
    int k; cin >> k;
    REP(j,k) {
      int a; cin >> a; a--;
      t[a][i] = true;
    }
  }

  REP(i,n) for(int j = i+1; j < n; j++) {
    bool ok = false; // 人iが全ての人と一度は舞踏会に参加したかどうか
    REP(k,m) ok |= t[i][k] && t[j][k];
    if (!ok) { cout << "No" << endl; return 0; }
  }

  cout << "Yes" << endl;
  return 0;
}

C - Max Even

2要素の和が偶数になるケースは

偶数 + 偶数
奇数 + 奇数

の2パターンしかない。偶数、奇数それぞれをソートして最大の値の和を取れば良い。

#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; cin >> n;
  vector<int> a(n);
  REP(i,n) cin >> a[i];
  sort(a.begin(),a.end());
  vector<int> e,o;
  REP(i,n) {
    if (a[i] % 2 == 0) e.push_back(a[i]);
    else o.push_back(a[i]);
  }

  int ans = -1;
  if(e.size() >= 2) ans = max(ans, e[e.size()-1] + e[e.size()-2]);
  if(o.size() >= 2) ans = max(ans, o[o.size()-1] + o[o.size()-2]);

  cout << ans << endl;
  return 0;
}

D - Root M Leaper

整数で扱うために平方根を外し、 (i-k)² + (j-l)² = M となる位置にコマを移動させることを考える。

コマの相対的な移動先はどの位置でも変わらない。それを前計算しておけば単純にBFSで最短手数を求められる。

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

int n,m;
vector dist(400,vector<int>(400,INF));
vector<P> moves;

void bfs() {
  queue<P> q;
  q.emplace(0,0);
  dist[0][0] = 0;

  while(q.size()) {
    auto [x,y] = q.front(); q.pop();
    int nd = dist[x][y] + 1;
    for(auto [i,j]: moves) {
      int nx = x+i, ny = y+j;
      if (nx < 0 || ny < 0 || nx >= n || ny >= n) continue;
      if (nd < dist[nx][ny]) {
        dist[nx][ny] = nd;
        q.emplace(nx,ny);
      }
    }
  }
  return;
}

int main() {
  cin >> n >> m;
  REP(i,n) REP(j,n) {
    if (i*i+j*j == m) {
      moves.emplace_back(i,j);
      moves.emplace_back(-i,-j);
      if (i != 0) moves.emplace_back(-i,j);
      if (j != 0) moves.emplace_back(i,-j);
    }
  }

  bfs();
  REP(i,n) {
    REP(j,n) cout << (dist[i][j] == INF ? -1 : dist[i][j]) << " ";
    cout << endl;
  }
  return 0;
}