公式

A - No Attacking 解説 by Nyaan


ルークを \((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)\) で十分高速です。

投稿日時:
最終更新: