AtCoderを退会するための問題、の元ネタは以下のツイートです。
twitter.com本当に退会しますか？
— chokudai(高橋 直大)🍆🍡🌸 (@chokudai) May 28, 2019
※botではないことの確認のため、以下の問題を解き、ソースコードを提出してください。
問題文
K の正の倍数の 10 進法での各桁の和としてありうる最小の値を求めてください。
制約
2≤K≤100,000
K は整数である
[コードを提出して退会する]
どうやらこの問題はAtCoder Regular Contest (ARC) 084のD問題「Small Multiple」として出題されたことのある、過去問のようです（併設のBeginner Contest (ABC) 077のD問題でもあります）。
この問題を自力で解いた提出が以下になります。ABC側に提出しましたが、このような併設開催だったコンテストの過去問の場合、どれに提出するのが一般的なんでしょう……？
Submission #5698661 - AtCoder Beginner Contest 077 | AtCoder
私の提出した解法は、他の提出とは異なる解法のようです。 というかあまりにもdouble ended queue (deque)による0-1BFS*1を用いた解法ばかりです。 どうやらコンテストの解説資料がこの解法によるものになっているようです。 つまり、最近の提出は「過去問演習で解けなかったので解説を見てから提出」というパターンで提出されたものなので、こういう提出ばかりになったものと思われます。
……と思っていたら、コンテスト中に提出された解法もほぼすべてが似た解法でした。さすがに洗練された0-1BFSではなく、単なるBFS（幅優先探索）やDFS（深さ優先探索）によるものもありますが、グラフの構築法は同じです。
こういう解き方もあるんだよという啓発になればと思って記事を書きます。
目次的なもの
以下の節は思考の垂れ流しなので、アルゴリズムを知りたい場合は読まなくてよいです。 ただ、「なんでこんな発想に至ったのか」ということを知る方法はあまりないので、参考にしたいことがあるかと思い一応書いておきます。
着想に至った経緯
お風呂に入っていたら思いつきました。
問題文を見てからの思考
- なるほど、7なら1001だから2と答える感じかぁ
- すごく大きなKの倍数が1000....0001の形になるかを判断するのは難しそう
- 2n 5m の形なら1が答えになる
- 2n 5m K の形なら、Kの答えと同じになる
- もしかして2n 5m 以外だと全部1000...0001の形にできて2が答えになるのかな
- これは間違い、例えばK=3だと3が答えになる
- 3の倍数だけ特殊扱いすればいいのかな……？*2
- Kは小さいので、指数時間アルゴリズムを用いてよい（※入力長log Kに対しての指数時間アルゴリズムが通るという話であって、Ο(2K)が通るという話ではないです）
- お風呂入ろう
お風呂での思考
- 素因数分解する問題ではなさそう
- そもそも、大きな素数に対してどう解けばいいのか不明
- 具体的に構成する方法がありそう
- 根拠なし
- まず7の時にどうやって1001にたどり着くかを考えよう
- KのT倍について考える
- Mの1の位から考えていく
- 1001にたどり着く場合、7×3=21を最初に選んだわけで、Tの1の位は3
- つまり、1倍～9倍のなかで1の位が小さくなるものを選べばよさそう
- もちろん、貪欲にやってうまくいくとは限らなさそう
- そうすると、10の位に2が余る
- ここで7×14=98を選べば、さっき余った2と合わせて100になって、十進法を用いたときに各桁の和が最小となる
- つまり、7の倍数+2の形をしたものについても十進法を用いたときに各桁の和が最小となるものを探せばよい
- 一般に、Kの倍数だけではなく、Kの倍数+rの形をしたものに対しても探せばよい
- rの作り方は一般に複数通りある*3ので、DPっぽい*4
- Tのu桁目tとしてあり得る0～9のすべてに対し、r+Ktを考えて、それを10で割った余りがKTのu桁目に対応
- 下の位から確定させていくとき、KTのu桁目を変えられるラストチャンスはTのt桁目の時
- KTを十進法で表したときの各桁の和は、確定した部分のみの和より少なくなることはあり得ない
- r+Kmを10で割って切り捨てたものが次のr
- rとしてあり得るのは0～K-1のK通り
- rに対応する頂点と、遷移（今のr→次のr）に対応する辺を考えると、頂点数K・辺数10Kの疎なグラフについての最短路問題となる
- 辺のコストとしてありえるのは0～9
- よって優先度付きキューを用いたdijkstra法のようなソートが必要な最短路アルゴリズムではなく、キューををたくさん用意する最短路アルゴリズムが使える
- 色々なダイクストラ高速化の20ページ目、「辺の長さが100以下とか→キューを101個用意しろ」
- お風呂出よう
ここまで20分くらいでした。紙とペンがあったらもっと早く思考をまとめられたのでしょうか……？
アルゴリズムの概略
スタート地点となる頂点からは9本の辺が出る。枝t(0<t<10)は頂点K*t/10への辺である。その辺のコスト（距離）は、K*t%10である。
頂点0はゴール地点である。その他の頂点rからは10本の辺が出る。枝t(0≦t<10)は頂点K*t/10への辺である。その辺のコストは、K*t%10である。
スタート地点からゴール地点への最短路長が求める答えである。
アルゴリズムの実装における工夫
- 辺のコストは0～9であるため、キューを10個用意する幅優先探索を行う。
- 実際に提出したコードでは、キューは再利用せず使い捨てている。その場合、キューは54個用意する必要がある。
- グラフをあらわに持つことはせず、その頂点を訪れたときにその場で生成する。
実装は35分くらいかかりました。もっと早く書けるようになりたいなぁ……。
提出ソースコードの解説
キューとして何を用いるべきか
キューの挿入される回数の上限値が事前にわかっているため、static_vectorが最適です。検討した他のコンテナは以下の通りです。
std::vectorは、push_backするとイテレータが無効になるため注意が必要です。必要な量が前もってわかるため事前に確保しておけば問題ないですが、確保量を間違えた場合に危険です。- 必要な容量はKです。
std::dequeは、危険性はありません。しかし、事前に確保できないため複数回newが走り、遅いです。std::queueは、普通は内部実装がstd::dequeです。std::listは、毎回newが走り、非常に遅いです。
まぁそこまで遅いアルゴリズムではないので、std::queueを使っても問題にはならないでしょう。
range-based-forを使わない理由
途中でendイテレータが変更されるためです。range-based-forは最初に一回だけend( Container )を評価します。そのため、ループの中でその後にpush_backをしてendイテレータが変更されても、ループ開始前にキューに入っていたものしか取り出されません。
「距離0」が存在するような幅優先探索に用いるキューを取り扱うためには不適です。
最短路を求める方法
q.at( cost ).push_back( rem )により、「頂点remへたどり着くためのコストは、costである」ことを記憶します。
今の頂点rにたどり着くのに必要なコストがiである場合、q.at( i + cost ).push_back( rem )により、「頂点remへたどり着くためのコストは、i + costである」ことを記憶します。
これは正確には「頂点rを直前に通って、頂点remへたどり着くまでのコスト」なので、他の行き方がある可能性が残されます。
例えば、頂点0にたどり着けるとしても、その行き方が最短路ではなく、他の行き方だともっと低コストでたどり着ける可能性が残されています。
よって、枝を張る部分（内側のfor文）でrem == 0の時にi + costを出力するのでは間違いです。
このキューをコストの低いほうから順にみていけば、ある頂点rを初めて訪れた（visited.at( r ) == false）時、その時のコストiが頂点rにたどり着くための最低コストになっています。
頂点0であればゴール地点にたどり着いたので、コストを出力して終了です。
頂点0以外であれば探索を進めます。
頂点への二回目以降の訪問は、遠回りをして到着した場合なので、その先に探索を進める必要はありません。
どこまで探索すればよいか
求めるべき答えは、Kを十進法で表したときの各桁の和以下であることが明らかです。
K=99999の場合が最も大きく、その値は45です。
よって、iは0～45の範囲を探索すればよいです。
キューは何個用意すればよいか
i = 45の場合、必ず答えが出力される（つまり終了する）ことが保証されています。
よって内側のfor文に入る時、iは最大で44です。
costは最大で9なので、q.at( 53 )へのアクセスがあり得ます。
それ以上はあり得ないので、キューは54個用意すれば十分です。
実際には、同時に使われるキューの数は10個であり、使い捨てずに節約することが可能です。
想定解法との違い
想定解法の速い実装としては、準急くきさんの提出Submission #1742945 - AtCoder Regular Contest 084 | AtCoderがわかりやすいでしょうか。
アルゴリズムの違い
考えているグラフの違い
実は考えているグラフはほとんど同じものです。 想定解法では×10, +1の二種類だけを用いたグラフです。そうではなく、×10, +1, +2, +3, +4, +5, +6, +7, +8, +9の十種類の辺を用いたグラフとすれば私の解法と同じグラフになります。 繰り上がりの部分で余計なことを考えなくてよいので、十種類の辺を用いたグラフを考えるのも自然です。
辺の向きの違い
想定解法と私の解法では以下の点が異なります。
- スタート地点とゴール地点が入れ替わっている。
- 有向辺の向きが逆向きになっている。
この違いは、構築を上位桁から行うか、下位桁から行うかに対応しているようです。
想定解法では、上位桁から求めていっています（10倍する操作は、考える桁を一つ下に移動することに対応します）。 私の解法では、下位桁から求めていっています（10で割る操作は、考える桁を一つ上に移動することに対応します）。
下位桁から構築するのもそんなに不自然ではないと思うのですが、競技プログラマーのほとんどが想定解法で解いているようで、不思議です。 「十進法で表したときの各桁の和」に対する典型解法だったのでしょうか……？
辺を構築しやすいか
想定解法では、辺がどの頂点とどの頂点を結んでいるか、その辺のコストはいくらか、がほぼ自明です。 私の解法では、そんなに自明ではありません。
計算量
この手のBFSの正しい時間計算量
想定解法は0-1BFSにより時間計算量Θ(K)で解けるとしています。 競技プログラミングの文脈では正しいのかもしれませんが、計算量理論的にはこれは誤りです。 なぜなら、キューの一エントリは0～K-1を格納するためにΘ(log K)ビット必要で、それがΘ(K)エントリ必要ならば空間計算量はΘ(K log K)となるからです。 空間計算量より時間計算量が小さいことはあり得ませんから、0-1BFSを用いたところでΘ(K log K)であることには変わりません。
私の解法も、同様の理由により時間計算量Θ(K log K)の解法です。
なお、普通の優先度付きキューを用いたDijkstra法の時間計算量は同様の理由により時間計算量Θ(K (log K)2)となるので、それよりオーダーとして高速なアルゴリズムだという点は間違いではありません。 Radix Heapを用いた場合は、時間計算量Θ(K log K log log K)になります。
mod Kの存在
想定解法では、10倍してmod Kをとる操作があります。 私の解法では、mod 10をとる操作があります。
一般に、変数による剰余は低速です。最近のIntel CPUだと26サイクルかかるようです。 一方、定数による剰余は乗算命令とシフト命令に最適化されるため、高速です。
私の解法ではK*tを求める部分がありますが、これは誘導変数*5であり、乗算は不要です。
実際、最近のコンパイラはこの最適化を行ってくれるようです。
一頂点からでる辺の本数
想定解法では2本であり、私の解法では10本です。
この違いは大きいようで、私の解法は想定解法より3倍程度遅いです。
おわりに
こういう問題、競技プログラミングの問題として出される（＝高速な解法があることが保証される）から解けるけれど、そういうメタな情報が無かったら愚直に探す解法しか思いつけなかったような気がします。 それでも、答えを見ずに解けたときはうれしいです。 それが独自の解法であったときは特にそうです。
あと、AtCoderを退会できるくらいの実力があることはわかったので、少し自信がついたかもしれません。
