AOJ 0503 - Cup (Part 2)

これの続きです。このコードを短縮します。

まずは、配列pow3をわざわざ用意するのは長くなるので、毎回pow関数を使って値を求めることにします。
また、この問題の特徴として、#0と#2が入れ替わっても答えが変わらないことが挙げられます。そこで入力の際、#0→#1→#2の順に入力していましたが、これを#2→#1→#0の順にします。
以上をまとめると次のようになります。まだ長いですが、徐々に短くしていきます。

#include <stdio.h>
#include <stdlib.h>
#include <math.h>

int c[16];
int n, m, i, j, k, d, x, p;

int main(void){
	for(; scanf("%d%d", &n, &m), n; printf("%d\n", x > m ? -1 : x)){
		for(i = 3; i--;)
			for(scanf("%d", &j); j--; c[n-k] = i)
				scanf("%d", &k);
		p = 0;
		x = 0;
		for(i = n; i--; ){
			d = abs(p - c[i]);
			x += pow(3, i) * d;
			if(d == 1){
				p = 2 - p;
			}
		}
		x = fmin(x, pow(3, n) - 1 - x);
	}
	return 0;
}

次に、全部の円盤の位置pについて考えます。pの値は0または2なので、pは非負整数qを用いて(q*2%4)と表すことができます。これはすなわち、qが偶数であれば#0、qが奇数であれば#2になるということです。ここで、qに値を加算すると、次のような変化があります：

qに1を加算すると、qの偶奇が入れ替わります。すなわち、#0であった場合は#2に、#2であった場合は#0に移動することになります。
qに0または2を加算しても、qの偶奇は変化しません。すなわち、全円盤の位置pは変化しません。

さて、各c[i]の値は0,1,2のいずれかですが、これが0または2であるときはpを変化させず、1であるときはpを変化させる必要がありました。これと上記の事項から、pを適切に移動させるためには、qにc[i]を加算するだけで良いことが分かります。つまり、実はif文を使わずに、以下のように簡潔に書くことが可能です。

#include <stdio.h>
#include <stdlib.h>
#include <math.h>

int c[16];
int n, m, i, j, k, x, q;

int main(void){
	for(; scanf("%d%d", &n, &m), n; printf("%d\n", x > m ? -1 : x)){
		for(i = 3; i--;)
			for(scanf("%d", &j); j--; c[n-k] = i)
				scanf("%d", &k);
		q = 0;
		x = 0;
		for(i = n; i--; ){
			x += pow(3, i) * abs(q*2%4 - c[i]);
			q += c[i];	// 変更部分
		}

		x = fmin(x, pow(3, n) - 1 - x);
	}
	return 0;
}

さらに、qの初期値について考えます。前回記事ではpの初期値を#0としていましたが、入力部と同様、pの値は実は#0でも#2でも答えは同じになります。これをqについて考えると、実は、qの初期値は非負であれば何でも良いということになります。そこで上記のコードについて考えてみますと、入力に用いたkという変数は明らかに正の値であり、かつその後kを使うことはありません。従って、qとkを共用の変数とすることができ、さらにその初期化も不要ということになります。ここから、qを消去した次のコードが得られます。

#include <stdio.h>
#include <stdlib.h>
#include <math.h>

int c[16];
int n, m, i, j, k, x;

int main(void){
	for(; scanf("%d%d", &n, &m), n; printf("%d\n", x > m ? -1 : x)){
		for(i = 3; i--;)
			for(scanf("%d", &j); j--; c[n-k] = i)
				scanf("%d", &k);
		x = 0;
		for(i = n; i--; k += c[i])
			x += pow(3, i) * abs(k*2%4 - c[i]);
		x = fmin(x, pow(3, n) - 1 - x);
	}
	return 0;
}

次に、xについて考えてみます。ここで敢えて、z=(-1-x)という変数を定義し、xの代わりにzを計算してみることにします。このとき、x=(-1-z)=~z であることを利用すれば、次のようになります。

#include <stdio.h>
#include <stdlib.h>
#include <math.h>

int c[16];
int n, m, i, j, k, x, z;

int main(void){
	for(; scanf("%d%d", &n, &m), n; printf("%d\n", x > m ? -1 : x)){
		for(i = 3; i--;)
			for(scanf("%d", &j); j--; c[n-k] = i)
				scanf("%d", &k);
		z = -1;	// zの初期値は-1
		for(i = n; i--; k += c[i])
			z -= pow(3, i) * abs(k*2%4 - c[i]);  // ステップ数を減算
		x = fmin(~z, pow(3, n) + z);
	}
	return 0;
}

これはさっきより長いコードです。しかし、次のようにすれば短縮につながります。
入力が終わった段階で、変数jの値は-1となっているはずです。さらに、変数jはこの後使うことはありません。そこで、zの代わりにjを使うことで、zの初期化が不要となります。また、変数xについてもjを使えばいいので、xは消去できます。これよりコードは次のようになります。

#include <stdio.h>
#include <stdlib.h>
#include <math.h>

int c[16];
int n, m, i, j, k;

int main(void){
	for(; scanf("%d%d", &n, &m) * n; printf("%d\n", j > m ? -1 : j)){
		for(i = 3; i--;)
			for(scanf("%d", &j); j--; c[n-k] = i)
				scanf("%d", &k);
		for(i = n; i--; k += c[i])
			j -= pow(3, i) * abs(k*2%4 - c[i]); //zの代わりにjをそのまま使う
		j = fmin(~j, pow(3, n) + j);
	}
	return 0;
}

出力、すなわちprintfを実行する段階において、カウンタiの値は当然-1となっているはずです。従って、-1と書く代わりにiと書くことで、1byte短縮できます。
あとは、scanfが多いのがちょっと気になります。汚くなりますが、「scanf("%d",」の部分を#defineで1文字にまとめます。
最後に、余計な#includeやreturn、型名、空白などを取り除いて、次のコードが得られます。

#define S scanf("%d",
c[];
main(n,m,i,j,k){
	for(;S&n),S&m),n;printf("%d\n",j>m?i:j)){
		for(i=3;i--;)
			for(S&j);j--;c[n-k]=i)S&k);
		for(i=n;i--;k+=c[i])
			j-=pow(3,i)*abs(k*2%4-c[i]);
		j=fmin(~j,pow(3,n)+j);
	}
}

改行およびインデントを取り除けば、195byteのコードが完成します。

いかがでしたでしょうか。今回は割と丁寧に書いたので、おそらく理解していただけたのではないかと思います。
この記事を読んだ方には、さらなる短縮に挑んで頂ければ幸いです。