403.1

今回も500から開始、でも500だけお亡くなりになりました。Petrに25点あげてしまった。

250

A以上B以下の整数で、各桁の数字が4ないし7のものの数を答えよ、という問題。

AからBまでループ回して検査して、とやってはいけません、というだけの問題。ちゃんと4ないし7からなるAとBの可能な範囲の数を全部作ってから、判定しましょう。

500

各桁の数字が4ないし7からなる数字を使って、N個の配列を作る。i番目の最後の桁とi+1番目の最初の桁が同じになるものの数を求めよ、という問題。

(4|7)で終わって(4|7)で始まるものの4パターンから、遷移行列が作成できるので、N回遷移後(つまり行列のN乗)から各配列パターンの個数が求まる。これを精度に気をつけながらやりましょう、という問題。

行列乗算のところと、最後に結果を計算するための加算の部分がそれで、後者を忘れましたよ、と。

1000

ある整数Nを、各桁が4もしくは7からなる数の和に分解方法のうち、一番分回数が少なくて、辞書順で最初のものを答えよ、という問題。

取り敢えず必要な分解要素数でループします。そして一番下の桁の値の分布を計算します。4と7をそれぞれいくつ使うか、その和は必要な値の最後の桁を実現するか、という点に注意します。できるだけ4を多く使うようにしないといけないのと、それ以前に4と7を使う数を少なくしないといけない(これは辞書順で最初のものを取得するため)という2点に注意しながら、うまくいかないものを実現する数と使える要素数をメモしながら計算します。最初にうまくいったものが辞書順で先頭のものになるので、それを返せばおしまい。

実は、使える要素数が決まっているときに、4と7の使う数の和が少ないものから順にやるまでは良かったものの、4の数が少ない方から計算しているので、もしそういうケースがあったらダメだったっぽい。(少なくともシステムテストには)たまたまなかったので通りました。

そして多分正解は別にあるんだろうなぁ、という気もします。