2022-03-02 アルゴリズムと数学演習問題集 064, 065 を解いた

アルゴリズムと数学演習問題集 064 - All Zero を解いた。

数列の要素に対して +1 or -1 する操作をちょうど K 回してすべての要素を 0 にできるか。各要素を 0 にしたあと残った回数を +1, -1, ... の繰り返しで消費できれば良い。偶数回残れば良い。

数列の総和 S が S > K の場合はすべての要素を 0 にはできない。 S <= K の場合は K - S した残りを 2 で割った余りが 0 ならできる。

ぼくは実装としては S と K の偶奇が一致するかで判定した。

考察はどことなく 058 - Move on Squares 1 (2022-02-28) と似ている。

アルゴリズムと数学演習問題集 065 - Bishop を解いた。

H 行 W 列のマスからなる盤面で左上のマスに将棋の角 (chess の bishop) の動きをするコマがある。このコマが動けるマスの数はいくつかを求める。

まず H または W が 1 の場合は移動できないため最初に居るマスのみの 1 。そうでないときは約 H * W / 2 個のマスに移動できる。 H と W が奇数・偶数のときの例を調べて数を数えると切り上げにしておくと良さそうだ。 (H * W + 1) / 2 で切り上げは計算できる。

今日のコミット。