Atcoder Beginner Contest 088

A - Infinite Coins

Nを500で割った余りがA以下ならば"Yes".

#include <bits/stdc++.h>

using namespace std;

int main(void) {
  int n, a;
  cin >> n >> a;

  int m = n % 500;
  if(m <= a) {
    cout << "Yes" << endl;
  }
  else {
    cout << "No" << endl;
  }
}

B - Card Game for Two

AliceとBobは大きいカードから順に交互に取っていくので, カードをソートして
交互に和をとればよい.

#include <bits/stdc++.h>

using namespace std;

int main(void) {
  int n;
  cin >> n;
  vector <int> a;
  for(int i = 0; i < n; i++) {
    int x;
    cin >> x;
    a.push_back(x);
  }

  int Alice = 0, Bob = 0;
  sort(a.rbegin(), a.rend());
  for(int i = 0; i < n; i++) {
    if(i % 2 == 0) {
      Alice += a[i];
    }
    else {
      Bob += a[i];
    }
  }

  cout << Alice - Bob << endl;
}

C - Takahashi's Information

自力では解けなかった.
高橋君の情報が正しいなら
a[1] = 0
b[i] = c[1][i] - a[1]
a[i] = c[i][1] - b[1]
となるので, c[i][j] = a[i] + b[j]が成り立つかどうかを確かめればよい(らしい).

#include <bits/stdc++.h>

using namespace std;

int main(void) {
  int c[4][4];
  for(int i = 1; i <= 3; i++) {
    for(int j = 1; j <= 3; j++) {
      cin >> c[i][j];
    }
  }

  int a[4], b[4];
  a[1] = 0;
  for(int i = 1; i <= 3; i++) {
    b[i] = c[1][i] - a[1];
  }
  for(int i = 2; i <= 3; i++) {
    a[i] = c[i][1] - b[1];
  }

  for(int i = 1; i <= 3; i++) {
    for(int j = 1; j <= 3; j++) {
      if(c[i][j] != a[i] + b[j]) {
	cout << "No" << endl;
	return 0;
      }
    }
  }
  cout << "Yes" << endl;
}

D - Grid Repainting

2次元迷路の最短路の長さを求めて白いマスの数から引けばよい.
最短路の長さは幅優先探索(蟻本そのまま)で解ける.

#include <bits/stdc++.h>

using namespace std;

int h, w;
char maze[51][51];
int d[51][51];
int dx[4] = {1, 0, -1, 0};
int dy[4] = {0, 1, 0, -1};

void bfs() {
  queue< pair<int, int> > que;
  for(int i = 1; i <= h; i++) {
    for(int j = 1; j <= w; j++) {
      d[i][j] = INT_MAX;
    }
  }
  que.push(pair<int, int> (1, 1));
  d[1][1] = 0;

  while(que.size()) {
    pair <int, int> p = que.front();
    que.pop();
    if(p.first == h && p.second == w) {
      break;
    }
    for(int i = 0; i < 4; i++) {
      int nx = p.first + dx[i];
      int ny = p.second + dy[i];
      if(1 <= nx && nx <= h && 1 <= ny && ny <= w && maze[nx][ny] != '#' && d[nx][ny] == INT_MAX) {
	que.push(pair<int, int>(nx, ny));
	d[nx][ny] = d[p.first][p.second] + 1;
      }
    }
  }
  return;
}

int main(void) {
  cin >> h >> w;
  for(int i = 1; i <= h; i++) {
    for(int j = 1; j <= w; j++) {
      cin >> maze[i][j];
    }
  }

  int count = 0;
  for(int i = 1; i <= h; i++) {
    for(int j = 1; j <= w; j++) {
      if(maze[i][j] == '.') {
	count++;
      }
    }
  }

  bfs();
  int mn = d[h][w];
  if(mn == INT_MAX) {
    cout << "-1" << endl;
    return 0;
  }
  cout << count - (mn + 1) << endl;
}