読者です 読者をやめる 読者になる 読者になる

pekempeyのブログ

競技プログラミングに関する話題を書いていきます。

Codeforces Round #341 (Div. 2) B. Wet Shark and Bishops

もうすぐ期末試験。

codeforces.com

問題概要

1000x1000 のチェス盤の上に n 個のビショップが置かれている。 通常のビショップとは異なり駒を飛び越えることもできる。 互いに取られる位置にあるビショップの対はいくつあるか。

解法

ビショップは将棋の角と同じで、斜め 4 方向に遮るものがない限り進める。ただし今回は遮るものがあるかは考えなくても良い。

互いに取られる位置にあるビショップというのは、x+y が等しいか x-y が等しいかのどちらか一方である。 ゆえに求める場合の数は次の総和になる。

  • x+y が等しいビショップから 2 つ選ぶ場合の数
  • x-y が等しいビショップから 2 つ選ぶ場合の数

配列だと負のインデックスの扱いが面倒なので map を使った。

Codeforces Round #341 (Div. 2) B. Wet Shark and Bi ...

間に駒があっても大丈夫なのは直感に反する。