AtCoder Grand Contest 027 - 情報妖精の競プロ日記

AtCoder Grand Contest 027に参加しました！
AtCoder Grand Contest 027 旧版
 AtCoder Grand Contest 027 beta版

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

要項

AtCoder Grand Contest 027
rated
9/16(土) 21:00 ～ 23:20 (140分)
200-700(400)-900-1100-1300-1900 (6問)
ペナルティ: 5分

方針

2完、どうせB問題はDPなので解きたい
後は構築問題があれば最高かなぁ、とにかく1問目は速く解かないと

A - Candy Distribution Again

なるべくお菓子をあげる個数を減らした方が最大化しやすいので、まず $a$ をソートし、小さい順にあげることにします。
ただし、全員にお菓子をあげることに成功した場合、丁度の個数にならない分を全部最後の人に押し付けることにします。
これにより、 $a_i$ について $x$ 以下ならば $x$ から $a_i$ を引き、そうでないならば $i$ を出力することで求められることができます。
ただし、最後までループが回った場合はその時の $x=0$ で無ければ答えを1引くのを忘れないようにしましょう。

B - Garbage Collector

解けたら天才だと思う。

C - ABland Yard

まず、自分がある頂点にいるとしましょう。
その時、その頂点に繋がる頂点には'A'も'B'も存在する必要があります。
もし片方、あるいは両方が欠けているならばその欠けている方を次の文字とする文字列が構成できないからですね。
逆に、全ての頂点がこの条件を満たしているならばその頂点を通ることで任意の文字列が構成できます。
そこで、各頂点について、隣接する頂点の中に'A'、あるいは'B'が欠けているならば削除することを繰り返し、最後に残る頂点があるかどうかで判定しましょう。
この時、直前に消した頂点に隣接する頂点以外は調べる必要が無いことを利用すると、計算量は ${\rm O}(N+M)$ で解けます。

D - Modulo Matrix

まず、一番厳しい制約条件は余りの条件なので、ここを何とかしたいです。
そこで、仮に余りを決め打ってしまいましょう。
その時、あるマスについて、周囲4マスの最小公倍数+ $m$ にしておけば、答えになりそうです。
周囲4マスより $m$ が大きいと意味がないので、 $m=1$ にでもしましょう。
さて、後は周囲4マスをどう決めるかですが、全部が素数ならば最小公倍数の計算で楽ができそうなのでそうします。
ということは、素数のマスと最小公倍数+1のマスができるので、市松模様にすることを考えます。
以下、市松模様を黒と白で塗り分け、黒が素数とします。
この時、 $N$ 番目までの素数を用意しておけば黒マスは $N^2$ 個しかなく、相異なる素数の積は互いに相異なるので問題なく敷き詰められそうです。
構築問題である以上ロジックは楽をしたいので、左上から右下に斜めに通る線と右上から左下に斜めに通る線を考え、それぞれに相異なる素数を割り当てます。
この時、線の個数は高々 $2N$ 個であり、素数も $2N$ 個ほど求めておけば問題ないです。
また、この時に $(x, y)$ の座標に入る素数を考えると、 $x+y$ が偶数の時のみ素数を入れる時、 $N + \frac{x+y}{2}$ 番目の素数と $\frac{N}{2} + \frac{y - x}{2}$ 番目の素数を掛け合わせるようにするとまさに条件を満たします。
また、 $x+y$ が奇数の時は左右の合成数の積+1を求めれば問題なく計算でき、これは制約条件も満たします。