AtCoderログ：0086 - パナソニックプログラミングコンテスト2020 B

問題

問題文

縦 $H$ マス、横 $W$ マスの盤面があります。 この盤面の左上隅のマスに角行の駒が置かれています。 駒が $0$ 回以上の好きな回数の移動を繰り返して到達できるマス目は何個あるでしょうか？
ただし、角行の駒は斜めに動くものとします。 より厳密には、駒が上から
$r_1$ 番目、左から $c_1$ 番目のマスから上から $r_2$ 番目、左から $c_2$
番目のマス目に動ける条件は
・$r_1+c_1=r_2+c_2$
・$r_1−c_1=r_2−c_2$
のうちちょうど一方が成立することです。

制約

・$1 \le H,W \le 10^9$
・入力は全て整数である。

収録されている問題セット

• [BfB-E](AtCoder Problems Boot camp for beginners Easy 100) #006

回答

回答1 (AC)

駒は斜めに移動するので、$H$ または $W$ が偶数ならば駒はマス目のちょうど半分のコマを移動することができ、到達できるマス目の数は $HW/2$ 個となります。また、$H$ も $W$ も奇数ならば、コマは半分より1個多いコマを移動することができるので、到達できるマス目の数は $(HW+1)/2$ 個となります。

これをコードにすれば良いと思いきや、これでは WA になってしまいます (なってしまいました)。これは $W=1$ または $H=1$ になっている場合を見落としていることが原因です。マス目が1行または1列の場合には、コマは全く移動できないことに気づく必要があるのです。この場合、到達できるマス目の数は $1$ 個であり、コードでは別扱いが必要があります (私はこの例外になかなか気づかず、WA を重ねてしまいました)。以上よりコードは次のようになります。

panasonic2020b-1.cpp

#include <bits/stdc++.h>
using namespace std;

int main() {
  int64_t h, w;
  cin >> h >> w;

  if ( h==1 || w==1 ) {
    cout << 1 << endl;
  } else if ( 'h*w)%2==0 ) {
    cout << h*w/2 << endl;
  } else {
    cout << (h*w+1)/2 << endl;
  }
}

調べたこと

AtCoder の解説 → ユーザ解説

回答1と同じ方針ですが、出力式は「(h*w+1)/2」にまとめられるとのことでした。

AtCoder の解説 → コンテスト全体の解説

回答1と同じ方針です。

リンク

前後の記事

• 前の記事 → AtCoderログ：0085 - ABC 049 C
• 次の記事 → AtCoderログ：0087 - AGC 013 A