A - No Attacking Editorial
by
Nyaan
Editorial for printing
ルークを \((i, j)\) に置くと \(i\) 行目と \(j\) 列目に駒を置くことが禁止されます。よってルークを \(N\) 個置いた時点で全てのマスに駒を置けなくなるので、\(A \gt N\) の場合は答えは No です。
\(A \leq N\) の場合を考えます。ルークを \(A\) 個うまく置いたときに、ポーンを \(1\) 列につき最大何個置けるかを考えてみます。
まず、ルークの置かれた行にポーンは置けないことから、上界の 1 つとして \(N - A\) 個が挙げられます。
また、\(1\) 行目を除く位置にポーンを \(1\) 個置くごとに、その上のマスにポーンを置くことが出来なくなるため、\(2\) マス駒を置けないマスが増えることになります。ここからもう 1 つの上界として \(\left \lfloor \frac{N + 1}{2} \right \rfloor\) 個を導出できます。
以上より上界として \(\min(N - A, \left \lfloor \frac{N + 1}{2} \right \rfloor)\) 個 (これを \(C\) 個と置きます) を得ることが出来ました。逆に、次のようにルークとポーンを配置することで、\(1\) 列につき \(C\) 個ポーンを配置することが出来ます。
- ルークを \(2\) 行目、\(4\) 行目、\(\dots\) と偶数行目に置いていく。ルークが偶数行目全てに置いても余っていたら、\(1\) 行目、\(3\) 行目、\(\dots\) と奇数行目に置いていく。
- 次に、ポーンを奇数行目のうち置ける行に置いていく。
ポーンを置ける列は \(N - A\) 列あるので、ポーンは最大で \((N - A) \times C\) 個置けることになります。よって、\((N - A) \times C \geq B\) ならば答えは Yes 、そうでない場合は答えは No になります。
計算量はテストケースあたり \(\mathrm{O}(1)\) で十分高速です。
posted:
last update:
