AtCoder Beginner Contest 096の解説
お疲れ様でした！
A - Day of Takahashi
入力: a b (a, b ∈ ℤ; 1 ≦ a ≦ 12; 1 ≦ b ≦ 31)
出力: 1月1日からa月b日までの「高橋」の日数
「高橋」…月と日の数が等しい日
まず、a-1月までの「高橋」は確実に含まれるので、
tmp += a-1;
また、bがa以上ならば、a月の「高橋」も含まれるので、
if(b >= a) tmp++;
最後に出力
writeln(tmp);
感想: 1WAした。落ち着いて考えることで、上のような方針が立つ。
B - Maximum Sum
入力: A B C K (A, B, C, K ∈ ℤ; 1 ≦ A, B, C ≦ 50; 1 ≦ K ≦ 10)
出力: K回の操作を終えた後の黒板上の整数の合計としてありうる最大の値
最大の値をとるとき、A, B, Cのうち最も大きい値のみを操作し続けることがわかる。よって
int r = max(A, B, C) * 2 ^^ K;
また、max(A, B, C)をA+B+Cから引いた値、すなわち操作しなかった2つの値についても合計に加えるため
int s = A + B + C - max(A, B, C);
最後に操作後の黒板の整数の合計を出力
writeln(r + s);
感想: 落ち着いて考えることで、上のような方針が立つ。
C - Grid Repainting 2
入力: H W (H, W ∈ ℤ; 1 ≦ H, W ≦ 50)
s(1,1)s(1,2)s(1,3)...s(1,W)
s(2,1)s(2,2)s(2,3)...s(2,W)
…
s(H,1)s(H,2)s(H,3)...s(H,W)
なお ∀i∀j(s(i,j) = '#' ∨ s(i,j) = '.') (1 ≦ i ≦ H, 1 ≦ j ≦ W)
出力: 目標達成が可能なら"Yes", そうでないなら"No"
まずsを2次元配列として読み取る。
'#'に着目する。('.'は初期状態としてすべてのマスに配置されているので、着目しない。)
'#'の近傍4マスに'#'が存在しないならば、すなわち目標を達成することは不可能であることがわかる。よって、'#'を探し、もし存在したら、そこの近傍4マスを探索し、その4マスのどこにも'#'が存在しないならば"No"を即座に出力して終了すればよい。そして、もしすべてのマスが条件を満たしているならば、"Yes"を出力して終了すればよい。解答例は下にまとめてある。
感想: こういう「近傍nマス」みたいなことをするプログラムを書くのに慣れてきた。マインスイーパーとか実装するときよく使う。これにDFS組み合わせたりすると面白くなる。
D - Five, Five Everywhere
入力: N (N ∈ ℤ; 5 ≦ N ≦ 55)
出力: 長さNの数列a_1, a_2, ..., a_Nを出力する。
ただし…
条件を満たす数列が複数個あるなら、どれを出力してもよい。
まず2から1381までの素数を含んだリストを用意する。エラトステネスの篩とかで。
ここで、10n + 1(a ∈ ℤ+)な形をしている素数に着目する。それぞれ異なる5個の素数を、10a+1, 10b+1, 10c+1, 10d+1, 10e+1とおくと、合計は
10(a+b+c+d+e)+5 = 5(2a+2b+2c+2d+2e+1)
となる。ここで、2a+2b+2c+2d+2e+1が2以上であることは明らかなので、10n+1な形をしている素数を55個集めておけば、この問題は解くことが可能である。そのような素数は
11 31 41 61 71 101 131 151 181 ...
と続く。
つまり、一度素数列を生成した後、文字列に変換して一桁目を取得してそれが'1'なら列に入れる、といったfilterの操作をしておいて、そのリストの0個目からN-1個目の値を出力するなどすればよい。
なお、10n+1だけでなく、10n+3, 10n+7の形をした素数列を出力することでも解ける。証明は省略。10n+3の形が一番コストが低いかも？(1303まで用意すれば十分だから)
追記: 想定解の、「5で割って1あまる素数の列」は上の10n+1の形の素数列と全く同じ列を生成する。5(2k+1)+1 = 10k+6 = 2(5k+3)で、商が奇数のときは素数ではないので、結局同じものになる。10n+3, 10n+7の形をした素数列についてもAtCoderで提出をしてACを確認した。
感想: 数学な問題は普段数ⅡBの問題を解くときとかにも使える考え方が適用できたりして面白い。最初「素数列生成してそのまま出せばいいだろ〜ｗ」みたいな甘い考えをしていたら普通にWAされた。A問題と合わせて10分のペナルティがprivate_yusukeを襲ったのであった。
A: https://beta.atcoder.jp/contests/abc096/submissions/2460648
B: https://beta.atcoder.jp/contests/abc096/submissions/2459724
C: https://beta.atcoder.jp/contests/abc096/submissions/2461606
D: https://beta.atcoder.jp/contests/abc096/submissions/2463242
