「今週のお題：互い違いに並べ替え」問題解答 ( CodeIQ )

CodeIQ コードゴルフ

はじめに

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

問題

簡単に書くと、

  • 標準入力より数値 ( nとする ) が与えられる
  • n個の相異なる数字に対して「互い違い」に並べる方法が何通りあるか、その数値を出力する。
    ただし「互い違い」とは、どの連続する3数をとっても単調増加/減少 ( 1→2→3 とか 6→4→2 とか ) ではない、すなわち増加・減少を繰り返すことを指す。

という問題でした。
CodeIQマガジンに記事も出ましたのでご参照ください。( 2015/10/22追記 )

codeiq.jp

解答

以下が提出版のgolf解、Perl(50)。…自動採点だからといって、コメントつけないのは良くないねと反省したばかりなのに、見事にコメントを付け忘れてました。ゴメンナサイ。

@^=2;$\=0,@^=map$\+=$_,reverse 0,@^for 2..<>;print

なお、出題時のテストケースでは n=20 が最大でしたが、もっと大きくなると解答の数値が爆発して、bigint を使ってもこれでは対処できなくなります。…おそらく特殊変数 $\ の制約でしょうね。( $\ を止めて bigint を使えば対応できますが )
計算量的にはΟ(n2)ですが、実際の処理負荷は途中の数値の桁数によって変わってきますので、処理時間的にはそう単純にはいかないでしょう…。一応 n=200 でも 0.5秒くらいで捌けそうでしたが。

解説

方針

やはり規則性を調べて漸化式を立てる、という方針で考えます。漸化式さえ分かってしまえば、機械的に計算を回すだけで済むからです。 丁度、次の図の通り、途中までどんな並べ方をしていたとしても ( 次が smaller/bigger かは定まるにせよ )、そこからの並べ方は「残りの個数」「次の方向にある個数」の2種類のパラメタで定まります。

f:id:ange1:20151019233734p:plain

この「そこからの並べ方」を g(n,m) ( nは残り個数、mは次の方向にある個数 ) と定めると、nに対する解 f(n) は
f(n)=2\left\{g(n-1,1)+g(n-1,2)+\cdots+g(n-1,n-1)\right\}=2\sum_{k=1}^{n-1}g(n-1,k)
で求めることができます。

f:id:ange1:20151020015218p:plain

なぜ2倍しているかと言うと、最初に smaller/bigger どちらを選ぶかが同等だからですね。なお、n=1 はこの「倍」に当てはまらないので除外しておきます。

規則性

後はそうすると、g(n,m) の規則性を調べる事になります。mは次に選べる個数を表しますから、mが大きくなるごとにg(n,m)の値も大きくなることが推測できます。
という事で、次の図のようにmを変化させてみると、
g(n,m)=g(n-1,n-1)+g(n-1,n-2)+\cdots+g(n-1,n-m)=\sum_{k=n-m}^{n-1}g(n-1,k)
と言うように、g(n-1,XX) を逆順に足していく形が出てきます。 f:id:ange1:20151020004749p:plain なお、nが2以上の場合、g(n,n) は g(n,n-1) と等しくなります。なぜならば、候補が n 個あると言っても、最大/最小 ( 向きにより変わる ) を選ぶとその次で互い違いにできず、結局 n-1個の中からしか選べないからです。

漸化式の整理

これまでに出てきた式を整理してみます。また、始まりとなるべき g(1,1)の値はtrivialなので、一緒に書いておきます。

  • g(1,1)=1
  • g(n,m)=\sum_{k=n-m}^{n-1}g(n-1,k)\,\,\left(n\geq 2,1\leq m\leq n-1\right)
  • g(n,n)=g(n,n-1)=\sum_{k=1}^{n-1}g(n-1,k)
  • f(n)=2\sum_{k=1}^{n-1}g(n-1,k)\,\,\left(n\geq 2\right)

こうして見ると、実は f(n) と g(n,n) は非常に良く似た形をしていることが分かります。ここから、

  • f(n)=2g(n,n)=2g(n,n-1)

と言えます。

さてしかし。g の漸化式、和が逆順なのでやはり分かりにくい所です。そこでいっそのこと逆を作ってしまいましょう。 g_r(n,1)=g(n,n), g_r(n,2)=g(n,n-1), \cdots,g_r(n,n)=g(n,1)
というように。 すなわち、

  • g_r(n,m)=g(n,n+1-m)

として gr を定義します。そうすると、

  • g(n,m)=\sum_{k=1}^{m}g_r(n-1,k)\Leftrightarrow g(n,m)=g(n,m-1)+g_r(n-1,m)

のように、g は、gr を使った漸化式の形で書くことができます。
便宜的に g(n,0)=0 とすると、次の図に示すように、g(n,X) のリストから g(n+1,X) のリストというように、再帰的に次々と g を決めていくことができることが分かります。

f:id:ange1:20151020012315p:plain

仕上げとサンプルコード

長くなりましたが、いよいよ仕上げになります。 さて、g から f を求める時に2倍している訳ですが、もともと g, gr を2倍の値に作っておけば、後から倍する必要は無くなります。g,grの代わりに G, Gr としましょう。漸化式自体は ( 線形性があるので ) 同じ形です。
最終的に残る式は、

  • G(1,1)=2
  • G_r(n,m)=G(n,n+1-m)
  • G(n,0)=0
  • G(n,m)=G(n,m-1)+G_r(n-1,m)\,\,\left(n\geq 2,1\leq m\leq n-1\right)
  • f(n)=G(n,n)=G(n,n-1)\,\,\left(n\geq 2\right)

という事で、Perl, Ruby での実装例は次の通りになります。G(n,X) の値をリストとして持っておき、ループ毎に更新していきます。これをちょっと縮めたのが、冒頭に挙げたコードということになります。

$n=<>;
die if $n<2;
@g=(2);
for ( 2..$n )
{
  @gr=reverse @g;
  $s=0;
  @g=map{$s+=$_}@gr;
  push @g,$s;
}
print $g[-1];
n=gets.to_i
raise if n<2
g=[2]
2.upto(n){
  gr=g.reverse
  s=0
  g=gr.map{|e|s+=e}
  g<<s
}
puts g[-1]

最後に

なんか、コードを書くより図を描いて解説する方が疲れました…。が、イメージを言葉だけで説明するのもなかなか難しい所なので。今後も面白い問題/解答があれば、解説を書いて行こうかと思います。