第19回日本情報オリンピック　二次予選

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

解説

小課題1

小課題 1 では， JOI 君が入力すべき整数は 100000 × n + R (n は0以上の整数)の形で表すことができる．

このような整数の下 5 桁は R で固定されているため，操作回数を最小化するためには R を入力するのが最適であることがわかる．

R を入力するのに必要な操作の回数を計算するには， R の各桁について，「その数字が印字されているキーまで移動し，キーを押す」ために必要な操作の数をそれぞれ計算し，足し合わせればよい．

小課題2

答えは最大で 30 になり，操作の種類は 2 ~ 5 通りあるので，単純な全探索では時間内に答えを出すことができない．

そこで，状態をまとめることを考える． 具体的には，(カーソルの位置，入力した数字を M で割った余り) の組を状態とする． このとき求めるべきものは，カーソルの位置が 0 ，余りが 0 である状態から，余りが R である状態にするために必要な最小の操作回数である．

これは，それぞれの状態を頂点とし，可能な操作に対応した辺を張ったグラフ上で，幅優先探索を用いて最短経路を計算することで求めることができる． 状態数は O(M) ，それぞれの状態で可能な操作は O(1) 通りであるので，上記のグラフの辺数は O(M) となる． よって幅優先探索は O(M) で実行でき，これは全てのケースを正解するのに十分高速である．