AtCoder Beginner Contest 109
A - ABC33
問題文をよく読めばできます。
方針
A*B*Cが奇数となるにはAとBがどちらも偶数でなければならない。
AとBが奇数の場合、Cは1または3を選択すれば、A*B*Cは奇数となる。
自分の回答
#include<iostream> using namespace std; int A, B; int main() { scanf("%d%d", &A, &B); if (A % 2 == 0 || B % 2 == 0) printf("No\n"); else printf("Yes\n"); return 0; }
コメント
特になし。
B - Shiritori
こちらも特に難しくはないです。
方針
しりとりが成立しているか順番に確かめればよい。
自分の回答
既出の単語かどうかを調べる操作はハッシュ連想配列を用いれば、O(1)で行える。
#include<iostream> #include<unordered_map> using namespace std; unordered_map<string, int> mp; int N; string input; int main() { scanf("%d", &N); char last; for (int i = 0; i < N; ++i) { cin >> input; if (i != 0) { if (input[0] != last) { printf("No\n"); return 0; } } last = input[input.length() - 1]; auto itr = mp.find(input); if (itr != mp.end()) { printf("No\n"); return 0; } mp[input] = 0; } printf("Yes\n"); return 0; }
コメント
unordered_mapなどの標準ライブラリの使い方は覚えておくと役に立つことが多々あります。
C - Skip
冷静になれば解ける問題です。
方針
移動できる距離は$D$と決まっているので、初期位置$X$に対して、移動できる位置は$X+nD$（$n$は整数）のみである。したがって、$N$個の都市と初期位置までの距離が$D$の倍数にならなければならない。
このとき、$D$を最大化するため、$D$は$N$個の都市と初期位置の間の距離の最大公約数であることがわかる。
自分の回答
#include<iostream> using namespace std; int N, X, x; int get_dist(int a, int b) { if (a >= b) return a - b; else return b - a; } template <typename T> T gcd(T a, T b) { if (a < 0) a = -a; if (b < 0) b = -b; while(b != 0) { a %= b; if (a == 0) return b; b %= a; } return a; } int main() { scanf("%d%d", &N, &X); int ans = 0; for (int i = 0; i < N; ++i) { scanf("%d", &x); int dist = get_dist(X, x); if (i == 0) ans = 0; ans = gcd(ans, dist); } printf("%d\n", ans); return 0; }
コメント
最大公約数や最小公倍数は忘れた頃に出題されるので、きちんと押さえておきましょう。
D - Make Them Even
今回は400点問題でD問題の中では簡単な方でした。
方針
偶数枚のコインが置かれたマスの数を最大化するには、奇数枚のコインが置かれたマス（以降、奇数マス）から他の奇数マスに移動すればよい。
ただし、移動について「まだ選んだことのないマスしか選択できない」という制約がある。
問題を簡略化するため、できるだけ同じ行にある奇数マス同士間でコインを移動させることを考える。すると、
(1) 同じ行に奇数マスが偶数個ある場合
同じ行内で移動をすべて完結させることができる。
(2) 同じ行に奇数マスが奇数個ある場合
1マスだけ奇数マスが残る。
ある行について、左から順番に奇数マスとその一番近くの右にある奇数マス同士で移動するとした場合、同じ行に奇数マスが奇数個ある行は、一番右の奇数マスだけが残ることになる。
そして次に、奇数マスが奇数個ある行の一番右にある奇数マスについて、行をまたいで移動することを考える。左の奇数マスから右の奇数マスへコインを移動させる場合、一番右側の列はかならずまだ選択されていないことになる。
したがって、上から順番に余った奇数マスから
(1) 一番右に移動する
(2) 最も近くにある奇数マスの行まで下に移動する
(3) 奇数マスにたどり着くまで左に移動する
という操作を繰り返せばよいことがわかる。
自分の回答
上記の方針の通りに実装する。
出力として最初に移動回数を出力しなければならないため、vectorに移動内容を入れておく。
#include<iostream> #include<vector> using namespace std; typedef struct { int x; int y; } Pos; int H, W, a; vector<vector<int>> procs; // procs[i]: i番目の移動内容 int main() { scanf("%d%d", &H, &W); vector<Pos> odds; // 奇数マス for (int h = 1; h <= H; ++h) { for (int w = 1; w <= W; ++w) { scanf("%d", &a); if (a % 2 == 1) odds.push_back(Pos{w, h}); } } // 1. できるだけ同じ行内で解決する。 vector<Pos> remain_odds; // 残った奇数マス for (int i = 0; i < odds.size(); ++i) { if (i == odds.size() - 1) { remain_odds.push_back(odds[i]); break; } if (odds[i].y == odds[i+1].y) { // 同じ行内に奇数マスがある場合 int y = odds[i].y; for (int x = odds[i].x; x < odds[i+1].x; ++x) { procs.push_back(vector<int>({y, x, y, x+1})); } i += 1; } else { // 同じ行内に奇数マスが残ってない場合 remain_odds.push_back(odds[i]); } } // 2. 残った奇数マスはできるだけ近い列のものと解決させる。 for (int i = 0; i + 1 < remain_odds.size(); i += 2) { int y1 = remain_odds[i].y; int x1 = remain_odds[i].x; int y2 = remain_odds[i+1].y; int x2 = remain_odds[i+1].x; // 2-1. 一番右まで進む。 int x = x1; int y = y1; while (x != W) { procs.push_back(vector<int>({y, x, y, x+1})); x += 1; } // 2-2. 下に移動する。 while (y != y2) { procs.push_back(vector<int>({y, W, y+1, W})); y += 1; } // 2-3. 左に進む。 while (x != x2) { procs.push_back(vector<int>({y2, x, y2, x-1})); x -= 1; } } printf("%d\n", procs.size()); for (int i = 0; i < procs.size(); ++i) { printf("%d %d %d %d\n", procs[i][0], procs[i][1], procs[i][2], procs[i][3]); } return 0; }
コメント
今回のように問題を要素分割していき、簡単な問題に落としこんでいく力がC問題やD問題では問われることが多いです。
様々な例を自分の手で書いてみて、冷静に問題を見つめなおしてみましょう。
