- Quiz
- Submit
- その他
- 他の人の解答を見ていたら、ダイクストラをライブラリで持っていて適用して解いている人が多かった
- 発想
- 「桁の和」は、数字Xを作る時に1から出発して「＋１（コスト１）」「ｘ１０（コスト０）」で作った時のコストの和＋１である
- 例：123は、1->10★11★12->120★121★122★123（星部分がコスト１）
- よってコスト5で123に到達でき、桁和はそれ＋１の6で一致する
ポイント
- グラフ問題でとらえる
- 1を足すのはコスト1のエッジ
- 10倍するのはコスト0のエッジ
- 無限にノードがあるが、パターンからmod Kしてよいと気づく
- (というか、そういう性質がないと最適性が言えないので、あるはずと考えて探すのが良さそう）
01BFS
- 両端キューを使った幅優先探索。コストが0の時はqueueの左から入れ、コストが1の時は右から入れることでコスト0を優先して処理する
- エッジのコストが0, 1の時はこれで十分なのでこれで書いていこう
- コンテスト中に定型アルゴリズムを書くのは、理解した後に減らしていこう
- 参考にしたサイト：https://betrue12.hateblo.jp/entry/2018/12/08/000020
- 計算量 O(E)
- ダイクストラで間に合うならダイクストラを貼り付けてもいい
ノート
01BFS類題
- D - Wizard in Maze
- https://atcoder.jp/contests/abc176/tasks/abc176_d
- AC https://atcoder.jp/contests/abc176/submissions/16160474
- bfsってdistが未定義な時1度だけ書き換えればいいと思っていたけれどこの場合は違って、より短く更新できるなら書き換えるように書くべし
012BFS
- 2024/02/06
- chokudaiさんによると012BFSというのもあるらしい
