ABC114-C
自力では解けなかったのでカンニングした。
考えたこと
- 375とか537とかの753数の頭に3,7,5のどれかを付け足すと簡単にできそう。
- いや、3557も753数。ベースとなる数字が753数とは限らない。
- とりあえず3,5,7を適当に並べた数字を作るか。でもその方法が分からない。
- ここで解説をカンニング。深さ優先探索を用いて再帰的に0に3,5,7をくっつけていって753数か確認、Nを超えるとそれより深いところの探索停止みたいな形になっていることは分かった。
- しかし、「こんなん俺が思いつけるわけないやん」とおもった。
- 別の解法をググった。(https://naoyat.hatenablog.jp/entry/ABC114)@naoya_t様、参考にさせていただきました。ありがとうございます!。
- C++だったのでpythonにした。
学んだ/思ったこと
- あるデータについて次のループというかステップでそいつを使いたい場合、キューを上手に使う。キューから取り出して処理、キューの後ろに追加の流れ。キュー自体は知っていたし、使ったこともあったが、3,5,7の適当な並びを作るのにキューを使うのは思いつかなかった。
- 0に数字足していって3,5,7の数字作る処理の流れ自分では思いつかなかったので結構感動した。
- 再帰は再帰停止条件とかいろいろ考えなければならないので、使いこなすには比較的簡単な問題をそれなりに数こなして訓練する必要がありそう
- 思いつかないものは思いつかないので、いくらか時間をかけて解けないならスパッとあきらめて数こなす方が実力/経験値向上には役に立つ。が、粘り強く考えるコンテストに必要な力はつかないので困りもの。
下記回答は@naoya_t様の回答を私のショボい力でpyrhon化したものです。私の実力ではありません。