AtCoder Beginner Contest 096

AtCoder Beginner Contest 096の解説です。
ABC096 旧版:
abc096.contest.atcoder.jp
ABC096 beta:
https://beta.atcoder.jp/contests/abc096/beta.atcoder.jp

解けた問題だけ解説をしていきますー

要項

AtCoder Beginner Contest 096
rated 1200
5/5(土) 21:00 ～ 22:40 (100分)
100-200-300-400 (4問)
ペナルティ: 5分

方針

例大祭前日の為非参加

A - Day of Takahashi

まず、1月からa-1月までの高橋は全部でa-1個あります。
後はa月a日が過去か未来か確認したいので、a<=bならば高橋を1個増やします。
三項演算子を用いるとa<=b?a:a-1;と書けます。

B - Maximum Sum

まず、どの数を2倍すべきか考えます。
A,B,Cのある数を2倍すると、その数がもう1個増えることと同義ですから最も大きい数を増やすのが最も結果が良くなります。
よって、3つのうち最大の数を倍すれば良いです。

C - Grid Repainting 2

まず、同時に隣接した2マスを塗る必要があるので、周囲に黒マスが無い黒マスを作ることはできません。
それ以外の時を考えます。すなわち、黒マスがn個(2≦n)隣接しているとします。
まず、2個の黒マスが隣接しているならば問題なく塗ることができます。
今、m個の黒マスを塗れたとします。この時、そのうちの1個の黒マスと隣接した白マスを同時に塗ることで、m+1個の黒マスを塗ることができます。
即ち、数学的帰納法を用いて2個以上の隣接する黒マスを全て塗ることができました。
ということは、周囲に黒マスが無い黒マスが存在するかどうかのみを調べれば良いことが分かります。
なお、こういう周囲を調べる時は、先にキャンパスを上下左右に1マス拡張しておくと便利ですよ。
例えば
3 3
.#.
###
.#.
と与えられた時、次のように変形しておくのです。
.....
..#..
.###.
..#..
.....
こうするとマップの端を例外処理しなくて良くなり、調べる速度が上昇します。

D - Five, Five Everywhere

まず条件に注目すると、素数が55555以下に対しNが55以下なので、割と自由に素数を持ってくることができると分かります。
次に、どの異なる5個を選んでも合成数になるという点から、全ての素数に対し共通の性質があることも分かります。
異なる5個を選んでも合成数になる、という点から合成数は5の倍数ではないかという仮定を立てられます。
この時、倍数判定なのでmodを考えると、5つの素数がそれぞれ5a+n、5b+n、5c+n、5d+n、5e+n(1≦n≦4)であれば全ての素数の和が5(a+b+c+d+e)+5nと5の倍数になることが分かります。
後は高々55個なので素数判定でも篩でも好きなものを選べば大丈夫です。

感想

解くことは難しくなく、速く解くとなるとある程度アルゴリズム関連の知識が必要になるのでABCOnlyと考えると良問ですね。
B問題に関しては2倍の処理をビットシフトで作ることによって面倒なことをせず解くことができます。
C問題に関しては二次元マップの頻出知識、周囲1マスずつ拡張と1個のforで4個を見る方法を知っていると楽に考えられます。
あ、1個のforで4個を……というのは次のような方法です。
int dx[8] = {1, 1, 0, -1, -1, -1, 0, 1};
int dy[8] = {0, 1, 1, 1, 0, -1, -1, -1};
for (int i = 0;i < 8;i += 2) map[y + dy[i]][x + dx[i]] ……
これで周囲4方向に関して調べることができるので、覚えておくと良いです。8方向ならi += 1に変えるだけで動きます。
D問題に関しては、素数の大まかな個数や合成数の性質、異なる5個～と合成数～からmod5を連想する力などが必要な知識ですかね。
私は参加していないですが、参加者の皆さん、お疲れさまでした。