難易度高めだったという噂の問題。実際難しかったと思います。個人的には期待値がおそろしく苦手なので、余計に大変でした。ですがなんとか回答できたので、そのコードをここにさらしておきます。
使用言語はRuby。1回目の提出で無事合格でした。
今回は問題そのものもそうでしたが、解法をわかりやすく文章にするのがなにより大変だったように思います。提出時に書いた説明をソースコードの下に載せていますが……時間を空けて読むとわかりづらい(苦笑)。やはり他人が理解しやすいよう文章を書くのは難しいですね。あと数学的な知識の不足。数学を専門に勉強していない文系の限界を感じます。もう少し数学的なことを知っていれば、今回の説明文もスマートに書けたはずです。
反省はそこそこに、解法について少し書いておきます。今回の問題は数字の並びを扱うという点で、いわば順列の問題です。しかし順列を扱うとなるととんでもない計算量になりかねないので、工夫してこれを減らす必要が出てきます。そこで思いつくのはいわゆる組み合わせ。組み合わせと順列は1対多の関係にあり、この関係性を利用すれば計算量が圧縮できるのですが……n = 12とかになると、これでもまだまだ計算量が多いのです。したがってまだまだ圧縮の必要がある。ということでわたしはパターンという独自概念(?)を導入したわけです。パターンとは組み合わせのプロトタイプであり、当然1対多の関係にあります。つまりパターンをひとつ定めたら、そこから作られる組み合わせが定まり、自動的に順列も定まるという算段です。
――と自分で書いていてこういうのもあれですが、やはりわかりにくいですね。要するに「どんどんまとめていこう」という程度のことでした。
