隣接2桁が3の倍数にならないN桁の3の倍数の数え方と解説

この問題では、N桁の正の整数で3の倍数でありながら、隣り合う2桁の数字がいずれも3の倍数にならない数を求める条件付き計数の考え方を学びます。

問題の条件整理

条件を整理すると以下の通りです。

まず、3の倍数の性質と2桁の数字の3の倍数条件を理解しておくことが重要です。

任意の整数が3の倍数であるための条件は、各桁の和が3の倍数になることです。

したがって、N桁の数字をd₁d₂…d_Nとしたとき、Σd_i ≡ 0 (mod 3) が成立する必要があります。

2桁の数字ABが3の倍数になるのは、A+B ≡ 0 (mod 3) のときです。

よって隣接する数字の組(d_i,d_i+1)は(d_i+d_i+1) mod 3 ≠ 0でなければなりません。

この条件を満たす数列を構築するためには、各桁のmod3の余りを考えて数列を列挙するのが有効です。

各桁の数字をmod3で分類すると、0,1,2の3種類に分けられます。

隣接する桁の和が0 mod3にならないようにするには、隣接する余りの組み合わせとしては以下が可能です。

このように、隣接余りが0にならないように数列を制限していきます。

一般的にはN桁の数列を数える場合、動的計画法(DP)が有効です。

状態をdp[i][r]とし、i桁目まで決めたときの3での余りがrの数を保持します。

遷移は隣接余りの条件に従って更新します。

最終的にdp[N][0]がN桁の3の倍数かつ隣接2桁が3の倍数でない数の総数になります。

十の位が0の場合、2桁としてカウントしないので、0の数字が続く場合は特別処理が必要です。

通常のDPにおいて、d_i=0の場合に隣接チェックをスキップするか、0を除いた数字で遷移させる方法があります。

本問題は条件付きの数列構築とmod3による余りの管理を組み合わせた組合せ問題です。

ポイントは次の通りです。

この方法を理解すれば、N桁任意の値に対して条件を満たす数の総数を計算できます。