F - Numbered Checker 解説 by ryoryoryo111
以下のグリッドの和を求めることを考えてみます。
1 0 3 0
0 6 0 8
9 0 11 0
0 14 0 16
17 0 19 0
奇数行のゼロでないグリッドを抜き出すと、
1 3
9 11
17 19
となります。以下ではこのグリッドを元グリッドと呼び、この合計値を求め、偶数行については別途考えることとします。 元グリッド全体の平均値が求まれば、元グリッドのマス数に書かれている数字の和は (平均値) x (元グリッドのマス数)で求めることができます。
さて、元グリッド全体の平均値をO(1)で求めるためにはどのように計算すればよいでしょうか? まず各行の平均値を求めてみましょう。初項a、末項l、項数nの等差数列の和はn(a + l)/2であることから、平均値は(a + l) / 2であることがわかります。
3 5 7 9
の場合だと、(3 + 9) / 2 = 6が平均値です。
次に各行の平均値の平均値ですが、
2
10
18
で見ていくと、やはりこれも等差数列になっているため、(a + l) / 2で求めることができます。この例だと(2 + 18) / 2 = 10が平均値であり、これが元グリッド全体の平均値です。
結局、元グリッドの左上、右上、左下、右下の4つのマスの数字の平均値がグリッド全体の平均値となります。
さらに言うと(元グリッドの左上の数字) +(元グリッドの 右下の数字) = (元グリッドの右上の数字) +(元グリッドの 左下の数字) が成立するため、元グリッド全体の平均値は(元グリッドの左上の数字)+(元グリッドの右下の数字) / 2で求めることができます。
上記のグリッドの例で言えば(1 + 19) / 2 = 10が平均値です。この性質はどのような元グリッドでも成立します。
左上と右下のマスがどこにあたるかはmod2に気をつけながら求めれば、元グリッドのマス数を求めることができます。さらに定義どおり左上と右下の値を計算することで、元グリッド全体の平均値を求めることができます。
同様の議論は偶数行についても成立するので、それらの合計が答えです。
実装例(Rust)
投稿日時:
最終更新: