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; }