CodeIQ：左右に行ったり来たり
私自身が表題の問題を解いた時のプログラムについて解説します。
問題の詳細は「左右に行ったり来たり」（CodeIQ）を参照してください。
問題の概要
一列に n 個のマスが並んでおり、各マスには 1～(n-1) のいずれかの数字が書かれています。
この一列のマスに対して、書かれている数字の数だけ左右に移動します。
このとき、進む方向は「左」「右」を交互に繰り返します。
最初、左端から右向きにスタートして、右端のマスに到達するような数字の配置を考えます。
なお、右端のマスに到達した時点で終了するため、右端のマスは0とします。
また、左端のマスより左、右端のマスより右には移動できないため、そのような数字の配置はできないものとします。
例えば、以下のマスのように配置されていると、図のように移動します。
このように、右端に到達できる数字の配置のうち、すべてのマスでちょうど一度ずつ止まるものが何通りあるかを求めてください。
例えば、n = 6 の場合は、上記の左図の他に右図のようなパターンがあり、全部で5通りです。
なお、n は12以下の整数とします。
【入出力サンプル】
標準入力
6
標準出力
5
私のプログラム
C言語で解答しています。
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
int getNext(int flags, int pos, int cnt, int n){
int ret = 0;
if((pos < 0) || (n<=pos)){ return 0; }
int f = 1 << pos;
if((flags & f) == f){ return 0; }
if(cnt == n-1){
if(pos == n-1){ return 1; }
else{ return 0; }
}
for(int i=1; i<n; i++){
ret += getNext(flags | f, (cnt%2==0 ? pos+i : pos-i), cnt+1, n);
}
return ret;
}
int solve(n){
if( (n % 2) != 0 ){ return 0; }
return getNext(0,0,0,n);
}
int main(void){
char str[16] = {0};
int n = 0;
while( fgets(str, sizeof(str), stdin) != NULL ){
n = atoi(str);
printf("%d\n", solve(n));
}
}
解説
一応テストケースをパスしていますが同じロジックをRubyでやると時間切れです。
なので、どこか改善の余地があります。
考え方
基本的には問題の通りの操作をしています。
操作は再帰で単純に実装できます。
最低限、数字を入れる配列と最後に数値を置いた場所、何回目かを示すカウンタを引数に取る関数を用意します。
この関数が呼ばれたら、カウンタが偶数なら最後に数値を置いた場所にある値だけ右方向に、奇数なら左方向に次の値を置いて自分を再度呼ぶと言う操作を繰り返すことで操作を実現できます。
ただ、配列を使うとコピーが必要になったりするので手間と計算量がかかります。
そこで少し工夫をしています。
問題文の操作ですが、最後に置いた値以外はその場所にすでに値があるかどうかだけがわかれば良いので、配列ではなくビットフラグにしました。これで大分早くなります（が、Rubyでは時間に間に合いません）。
main
入力値を数値にしてsolve()に渡し、結果を印字します。
solve()
nが偶数の時は左向きに数値を配置した状態で終了になります。これは右端にたどり着かないので必ず結果は0になるので弾いてしまいます。
そうでなければgetNext()を呼んで解を求めます。
getNext(int flags, int pos, int cnt, int n)
問題の操作を行って条件を満たすパターンを数えます。
引数は次の通りです。
flags：配列の代わりで数値が置かれている場所が1、置かれていない場所を0として扱います。
pos：次に値を置くビット位置です。
cnt：操作回数です。
n：入力値です。
この関数は考え方に書いた方法と異なり、すでに置いた場所を扱うのではなく、次に置く場所を扱います。引数を見てもらうとわかりますが、いくつをどこに置いたのかを受け取っていません。次にどこに値を置くかと言う関数にすることでposに何を置くのかをまとめてしまうことができます。
わかりにくいので具体的に書いて見ます。
最初はsolve()に書いた通り、getNext(0,0,0,n)です。これは何も値を置いていないflagsの0番目に何らかの値を置けと言うことになります。
この状態で再帰呼び出しされると、n=6の場合なら次の5パターンが呼び出されます。
getNext(0b00000001, 0+1, 1, 6)
getNext(0b00000001, 0+2, 1, 6)
getNext(0b00000001, 0+3, 1, 6)
getNext(0b00000001, 0+4, 1, 6)
getNext(0b00000001, 0+5, 1, 6)
この第2引数の+の右側がflagsの1の場所に置かれた値、左側が置いた場所になるのですが、計算して次の場所にしてしまうことができるのです。ちなみにgetNext(0b00000001, 0+1, 1, 6)からの再帰呼び出し時は次のようになります。
getNext(0b00000011, 1-1, 2, 6)
getNext(0b00000011, 1-2, 2, 6)
getNext(0b00000011, 1-3, 2, 6)
getNext(0b00000011, 1-4, 2, 6)
getNext(0b00000011, 1-5, 2, 6)
これをやっているのが18〜20行目です。
説明が前後しますが、終了条件は値を置けなくなった時か最後の場合で、8行目は領域外の場合、11行目はすでに値が置かれている場所に値を置こうとした場合、13〜16行目は最後の値を置いた場合です。
すでに値が置かれているかどうかは置こうとしているビット位置に1を建てたものとflagsの論理積をとって置こうとしているビット位置に1が残ればNGと簡単に判断できます。
最後の値を置いた場合は位置が最上位ビットでなければならないのでチェックしています。
最終的に正しければ1、ダメなら0を返すので再帰の戻りでそれを加算すれば答えになります。
雑感
うまく説明しづらい。自分で書きながらわかりにくいなぁ、と思います。そんなに難しいことはやっていないのですが。
まぁ、Rubyでは時間的にダメなのでC言語で押し切ったと言うコードなのでこんなもので諦めます。