【ポケモン剣盾？】ハイドロポンプの略称を全部列挙する【プンポロドイハ】
諸悪の根源
『ポケットモンスター』縮めて、ポケモン#ハイドロポンプ 縮めて、ハイポン❓ドロポン❓ハインプ❓イドポプ❓ pic.twitter.com/emT4Gl3LVj
— 【公式】ポケモン情報局 (@poke_times) June 15, 2020
私はドロポン派です。
ポケモン公式が「ハイドロポンプの略称」という俗っぽい話題に言及したことで、Twitter各所でハイドロポンプの略称が話題に上がるようになりました。古来から各派閥に分かれて血を血で洗う争いが続いていたので、公式の爆弾投下によってTwitterが戦場にならないか心配ですね。ドロポン以外ならプンポロドイハが好きです。ドッヘンアイアも好きです。
そのような流れの中で、下のようなツイートを見かけました。
Q.ハイドロポンプの略し方、何通りあるか答えよ。ただし、略した名称は6文字以下とし、｢ハイドロポンプ｣は含まないものとする。
— @SUR(する) (@porigon865885) June 15, 2020
っていう数Ⅲの問題。
各文字を含めるか含めないかで考えれば=128、空文字と「ハイドロポンプ」は含めないので答えは128 - 2 = 126通りです。(数Aでは…？)
さて、これをもう少し改変して次のような問題を考えてみます。
「ハイドロポンプ」の1文字以上6文字以下の略称を「ハイドロポンプ」辞書順に全て列挙せよ。
— ARROWTUNA (@sub_827) June 15, 2020
ただし『略称』とは『ハイドロポンプ』の順序を保った部分文字列を指す。
定期テストで出てきたらめちゃくちゃ時間食われるのでスルー安定です…。
人力で126通り書き上げるのはとても大変ですが、コンピュータに任せればサクッとやってくれます。
……ホンマか？
言っておいて簡単じゃなかったら困るので自分で解いてみました。
できた pic.twitter.com/82p5lIck0O
— ARROWTUNA (@sub_827) June 15, 2020
(ちょっと難しかったです…)
「各文字について入れる/入れないで分岐して126通りの文字列を作った後ソートする」という方針だと「ソートする」の部分が少し厄介です。私は幅優先探索で解いてみました。
最後に
7文字入っちゃってるじゃん。
— ハャ卜(お父さん犬) (@PaintDoble) June 15, 2020
問題の条件には気を付けましょう。
追記
アイアンヘッドの略称の列挙は「ア」が2個含まれているので、もう少し難易度が上がります。誰か挑戦してみませんか？
追記2
フォロワーさんから「再帰で書いた方が速かった」と刺されたので考え直してみましたが、深さ優先で解くべき問題でしたね。再帰ではなくStackを使って書いてみました。文字の追加の順番が逆になるので注意が必要です。
計測結果
