第11回日本情報オリンピック　予選６

2011年12月23日
情報オリンピック日本委員会

解説

単純な解法として，A 以上 B 以下のすべての M の倍数について，それがジグザグ数であるか否かを判定するという方法が考えられる．しかし，B - A は非常に大きくなり得るので，この方法ではほとんどのデータに対して時間がかかりすぎてしまう．

この問題は，動的計画法あるいはメモ化再帰によって解くことができる．上の桁の方から確定させていくときに，「A 以上 B 以下かつ M の倍数かつジグザグ数」となるように残りの桁を決める方法は何通りあるか，を求めるために必要な情報を整理することが求められる．

(A 以上 B 以下の M の倍数のうちジグザグ数の個数) = (1 以上 B 以下の M の倍数のうちジグザグ数の個数) - (1 以上 A - 1 以下の M の倍数のうちジグザグ数の個数) であることに注目すると，「A 以上 B 以下」の条件の代わりに「1 以上 X 以下」として問題を解けばよいことがわかる．

動的計画法あるいはメモ化再帰の「状態」として，

• 現在，上から a 桁目まで決めている．
• 現在の上 a 桁の値を M で割った余りは b である．
• a 桁目は c である．
• a 桁目は a - 1 桁目から増加しているか (d = 0) 減少しているか (d = 1)．
• 現在の上 a 桁は X の上 a 桁と一致しているか (e = 0) 否か (e = 1)．

という情報 (a, b, c, d, e) を持っておけば，残りの桁を決めて M の倍数のジグザグ数になるかどうかを考えるのに十分である．最大で，およそ a は 500 通り，b は 500 通り，c は 10 通り，d は 2 通り，e は 2 通りであり，各状態に対して次の桁の決め方が高々 10 通りであるため，十分短い時間で計算を終えることができる．

細かい境界条件は複雑であるため，十分に注意する必要がある．単純な解法も実装し，答えを比較しながらデバッグを行うのも良いだろう．