[Ruby] AtCoder 過去問 B-Bishop

はじめに

AtCoder過去問のB問題、Bishopを解いてみました。

この問題を解くときに、最初に浮かんだのはfor文やtimesメソッドを用いて繰り返し処理をすることでした。しかしながら、数字が大きくなれば処理に膨大な時間がかかってしまい、アウトになってしまったので、他のやり方を試行錯誤してようやく解けました。

問題はこちらから確認してください。↓

よろしくお願いします。

B-Bishop

まず、はじめに入力の受け取りをします。

H, W = gets.split(' ').map(&:to_i)

考え方としては、一番左上に存在する角行が移動可能な最大のマスの数を出力せよ、ということで盤上のマスの数は入力値によって変動するようになっています。

まずはじめに、縦 × 横が盤上全体のマスの数になるので受け取った数値をかけたものを変数に入れておきましょう。後で使います。マスのことをcellと表現していいのかわかりませんが、、、

H, W = gets.split(' ').map(&:to_i)
total_cell = H * W

ここからはif文を使って条件分岐していくのですが、これから分岐する条件(後述します)の中にイレギュラーがあるので最初にその条件の振る舞いを書いてあげます。

それは縦もしくは横のマスが1マスしかない場合、斜めにしか動けない角行は、動きようがないということです。
ですので角行が存在できるマスは最初に位置している1マスだけになります。
下記のように書きます。

H, W = gets.split(' ').map(&:to_i)
total_cell = H * W

if H == 1 || W == 1
  answer = 1

イレギュラーの条件は最初に処理するように記述したので、あとはある共通の法則で分岐をすればOKです。

その法則とは、角行が一番左上がスタートであり、盤上のマスが偶数であれば単純に全部の数のちょうど半分のマスを角行は動くことができます。

つまりHかWのどちらかが偶数であれば、全部のマスの半分が答えの数になります。

H, W = gets.split(' ').map(&:to_i)
total_cell = H * W

if H == 1 || W == 1
  answer = 1
elsif H % 2 == 0 || W % 2 == 0
  answer = total_cell / 2

そして残るはそれ以外、つまりHもWも奇数で盤上のマスが奇数の場合です。
例えば縦3マス横3マスであれば9マスです。
紙に書くと非常にわかりやすいですが、この場合角行が動けるマスは5になります。

盤上のマスが奇数の場合は、その数に1足して、2で割ると答えが出ます。

H, W = gets.split(' ').map(&:to_i)
total_cell = H * W

if H == 1 || W == 1
  answer = 1
elsif H % 2 == 0 || W % 2 == 0
  answer = total_cell / 2
else
  answer = (total_cell + 1) / 2
end

puts answer

これで完了。

終わりに

はじめは、繰り返し処理を使ってfor文でぶん回していましたが、入力例3(冒頭の問題URLで確認してください)のような大きな数字が来るとかなり処理が重くなります。その結果、時間オーバーでアウトになってしまいました。

頭を柔らかく、ある法則を見つけ出して、できるだけシンプルに書くことが重要なんですね。