「今週のお題:異なる整数で作る逆三角形」問題解答 ( CodeIQ )

はじめに

CodeIQという所で週次で出題される「今週のお題」シリーズに解答しましたので、ネタバレです。

codeiq.jp

問題

今回は次のような問題でした。

  • 入力 n ( n≦7 ) を元に、自然数を配置した n 段の逆三角形を作る時の、最下段に配置されうる数値の最小値を出力する
  • 1段目は n個、2段目は n-1個、…と、全て異なる自然数により逆三角形を構成する
  • 同じ段の隣接する2数の直下に配置される数字は、その2数の合計となるようにする

図で表すと、次のような感じになります。

https://codeiq.jp/sites/default/files/answer_ready/3259/q82.png

解説

さて。まずは実際に最小値が現れる配置を1つ挙げます。n=7 ( 最小値212 ) の例です。

f:id:ange1:20170529002237p:plain

そうすると、途中の段の数字は上の段から次々と決まっていくわけですが、最下段に注目すると、実は1段目の数字から直接値が分かります。三角形の構成がパスカルの三角形にも似たものであり、組み合わせ ( C ) を係数とした積和になるのです。

ということは、実は重要なのは、左右対称の位置にある数字のペアの合計、この内訳がどうなるかなのです。

f:id:ange1:20170529003512p:plain

n が奇数の場合は中心のみ数字1つ分で考えることになりますが、この例だと、中心から外側に向かって 1-6-13-24 という内訳ということになります。

そこで、実装としては、このペアの合計がどうなるかを動的計画法で探索することにします。ただ、合計が同じペアであっても、左右どう数字を割り振るかで状況は変わりますから、合計値をまず固定してから内訳を変えて探索をかけます。

探索をかけるに当たっては、中心から外側へ向かってのペアの合計を変化させていくわけですが「同じ数字が三角形中に重複して現れてはいけない」という縛りがあります。そうすると、外側の数字の組に付随して三角形の外殻の数字も決まる度、重複チェックが必要になりますから、この外殻の情報を更新していくことを考えます。
※それとは別に全体の「使用済み数字のセット」も、重複チェックには必要です。

例えば n=7 で、中心の 1、その次の組 2-4 が仮決めしてある状況だと、外殻には 2,3,8,5,4 が並ぶことになります。この外殻の情報さえあれば、次の組の合計13の内訳7-6 を探索するとき、新たな外殻が分かって重複チェックにかけられるということです。

f:id:ange1:20170529005152p:plain

さて。動的計画法のアイデアは上記でいいのですが、都度最外殻まで探索してるとかなり時間を喰うことが予想されますから、途中で最下段の数字が大きくなりすぎることが分かったら探索を打ち切るように枝刈します。そのため、ペアの合計を仮決めした時に積和の計算を元に、最下段の数値が少なくともどれくらいになるかを見積もるようにします。

ということで、提出したコードは次になります。

重複チェックのための使用済み数はbit-setとして、Rubyの任意精度整数で管理します。また、外殻については左側と右側に分けて持っておきます。次にできる外殻に対応するbit-setは、1段目のペアの数字によっていくつシフトされるかを除けば同じbitパターンですから、重複チェックがshiftとbit-andだけで簡潔に記述できます。

ちょっとトリッキーなのは、最小値の見積もりの精度を上げるために、未使用の数字の中で最小のものを覚えておいて、それとの差分で候補を考えるということです。例えば 1~5 が既に使用済みの状態で 6-7 ペアを選ぶ時、コード上では「6が最小の未使用数字、0-1 の差分ペアを選択」と処理するということです。そのため、仮決定した数字の分の累積和の計算と最小値の見積もり用に、組み合わせ C の値の配列 cs とは別に、それぞれ csa, csm を用意します。

ちなみに余談ですが、1段目を1,2,4,…とすれば必ず重複なしの配置になって、最下段が$3^{n-1}$になることが分かりますから、最小値の初期値はこの$3^{n-1}$に設定しています。

問題での n は高々7ですが、この実装でCodeIQ実行君で、n=17 までなら1秒以内でこなせます。

終わりに

なかなか探索の方法を決めるのに難儀しました。なお、n が大きくなるとbit-setで管理している使用済み数のレンジが非常に大きくなる ( その割にセットされているbitの密度が疎になる ) ことから、ある程度大きい数字にたいしてはハッシュでの管理にした方が良いかと思ったのですが…。却って速度が落ちてしまいました。

なお、内側から順に貪欲に決定して行ければ楽かなと思ったのですが、積和計算の係数が n によって変わってきますので、それではまずいことが分かりました。 例えば n=9 の時は1列目 17,11,7,2,1,4,6,13,21 で最下段が最小 ( 答え1000 ) ですが、n=11 の時の1列目は 20,18,9,8,3,1,5,2,12,19,30 ( 答え4497 ) です。中心の1は同じですが、その隣が違います。…楽はできませんね。

ちなみにこの問題の答え、n を変えてできる数列は、OEISに載っているそうです。おそるべしOEIS。