AOJ 0268 - Kongo Type (Part 1)

AOJ

今回はこの問題を取り上げます。
まずはショートコーディングではなく、普通に解いてみることにします。

この問題では割と珍しいことに、16進数で入力されます。まずはこの入力部ですが、scanfには%xというフォーマットがあるので、これを使えば一発で終わります。基数変換などは不要です。
さて、それぞれの入力に対し、符号部・整数部・小数部それぞれ出力する必要があります。このうち符号部の処理は入力の32ビット目*1を見ればいいだけなので、簡単です。では、整数部および小数部はどのようにすればよいでしょうか。
整数部は、問題文で与えられているようにb_8+2^1\times b_9+\ldots +2^{23}\times b_{31}を愚直に計算しても、もちろん求めることはできます。ただし、ループを回すことになるため、面倒くさいです。実はこの問題では、入力の8～31ビット目を取り出し、これらを7ビット右シフトするだけで、整数部を求めることができます。これなら実装も楽ですし、何より短く書けます。短く書けます*2。
一旦以上をまとめると、概ね以下のような流れになります。

#include <cstdio>
using namespace std;

int main(){
	unsigned q, s;
	for(scanf("%u", &q); q--; ){
		scanf("%x", &s);	//16進入力
		int x = (s & 0x7fffffffu) >> 7;	//整数部
		int y = ...;	//小数部(後述)

		if(s >> 31) putchar('-');	//符号出力
		printf(...);	//整数部および小数部出力(後述)
	}
}

さて、今度は小数部の計算です。とはいえ、小数というのはどうにも扱いづらいので、出来る限り整数のまま扱いたいものです。そこで、小数部に10^7を掛けてみることにします。そうすると、1～7ビット目の重みは次のようになります。

ビット 本来の重み 10^7を掛けた重み
1 0.0078125 78125
2 0.015625 156250
3 0.03125 312500
4 0.0625 625000
5 0.125 1250000
6 0.25 2500000
7 0.5 5000000

このように、10^7を掛けることで重みは全て整数となり、何となく扱いやすそうな気がします。というわけで、小数部に10^7を掛けたものを求めてみることにしましょう。10^7=2^7\times 5^7なので、\left((0.5)^1\times b_7+(0.5)^2\times b_6+\ldots+(0.5)^7\times b_1\right)\times 10^7=\left(2^6\times b_7+2^5\times b_6+\ldots+b_1\right)\times 5^5と変形できます。整数部の処理と同様に考えれば、入力の下位7ビットを取り出し、それに5^5=78125を掛ければ、小数部を整数として求めることができることが分かります。あとは、桁数が7に満たない場合には適当に0を頭に付け足すことで、とりあえず正確な値を出力することはできます。未完成ですが、とりあえず今の段階でのコードは次のようになります。

#include <cstdio>
using namespace std;

int main(){
	unsigned q, s;
	for(scanf("%u", &q); q--; ){
		scanf("%x", &s);	//16進入力
		int x = (s & 0x7fffffffu) >> 7;	//整数部
		int y = (s & 0x7fu) * 78125;	//小数部

		if(s >> 31) putchar('-');	//符号出力
		printf("%d.%07d\n", x, y);	//整数部、小数点、小数部を出力(未完成)
	}
}

printfには便利な書式があり、%07dと書けば、整数を7桁以上(足りない桁は0で埋める)で出力してくれます。これを実行すれば分かりますが、とりあえず「正確な値」は出力されます。ただし、例えば入力00000f08に対する出力は30.0625000となり*3、「ある桁以下がすべて 0 の場合、その桁以下は省略するものとする」という条件を満たしていません。次はこれをなんとかする必要があります。
例えばその例の場合、小数部は整数625000として得られます。正しい出力と比較すれば、明らかに末尾の0を削れば良いことが分かります。ただし、そのまま10で割ってしまうと桁数が減ってしまうため、このままでは左側に要らない0が増えてしまいます*4。そこで、10で割ると同時に、全体の桁数も減らす必要があります。この桁数をdとして、とりあえず求めることにしましょう。そうすると、次のようなコードになります。

#include <cstdio>
using namespace std;

int main(){
	unsigned q, s;
	for(scanf("%u", &q); q--; ){
		scanf("%x", &s);	//16進入力
		int x = (s & 0x7fffffffu) >> 7;	//整数部
		int y = (s & 0x7fu) * 78125;	//小数部
		int d = 7;	 //最初は7桁とする
		while(d > 1 && y % 10 == 0){
			y /= 10; //末尾に0があるなら(すなわち10で割り切れるなら)、10で割る
			--d;	 //桁数も1つ減らす。1桁になったらループを抜ける。
		}

		if(s >> 31) putchar('-');	//符号出力
		printf(...);	 //整数部、小数点、小数部を出力(未完成)
	}
}

最後に、小数部の出力を考えます。これまたprintfには便利な書式があり、%0*dと書けば、任意の桁数で整数を出力(足りない桁は0で埋める)してくれます*5。そこでこれを使えば、最終的にコードは次のようになります。

#include <cstdio>
using namespace std;

int main(){
	unsigned q, s;
	for(scanf("%u", &q); q--; ){
		scanf("%x", &s);
		int x = (s & 0x7fffffffu) >> 7;
		int y = (s & 0x7fu) * 78125;
		int d = 7;
		while(d > 1 && y % 10 == 0){
			y /= 10;
			--d;
		}

		if(s >> 31) putchar('-');	//符号出力
		printf("%d.%0*d\n", x, d, y);	//整数部x, 小数部y(桁数d)
	}
}

以上で、普通に書いたコードの完成です。このままでも割と短いです。
次回はこれを短縮していきます*6。基本的な方針はほとんど同じです。

*1:問題文中の図に対応させて、1-basedとします

*2:大事なことなので(ry

*3:正しい答えは30.0625です

*4:たとえば1000で割って625にした場合、小数点直後に0が増えて30.0000625となってしまいます

*5:あんまり使わない書式かもしれませんが、たまに便利です

*6:3/21追記: そのうち書きます……

AOJ 0257 - Railway Ticket

AOJ ShortCoding

ブログを1ヶ月以上放置していたので、久しぶりに投稿してみます。問題はAOJ 0257です。

早速ですが、コードは以下のようになります。

a[];main(){read(0,a,5);*a=!puts(*a%3<1|a[1]&1?"Open":"Close");}

今回は、低レベルな入力関数であるreadにより入力を行うことにします。AOJの環境はリトルエンディアンのため、ASCIIコード表を参照すると、各入力に対する配列aの値は次の5通りとなります。ついでに、a[0]を3で割った余りも求めてみます。

入力 a[0] a[1] a[0]%3 出力
1 0 0 0x20302031 0x30 2 Close
0 1 0 0x20312030 0x30 2 Close
1 1 0 0x20312031 0x30 0 Open
0 0 1 0x20302030 0x31 1 Open
0 0 0 0x20302030 0x30 1 Close

表を見れば分かるように、a[0]%3が0であるか、あるいはa[1]が0x31(すなわち奇数)であればOpenを、さもなくばCloseを出力すれば良いことが分かります。
以上の考察により、コードは上記のようになることが直ちに分かります。

AOJ 0503 - Cup (Part 2)

AOJ ShortCoding

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

まずは、配列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のコードが完成します。

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

AOJの環境について

AOJ ShortCoding

AOJ(Aizu Online Judge)の環境でC言語を使う場合のメモです。特にショートコーディング*1を行う場合、以下の点に注意する必要があります。なお、これらはあくまでショートコーディングを行うためのものであり、通常のプログラミングでは考慮する必要がない(あるいは考慮すべきでない)ことも含まれます。

  1. 基本的に、規格はC89に準拠しているものと思われます
  2. char型は8ビット、short型は16ビット、int型およびlong型は32ビット、float型は32ビット、double型は64ビットです。
    • 標準的な仕様でしょう
  3. ポインタは64ビットです
    • 以前は32ビットだったような気がします。AOJのシステムの更新により変更されたのかもしれません。
  4. リトルエンディアンが採用されています
    • 通常は気にする必要はありませんが、たまにこれを利用してコードの短縮を行えることがあります
  5. 文字コードはASCIIです
    • C言語の規格上はASCII以外の文字コードもありうるのですが、少なくとも競技の環境では、ほぼ確実にASCIIと思って間違いないでしょう
  6. 整数において、負の数は2の補数表現です
  7. 二項演算子のオペランドは、左から右の順に評価されます(多分)
    • C言語の規格上は不定です
  8. 関数の引数は、右から左の順に評価されます
  9. 大域変数および引数宣言では、型がintであれば型名を省略できます
  10. 関数の戻り値の型は、intであれば型名を省略できます
  11. 文字リテラルについて、例えば'abcd'などの表記が可能です
    • この場合、0x61626364と同じ値になります。例えば要素数30000以上の配列を宣言したい場合、a[30000]と書くよりa['~~']と書いた方が短く書けます。
  12. 配列宣言において、要素数は省略できます
    • 例えば、double a[]; などの宣言が可能です。要素数は01となるようです。
  13. main関数の第一引数は1です
    • たまに使います
  14. main関数が0以外の値を返した場合、Runtime Errorとなります
    • これは割と厄介な仕様です。この条件を満たすため、以下のいずれかを行う必要があります。
    1. return 0;
      • 普通はこうしますが、長いです
    2. exit(0);
      • return 0; よりはやや短く書けます
    3. 計算結果が0になる式(ただし定数式でないもの)の値を、大域変数に代入する
      • これにより特定のレジスタの値が書き換わり、0が返るようになることがあります。なお、最適化のためか、局所変数に代入しても効果はないことが多いです。また、定数式の代入も効果がないことが多いです。
    4. 計算結果が0になる乗算や除算を行い、それを条件式として用いる
      • forの継続条件などにこういったものを用いると、効果があることもあります。
  15. 大域変数のメモリ配置は、変数の宣言順序とは必ずしも一致しないようです
  16. 定数EOFは-1です
    • C言語の規格上は「負の整数」というような規定しかありませんが、大抵の環境では-1だと思います
  17. 関数putsは、0以外の値を返します
    • ちょっと実験してみたところ、出力文字数(最後の改行含む)を返すようです
  18. #includeは省略できます
    • #includeを省略しても、通常通り動く場合が多いです。ただし、中には#includeを書かないとコンパイルエラーとなったり、あるいは動作がおかしくなる関数もあります。要確認。
  19. #includeを省略した場合、コンパイラによる引数のチェックが甘くなります
    • 引数の数が違ったり、あるいは型が違ったとしても、そのままコンパイルされる場合が多いです。

以上が、AOJのC言語における注意事項です。例外的に、リアクティブな問題(2273,2277,2410, 2414など)では、実行環境が以下のように異なります。なお、番号は上記のものに対応します。

  1. 規格はC99に準拠しているものと思われます
  2. 変数および引数の型は、intであっても省略できません
  3. 配列宣言において、要素数は省略できません
  4. main関数は、何も書かないでも0を返します
    • 従って、上記で挙げたような対策が不要となります
  5. #includeは省略できません

これらの問題では、全体的にショートコーディングに不利な条件となります。ただし14番だけは、C89の環境よりも有利です。

以上、AOJでショートコーディングする際の注意事項でした。普通の人にとっては、あまり役には立たないと思います。


(2/16追記)
long型は64bitでした。訂正します。

*1:コードゴルフという呼び方もありますが、本ブログではショートコーディングに統一します。

AOJ 0503 - Cup (Part 1)

AOJ

実質初投稿です。
書くネタはほとんどないのですが、以前書いたコードの解説でもしてみようかと思います。
題材はAOJ 0503です。私のお気に入りの問題の一つです。

問題ではコップが使われていますが、このままだと微妙に図で説明しづらいです。
というわけで、問題設定をちょっと変更します。
まず、各コップには一意な番号k (1≦k≦n)が付けられていますが、これを全てn-kという番号に付け替えます。これで、番号は[0,n)に付け替わります。以後、こちらの番号で説明します。
さらに、それぞれの番号に対し、円盤を対応付けます。このとき、0番の円盤が一番小さく、n-1番の円盤が一番大きくなるようにします。
ちょっと分かりにくいので、図で説明します。問題の入力例2に対応するのが図1です。コップで表したのが上半分で、さらに番号を付け替えて円盤で表したのが下半分です*1。これはどう見てもハノイの塔ですね*2。
これまた説明のために、それぞれの杭に#0～#2の番号を付けておきます。なお、この番号および杭は、以後面倒なので省略します。
f:id:climpet:20130101130131p:plain
ちなみに、n=4の場合の完成形は図2(もしくはこれを左右反転させたもの)です。
f:id:climpet:20130101130136p:plain
では、解法を説明します。この問題はJOIの過去問で、公式で解説も出ていますが、そのやり方とはやや異なるようです。漸化式？なにそれおいしいの？
この問題は、初期状態が与えられていて、最終状態(#0または#2に集める)にするまでのステップ数を答えるものです。これを逆に考えて、最終状態から初期状態にするまでのステップ数でも同じになるはずです。なのでここでは、全円盤が#0に集まった状態から、初期状態にするまでのステップ数を考えることにします。#2については後述します。
さらにこの問題をよく考えると、番号の大きい円盤*3から順に位置を確定させていくような感じにせざるをえません*4。
というわけで、i番の円盤を#0から目的の場所に移動させるためのステップ数、およびそのときの他の円盤への影響を考えてみます。

  • i番の円盤を#0から#0に移動させる場合
    • 何もしないでいいです
  • i番の円盤を#0から#1に移動させる場合
    • まず、0～i-1の円盤が邪魔なので、これらを一旦#2に移動させる必要があります。これには3^i-1ステップかかります*5。さらにその後、i番を#0から#1に移動させるため、全部で3^iステップ要することが分かります。このとき、0～i-1番は全部#2に移動します。この結果を図3に示します。
  • i番の円盤を#0から#2に移動させる場合
    • 「#0から#1」の移動の後、さらに「#1から#2」の移動を行います。後者については、0～i-1番を#2から#0に移し(3^i-1ステップ)、さらにi番を#1から#2に移します。結果として、2\times 3^iステップかかります。またこの後、0～i-1番は#0にあります。この結果を図4に示します。

f:id:climpet:20130101130141p:plain
f:id:climpet:20130101130149p:plain
以上の考察から、次のようにすれば全体のステップ数が求まることが分かります。

  1. 全部の円盤が#0にあると仮定する。なお、この位置をpとおくことにする(すなわちp=0)。
  2. i←n-1 とする。
  3. i≧0 の間、以下を繰り返す。
    1. i番目の円盤を移動させる距離d(同じ杭なら0、隣の杭なら1、それ以外は2)を求める。
    2. d\times 3^iをステップ数に加算
    3. dが1なら、0～i-1番の円盤を反対側に移動させる。すなわち、p←2-pとする。
    4. i←i-1とする。

これにより求まったステップ数をxとおくことにします。

では次に、全円盤が#2にあるとした場合のステップ数yを求めます。これとxのうち、小さいほうが答えとなります。
これは、pの初期値を2に変えれば、同様に求めることができます。しかしここでは、次のようにして求めることにします。
それぞれの円盤は#0,#1,#2の3通りの位置が考えられるため、この問題全体の状態数は3^nステップです。一方、全円盤を#0から#2に移動させるためのステップ数は、実は3^n-1ステップとなります。すなわち、全円盤を#0から#2に移動させる場合、その間に全状態を経由していることが分かります。従って、y=3^n-1-xが成り立ちます(図5参照)。
あとは、min{x,y}とmを比較し、mを超えていなければその値を、超えていれば-1を出力するだけです。
f:id:climpet:20130101125748p:plain
というわけで、やっとソースコードです。

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

int main(void){
	int pow3[16], c[16];
	int n, m, i, j, k, d, x, y, p;

	pow3[0] = 1;
	for(i = 1; i <= 15; ++i){
		pow3[i] = pow3[i-1] * 3;
	}

	while(scanf("%d%d", &n, &m), n){
		for(i = 0; i < 3; ++i){
			for(scanf("%d", &j); j > 0; --j){
				scanf("%d", &k);
				c[n-k] = i;	/* 番号付け替え */
			}
		}

		p = 0;
		x = 0;
		for(i = n - 1; i >= 0; --i){
			d = abs(p - c[i]);
			x += pow3[i] * d;
			if(d == 1){
				p = 2 - p;	/* 反対側に移動 */
			}
		}

		y = pow3[n] - 1 - x;
		if(x > y){
			x = y;
		}
		printf("%d\n", x > m ? -1 : x);
	}
	return 0;
}

(Part 2に続く予定)

*1:これらの図は、画像作成ソフトExcelを用いて作成されました

*2:ただし、各円盤は隣の杭にしか動かせないという制約付きです

*3:コップの番号で言えば小さいもの

*4:ここらへん日本語として変な気がする

*5:これは漸化式を立てれば証明できますが、割愛します

とりあえず作ってみた感じの何か

ブログ開設してみました。
使い道は未定です。

とりあえず、ソースコードを入力できるとのことなので、テスト用に定番のHello World!でも貼り付けてみます。

''=~('$?[-~)@_ `%,@/ ~/^,@$|@!]!'^'^/!}/@~{"*@@~`#)`.@$%`>#`]'&',@:_\\~.+_-^{,_\\;^<[=_#._>*');

(実行結果: http://ideone.com/wfQmSj)