Xmas Contest 2018 B: Bit Smaller 解説

https://atcoder.jp/contests/xmascon18/tasks/xmascon18_b

問題概要

とか， とか，そういうののうち 以下のものをすべて求めよ．

解法 1

全探索しましょう．数の切り方は高々 通りしかないのでなんとかなると思います．

先頭のほうから切っていく感じで再帰で実装するのもよいと思います．

枝刈りとかがんばらない限りは実行にそれなりに時間がかかりますが (わたしのは数分でした)，答えだけ出せばいいので安心．

たちの積を求めていくより で 回割っていく，みたいなののほうがオーバーフローを気にせずに済んで枝も刈れていろいろお得かも (ただし に注意)．

解法 2

https://oeis.org/A096298

親切にもふたつめの答えまで書いてあるので OEIS で検索すると見つかります．が，

• "not ending with 0" と書いてあるように，条件を満たす数の末尾に をつけてもやはり条件を満たす
• 切り分けたときに が入っていたり で始まっていたりそういうのも含まれている

ことに注意してください．

コメント

面白算数 (?) ネタを見つけたので易しめの問題にしてみました．作問陣は OEIS で検索するのをすっかりさぼっていたのですが，微妙に条件が違って逆にトラップになってたようで面白いですね．

この問題の範囲では一の位が (か ) の解しかないですが，他がないわけではないです (問題概要のとこの例とか)．

みたいに最後の部分がないパターンも綺麗ですが，探索で見つかる範囲だと全然ないようです．桁を増やせば，例えば とかがあります (見た目がやばいですがこうやって構成されています： https://math.stackexchange.com/a/2126667)．