Sを並び替えて有り得る組み合わせの中で、Kの長さの回文を含まない組み合わせの数を答える問題。
で、その列挙のためのC++やPythonにあるnext_permutationはどこ？ というのがC#で解くにあたって最も困難な部分。
これが使用する言語に関数などとして用意されているかで難易度がわりと変わってくる問題。残念ながらC#は用意されてない側の言語なので、自ら実装する必要がある。
制約的に全探索でいけそう、ということと並び替えて得られる文字列の探索とはどういうことなのか、どういう風に実装するものなのかが分かってないとその場その時に調べたとて分かりようもない。私は無理でした。
解説
Sを並び替えて得られる文字列は、Sを昇順に並び替えた上で次の順列を探索するコードを書けば全探索ができる。そして、制約的に全探索で十分問題が無さそう。
その上で回文かどうかを判定してインクリメントしていく。
以上の2点のみ。
C#で実装するnext_permutationの解説（備忘録）はすぐ下の記事からどうぞ。
文字列の場合でも昇順に並び替えは可能なのでそこは問題なし。文字コード的にアルファベットの中では大文字の「A」が一番小さくその次に「Z」が大きく、その次が小文字の「a」、最後は小文字の「z」が一番大きい。
この問題には関係ないが、日本語のひらがなやカタカナを昇順に並び替える場合も同じタイプの配列になっているので、人間が辞書順に並び替える時と同様の手順を踏むことができる。漢字は不可。
次に回文の判定。これはC問題に挑戦する程度の実力があるなら時間が掛かっても実装できるはずなので省略。
回文の判定であれば整数/2の切り捨て部分を考慮しなくても良かったかもしれない。ここで起こり得る切り捨ては割られる数が奇数のみかつ余りが1に限られるし、奇数の回文の頂点となる1文字は回文かどうかの判定に影響を及ぼすとは思えないし……。だからforの条件式はj<k/2で十分なはず。
感想
next_permutationの実装が一番難しかった。概念をちゃんと理解してないと問題毎にコードを合わせ難いので、理解した上で実装する手順を踏もうと考えて気付けば1年半も掛かってしまった。あーもー。
長さKの回文の判定は添え字が少し面倒なので、各自で決まった構文を事前に書いておいたり、特に添え字はそういうものとして覚えておく。大抵の場合で使うことになるであろうiとjと回文の長さであるkにそれぞれ意味があり、蓋然性があるので。ちゃんと手を動かして理解しておけば困らない。
しっかりと手と頭に覚え込ませていこう……。
コメント