MENU

出題から約弐年…解った事のざっくりまとめ

概要

これです(雑)

domsblog.hatenablog.com

今回はほぼ数式だけです

前回の記事を覚えている人がいるかわかりませんが、かなり方向性が違うので全く違うものと思っていただけると

説明等は要望が出たかつ時間ができたらやります

 

わかったこと①(最短経路について)

※⌊ ⌋は床関数です

pページ目まで移動するとき

a=\left\lfloor\dfrac{p}{100}\right\rfloor
b=\left\lfloor\dfrac{p}{10}\right\rfloor-10\left\lfloor\dfrac{p}{100}\right\rfloor
c=p-10\left\lfloor\dfrac{p}{10}\right\rfloor
d=\left\lfloor\dfrac{b}{6}\right\rfloor+\left\lfloor\dfrac{c}{6}\right\rfloor\left(\left\lfloor\dfrac{b}{5}\right\rfloor-\left\lfloor\dfrac{b}{6}\right\rfloor\right)
e=\left\lfloor\dfrac{c}{6}\right\rfloor+\left\lfloor\dfrac{b}{6}\right\rfloor\left(\left\lfloor\dfrac{c}{5}\right\rfloor-\left\lfloor\dfrac{c}{6}\right\rfloor\right)

とすると、移動に必要なボタンを押す最小の合計回数R

R=a+d+\left|b+e-10d\right|+\left|c-10e\right|

となります

また、最短経路のうち1つの経路(最短経路が複数存在する場合がある)のそれぞれのボタンを押す回数は

±100のボタン: a+d (回)

±10のボタン  : b+e-10d (回)

±1のボタン    : c-10e (回)

です

値がマイナスになる場合はマイナスのボタンを押すという意味です

(例: ±10のボタンを-5回→-10のボタンを5回)

 

わかったこと②(ページ数について)

2つの値を受け取り小さいほうを返すmin関数を考えます

ボタンをc回押したときにたどりつける0~99ページ目までのページ数s_{c}

s_{c}=\displaystyle-\min(1,c)-\min\left(1,\left\lfloor\dfrac{c}{10}\right\rfloor\right)+\sum_{i=0}^{\min(5,c)}\{\min(6,c-i+1)\cdot\min(2,i+1)+\min(4,c-i)\cdot\min(2,i)\}

(複雑そうに見えますが手計算でも計算できる量です)となり、c回押したときにたどり着ける全てのページ数S

S=\displaystyle\sum_{j=0}^{c}s_{c-j}=\sum_{j=0}^{c}s_{j}

となります