ARC136 D問題をRuby(NArray)で計算 - Qiita

例えば 41 に足して繰り上がりの起きない数は [31, 41, 26, 53, 58, 23] の6つです。というのも、これらは 99 - 41 == 58 よりも 各桁で数字が小さい（または同じ） ためです。 また、例えば「 53 が繰り上がりを起こさないなら [23, 31, 41] も起こさない」ということが言えます。そのためより大きな数値にはその下の情報も合算しておくのが良さそうです。今回の場合は累積和で簡単に作れます。 ある数 s よりも各桁で数字が小さい（または同じ）要素数を表にしてみます。各桁は別々に考えられるので、桁数ぶんの多次元配列を作ればいいです。 #--- aの要素数を各桁の数字別にカウント ---# Numo::UInt32#shape=[10,10] [[0, 0, 0, 0, 0, 0, 0, 0, 0, 0], [0, 0, 0, 0, 0, 0, 0, 0