MOD 逆数

 n を整数とすると, n と互いに素な任意の整数  a に対し,  ax \equiv 1\ ({\rm mod}\ n) を満たす整数  x\ (0 \leq x < n) がただ一つ存在します.この  x を,  n を法としたときの逆数といい,競技プログラミングで頻繁に役立ちます.今回はこれを計算するコードを C で書いていきます.

数学的な解き方

 ax \equiv 1\ ({\rm mod}\ n) ならば,ある整数  x' が存在して  ax + nx' = 1 です.すると,これは  nx' \equiv 1\ ({\rm mod}\ a) と書き換えられます.ここで  n a で割った余りを  r とすると,  rx' \equiv 1\ ({\rm mod}\ a) となります.これを繰り返すことで  x を求めることができます.具体的には, n = 529, \, a = 100 とすると

 100x \equiv 1\ ({\rm mod}\ 529)
ある  x' が存在して
 100x + 529x' = 1
よって
 529x' \equiv 1\ ({\rm mod}\ 100)
 29x' \equiv 1\ ({\rm mod}\ 100)
ある x''が存在して
 29x' + 100x'' = 1
よって
 100x'' \equiv 1\ ({\rm mod}\ 29)
 13x'' \equiv 1\ ({\rm mod}\ 29)
 13x'' + 29x''' = 1
 29x''' \equiv 1\ ({\rm mod}\ 13)
 3x''' \equiv 1\ ({\rm mod}\ 13)
 3x''' + 13x'''' = 1
 13x'''' \equiv 1\ ({\rm mod}\ 3)
 x'''' \equiv 1\ ({\rm mod}\ 3)
これより,最後の  x'''' の値を  1 とすれば,逆に辿って  x の値を求めることができます.逆に辿るやり方は,
 \begin{align*}3x''' &= 1-13x'''' \\
&= 1 - 3\cdot 4x'''' - x'''' \\
&= - 3\cdot 4x''''\end{align*}
より
 x''' = -4 x'''' = -4

 \begin{align*}13x'' &= 1 - 29x''' \\
&= 1 - 13\cdot 2x''' - 3x''' \\
&= 1 - 13\cdot 2x''' - (1 - 13 x'''') \\
&= -13\cdot 2x''' + 13 x''''\end{align*}
より
 x'' = -2x''' + x'''' = 9

 \begin{align*}29x' &= 1 - 100x''\\
&= 1 - 29\cdot3x''-13x''\\
&= 1 - 29\cdot3x''-(1-29x''')\\
&= -29\cdot3x'' + 29 x'''\end{align*}
より
 x' = -3x'' + x''' = -31

 \begin{align*}100x &= 1 - 529x' \\
&= 1 - 100\cdot5x' - 29x' \\
&= 1 - 100\cdot 5x' - (1 - 100 x'') \\
&= - 100 \cdot 5x' + 100 x''\end{align*}
より
 x = -5x' + x'' = 164
という具合です.

一般化

上の例より, a_0 = n a_1 = a とし,

 \begin{align*}
a_0 \div a_1 &= b_0 \cdots a_2 \\
a_1 \div a_2 &= b_1 \cdots a_3 \\
& \vdots \\
a_m \div a_{m + 1} &= b_m \cdots 1
\end{align*}
とすると,
 \begin{align*}
x_{m + 1} &= 1 \\
x_m &= - b_m x_{m + 1} \\
x_{m - 1} &= - b_{m - 1} x_m + x_{m + 1} \\
x_{m - 2} &= - b_{m - 2} x_{m - 1} + x_m \\
& \vdots \\
x_0 &= -b_0 x_1 + x_2
\end{align*}
という手続きで  x = x_0 の値が求められることが分かりました.

行列

上の手続きを行列を用いて表すと

 \begin{pmatrix} x_k \\ x_{k + 1} \end{pmatrix} = \begin{pmatrix} -b_k & 1 \\ 1 & 0 \end{pmatrix} \begin{pmatrix} x_{k + 1} \\ x_{k + 2} \end{pmatrix}
(ただし k 0以上 m以下の整数,また\begin{pmatrix}x_{m + 1} \\ x_{m + 2}\end{pmatrix} = \begin{pmatrix}1 \\ 0 \end{pmatrix}とする)となります.つまり
 \begin{pmatrix} x_0 \\ x_1 \end{pmatrix} = \begin{pmatrix} -b_0 & 1 \\ 1 & 0 \end{pmatrix} \begin{pmatrix} -b_1 & 1 \\ 1 & 0 \end{pmatrix} \cdots \begin{pmatrix} -b_m & 1 \\ 1 & 0 \end{pmatrix} \begin{pmatrix} 1 \\ 0 \end{pmatrix}
なので,行列計算によって  x_0 を求めることができます.

コード

この行列計算をそのままコードで書くと次のようになります.

int inverse(int mod, int val){
	int x[2] = {mod, val};
	int a[2][2][2] = {{{1, 0}, {0, 1}}};
	int i;
	for(i = 0; x[!i]; i ^= 1){
		a[!i][0][0] = a[i][0][1] - x[i] / x[!i] * a[i][0][0];
		a[!i][0][1] = a[i][0][0];
		a[!i][1][0] = a[i][1][1] - x[i] / x[!i] * a[i][1][0];
		a[!i][1][1] = a[i][1][0];

		x[i] = x[i] % x[!i];
	}
	return a[!i][0][0];
}

実際には行列の第 1 行と第 2 行の計算は独立しているので次のように書けます.

int inverse(int mod, int val){
	int x[2] = {mod, val};
	int a[2][2] = {{1, 0}};
	int i;
	for(i = 0; x[!i]; i ^= 1){
		a[!i][0] = a[i][1] - x[i] / x[!i] * a[i][0];
		a[!i][1] = a[i][0];

		x[i] = x[i] % x[!i];
	}
	return a[!i][0];
}

さらに第 1 列と第 2 列を配列内で毎回ひっくり返すようにすると次のようになります.

int inverse(int mod, int val){
	int x[2] = {mod, val};
	int a[2] = {1, 0};
	int i;
	for(i = 0; x[!i]; i ^= 1){
		a[!i] -= x[i] / x[!i] * a[i];
		x[i] = x[i] % x[!i];
	}
	return a[!i];
}

ただしこれだと答えが正になったり負になったりするので,常に  0 \leq x < n の範囲で値を得たいときは次のようにします.

int inverse(int mod, int val){
	int x[2] = {mod, val};
	int a[2] = {1, 0};
	int i;
	for(i = 0; x[!i]; i ^= 1){
		a[!i] -= x[i] / x[!i] * a[i];
		x[i] = x[i] % x[!i];
	}
	if(!i) a[!i] += mod;
	return a[!i];
}

この記事があなたの役に立てば幸いです.

AtCoder に登録したら解くべき精選過去問 10 問を C 言語で解いてみた ① (第1問から第4問まで)

「C」という名前の,何でもできてしまうすごいプログラミング言語があるらしいので,この言語を使って drken さんの「AtCoder に登録したら解くべき精選過去問 10 問」を解いてみました.qiita.com↑この方のブログは AtCoder でプログラミングを勉強しよう!と思っている人なら必ず読むべき良サイト.自分もよくお世話になっております.

まず自分の使っているテンプレートから紹介します.出入力部分などは本質でないので C 言語の標準ライブラリに全て任せて,あとは自力で書くことにしています.

#include <fcntl.h>
#include <unistd.h>
#include <sys/mman.h>
#include <string.h>
#include <stdio.h>

const char main_[] = { /* ここに解を求めるプログラムの中身を書く */ };

int main(void){
	int fd = open("/dev/zero", O_RDONLY);
	/* 返り値 */ (*solve)(/* 引数 */) = mmap(NULL, sizeof main_, PROT_WRITE | PROT_EXEC, MAP_PRIVATE, fd, 0);
	memcpy(solve, main_, sizeof main_);

	/* 入力を scanf などで受け取って solve 関数に渡し,返り値を出力する */

	close(fd);
	munmap(solve, sizeof main_);
	return 0;
}

例えば,2 つの整数を読み込んでその和を出力するプログラムであれば,const char main_[] にその旨を書いて,solve の型を int (*solve)(int, int) とし,solve(a, b) のように呼び出します.

1. A - Product

さて早速1問目から解いていきます.
1問目は,2つの正整数の積が偶数か奇数か判定する問題です.solve 関数は,2 つの int 型変数 a, b を受け取って,その積が偶数であれば 0 ,奇数であれば 1 を返せばよさそうです.よって solve の型は int (*solve)(int, int) となります.
さて,肝心の const char main_[] の中身ですが,問題文をそのまま解釈すれば,「 a と b の積を計算し,その最下位ビットを求める」と書けます.残念ながら私は機械語が読み書きできないので,一旦アセンブリ言語*1で書いてみます(コンテスト時間は限られているので,いずれは機械語を直接書けるようになりたいです).返り値は rax レジスタに置いておけばよいので,先に第1引数(rdi レジスタにある)を rax レジスタに動かしてから第2引数(rsi レジスタにある)をそこに乗算して,1との AND を取ります.

	.global solve
solve:
	mov %rdi, %rax
	imul %rsi, %rax
	and $1, %rax
	ret

これを適当なファイルに保存します.そのまま C のコードとリンクすれば実行ファイルができて,正しく動くか確認できます*2.このアセンブリコードを適当なコマンドを用いて機械語に変換すると,

0:	48 89 f8
3:	48 0f af c6
7:	48 83 e0 01
b:	c3

となり,これで AC コードを書くことができます(https://atcoder.jp/contests/abc086/submissions/7369756).しかし,よく考えてみると知りたいのは積の偶奇であって,積の値そのものではないことに気付きます.そうすると,実は imul コマンドで乗算を行わなくても,AND 演算を行うだけで事足りることが分かります.これを用いてプログラムを書き換えると,次のようになります.

	.global solve
solve:
	mov %rdi, %rax
	and %rsi, %rax
	and $1, %rax
	ret

これを先ほどと同じように機械語に変換すると

0:	48 89 f8
3:	48 21 f0
6:	48 83 e0 01
a:	c3 

となり,1バイト削れました.やったね.最終的な AC コードはこのようになります.https://atcoder.jp/contests/abc086/submissions/7369764

#include <fcntl.h>
#include <unistd.h>
#include <sys/mman.h>
#include <string.h>
#include <stdio.h>

const char main_[] = {
	0x48, 0x89, 0xf8,
	0x48, 0x21, 0xf0,
	0x48, 0x83, 0xe0, 0x01,
	0xc3
};

int main(void){
	int fd = open("/dev/zero", O_RDONLY);
	int (*solve)(int, int) = mmap(NULL, sizeof main_, PROT_WRITE | PROT_EXEC, MAP_PRIVATE, fd, 0);
	memcpy(solve, main_, sizeof main_);

	int a, b;
	scanf("%d%d", &a, &b);
	puts(solve(a, b) ? "Odd" : "Even");

	close(fd);
	munmap(solve, sizeof main_);
	return 0;
}

次の問題からは,コードとして載せるのは const char main_[] の中身の部分だけにし,include や main 関数など他の部分は省くことにします.

2. A - Placing Marbles

2 問目は,長さ 3 の文字列を読み込んで,その中に含まれる '1'(=0x31) の個数を数える問題です.solve 関数は,文字列を受け取って整数を返せばよいので,int (*solve)(char []) となります.
さて,ここでいくつか大事な知識が出てきます.ジャンプを利用した条件分岐とループ,そしてレジスタ間接参照によるメモリアクセスです.
rax レジスタを最初 0 にしておき,文字列を 1 文字ずつ読んでいって '1'(=0x31) が現れるたびに rax をインクリメントすることにします.ちなみに,任意の X について X xor X は 0 なので,

	xor %rax, %rax

とすれば rax レジスタを 0 にすることができます.これは機械語に直すと 48 31 c0 となり, mov 命令を使ったときの 48 c7 c0 00 00 00 00 に比べて 4 バイト小さく,実行も高速です.
文字列の先頭アドレスは第1引数なので rdi レジスタに入っています. 3 文字読んだら終わればよいと分かっているので, rdi から 3 バイト進んだ箇所のアドレスを rcx に置いておきます.

	mov %rdi, %rcx
	add $3, %rcx

そしてループ内で毎回 rdi を 1 増やしてゆき, rdi と rcx が等しくなったところでループを抜けます.

loop:
	# ここに処理を書く
	inc %rdi
	cmp %rdi, %rcx
	jnz loop

jnz 命令は,事前に cmp 命令で比較しておいた 2 つの値が等しくなかったときにのみジャンプをします.よって rdi レジスタと rcx レジスタの値が等しくなるまで,loop ラベルに戻って処理が繰り返されます.こうしてループが実現できました.
また,各ループ内で調べようとしている文字のメモリ上におけるアドレスは,rdi レジスタに書かれているので,間接参照によってその値を rdx にロードします.1 バイト分だけ移したいので,movzb コマンドを使います.

	movzb (%rdi), %rdx

そしてこれが '1'(=0x31) に等しいかどうかを cmp で調べ,等しかったときにのみ rax レジスタをインクリメントします.

	cmp $0x31, %rdx
	jnz neq
	inc %rax
neq:

以上をまとめると,関数全体では次のようになります.

	xor %rax, %rax
	mov %rdi, %rcx
	add $3, %rcx
loop:
	movzb (%rdi), %rdx
	cmp $0x31, %rdx
	jnz neq
	inc %rax
neq:
	inc %rdi
	cmp %rdi, %rcx
	jnz loop
	ret

あとは機械語に変換して AC .https://atcoder.jp/contests/abc081/submissions/7428628

const char main_[] = {
	0x48, 0x31, 0xc0,
	0x48, 0x89, 0xf9,
	0x48, 0x83, 0xc1, 0x03,
	0x48, 0x0f, 0xb6, 0x17,
	0x48, 0x83, 0xfa, 0x31,
	0x75, 0x03,
	0x48, 0xff, 0xc0,
	0x48, 0xff, 0xc7,
	0x48, 0x39, 0xf9,
	0x75, 0xeb,
	0xc3
};

3. B - Shift only

n 個の整数 ai について, ai を 2 で何回割れるか( ord2ai と表記するそうですね)を求めて,その最小値を答える問題です. solve は n と a を受け取るため, int (*solve)(int, int[]) となります.
ループが必要ですが,その回数は rdi レジスタに入っている第1引数 n です.そこで, rdi の値を 1 ずつ減算していって,それが 0 になったらループを抜けることにします.すると,このカウンタとしての rdi の値が,配列へのアクセスにそのまま利用できそうなことに気付きます. C 言語で書くと

do{
	--n;
	// a[n] を見る
}while(n != 0);

ということです.アセンブリ言語に直すと

loop:
	dec %rdi
	# ここにループ内の処理を書く
	cmp $0, %rdi
	jnz loop

さて,「a[n]」というのは「*(a + n)」の糖衣構文ですが,ここにおける「a + n」の意味は,「a と sizeof(int) * n の和」という意味であるため,アセンブリ的には「rsi に rdi * 4 を足した値」が欲しいということになります.実は x86_64 だとこれは「(%rsi, %rdi, 4)」と書くことができるようになっています. これを参照して rcx にロードします.

	mov (%rsi, %rdi, 4), %rcx

あとは, rcx の右端に何個 0 が並んでいるか数えれば良いです.これは有名テクですが, n & (-n) で一番下の 1 だけ残すことができます.アセンブリ言語で書けば

	xor %rdx, %rdx
	sub %rcx, %rdx
	and %rdx, %rcx

です.これによって,例えば rcx の値が 20 なら 4 に, 48 なら 16 になります. 2 の冪乗で表される最大の約数が残るわけです.うーん,こうして得られた値の, 2 を底とする対数をとれば, 2 で割れる回数が計算できるんですが,毎回 log2 を計算してからその最小値を求めるのではなくて,この「2 の冪乗で表される最大の約数」自体の最小値を求めてから最後に log2 をとることにしましょう.
rax レジスタにあらかじめ大きな値を入れておき,それより小さいものが現れたら更新します.十分大きな値として 2^30 = 0x40000000 を使います.

	mov $0x40000000, %rax

「小さいものが現れたら更新する」は,「小さくなかったら更新しない」と言い換えて

	cmp %rax, %rcx
	jae ae
	mov %rcx, %rax
ae:

とすればよいです.
さて,こうしてループが終了したら, rax に 2^ans という値が入っているので, 2 を底とする対数をとって答え ans を得ます.ここでは, rax をデクリメントして 2^ans - 1 にし, popcnt 命令で立っているビットの数を数えます.

	dec %rax
	popcnt %rax, %rax

以上を全てまとめて

	mov $0x40000000, %rax
loop:
	dec %rdi
	mov (%rsi, %rdi, 4), %rcx
	xor %rdx, %rdx
	sub %rcx, %rdx
	and %rdx, %rcx
	cmp %rax, %rcx
	jae ae
	mov %rcx, %rax
ae:
	cmp $0, %rdi
	jnz loop
	dec %rax
	popcnt %rax, %rax
	ret

https://atcoder.jp/contests/abc081/submissions/7412959

const char main_[] = {
	0x48, 0xc7, 0xc0, 0x00, 0x00, 0x00, 0x40,
	0x48, 0xff, 0xcf,
	0x48, 0x8b, 0x0c, 0xbe,
	0x48, 0x31, 0xd2,
	0x48, 0x29, 0xca,
	0x48, 0x21, 0xd1,
	0x48, 0x39, 0xc1,
	0x73, 0x03,
	0x48, 0x89, 0xc8,
	0x48, 0x83, 0xff, 0x00,
	0x75, 0xe2,
	0x48, 0xff, 0xc8,
	0xf3, 0x48, 0x0f, 0xb8, 0xc0,
	0xc3
};

4. B - Coins

初めて割り算が登場します. div 命令というのを使います.この命令は, rdx レジスタと rax レジスタを合わせた 64 bit の領域に入っている値を,別の 32 bit レジスタの値で割ります.
solve 関数は,4 つの整数 a, b, c, x を受け取って整数値の答えを返すので int (*solve)(int, int, int, int) です.まず第 4 引数 x ( rcx レジスタにある) を 500 で割ってみましょう.割る数 500 は,自由に使える r10 レジスタに入れることにします.

	xor %rdx, %rdx
	mov %rcx, %rax
	mov $500, %r10
	div %r10

ちなみに rdx レジスタにはもともと第 3 引数が入っているので,事前に別の場所に避難させておきます. r11 も自由に使えるレジスタです.

	mov %rdx, %r11

こうして rdx レジスタに商, rax レジスタに余りが格納されます.使える 500 円玉の枚数の最大値は,この商と第 1 引数 a のうち小さい方なので, rdi をこれで最小化してしまいます.

	cmp %rdi, %rax
	jae fivehundred
	mov %rax, %rdi
fivehundred:

さて,こうして 500 円玉の枚数の上限が定まったので, 0 枚 〜 上限枚の各場合について,残りの金額を 100 円玉と 50 円玉で支払うやり方が何通りあるか計算します.答えは rax レジスタに入れたいのですが, rax レジスタは div 命令によって使われてしまうので,代わりのレジスタを探します. r8 と r9 は引数を渡すためのレジスタですが,solve 関数には引数が 4 個しかないため使われていないことに気付きます.ここでは r8 を使うことにし,ループに入る前に 0 にしておきます.

	xor %r8, %r8

またこの後 50 で割る計算がループ毎に現れるので, r10 レジスタもループ前に 50 にしておきます.

	mov $50, %r10

さて,ここからのループですが,「0 以上 n 未満」のような半開区間ではなく「0 以上 n 以下」という閉区間になっているため,ループの形が少し変わります.

loop:
	# ここに処理を書く
	dec %rdi
	cmp $0, %rdi
	jge loop

jge は,符号付き整数としての比較です.こうして 0 と比較することで, rdi が負の数になったときにジャンプします.
500 円玉を何枚使うか決めると,支払う残りの金額が決まります.これは,ループ毎に rcx から 500 を引いてゆくことで得ることにします.

	sub $500, %rcx

ループ内の処理では, 100 円玉 b 枚以下,50 円玉 c 枚以下で残りの金額を支払うやり方の数を考えるのですが,これは「100 円玉と 50 円玉がともに無限枚あったと仮定したときの支払い方」から「使う 100 円玉が b 枚を超える場合」と「使う 50 円玉が c 枚を超える場合」を除くことによって求めます.場合によっては「100 円玉も b 枚を超えるし, 50 円玉も c 枚を超えるような場合」というのもありえますが,これは減算の結果が負になったときに 0 に修正することで対処できます.
まず残りの金額 (rcx) を 50 で割ります.

	xor %rdx, %rdx
	mov %rcx, %rax
	div %r10

このとき,問題文の制約により,余りは 0 になることが保証されます.つまり, div 命令の後, rdx は 0 になります.
そして rax に格納された商が,もし第 3 引数 c より大きければ, 50 円玉だけで残りの金額を全て支払うことはできないということになります.第 3 引数の値は r11 レジスタに避難させられています.使う 50 円玉が c 枚を超える場合の数は計算で求められます.

	cmp %r11, %rax
	jbe fifty
	mov %rax, %rdx
	sub %r11, %rdx
	inc %rdx
	sar $1, %rdx
fifty:

sar 命令は右シフトです.
今 rax に入っている値は rcx を 50 で割った商です.これを右に 1 ビットシフトすることで, rcx を 100 で割った商が得られます.

	sar $1, %rax

そして rsi に入っている第 2 引数 b の値と比較して, b の方が小さかったら b に書き換えます.

	cmp %rsi, %rax
	jbe hundred
	mov %rsi, %rax
hundred:

こうして計算した rdx レジスタと rax レジスタの値から,「100 円玉 b 枚以下,50 円玉 c 枚以下で残りの金額を支払うやり方の数」が得られます.

	inc %rax
	sub %rdx, %rax

これが負だったら 0 通りということなので,正のときのみ r8 に加算します.

	cmp $0, %rax
	jle minus
	add %rax, %r8
minus:

最後に,ループを抜けた後 r8 レジスタの値を rax レジスタに移し,関数の返り値とします.

	mov %r8, %rax

以上を全てまとめると, solve 関数の中身は

	mov %rdx, %r11
	xor %rdx, %rdx
	mov %rcx, %rax
	mov $500, %r10
	div %r10
	cmp %rdi, %rax
	jae fivehundred
	mov %rax, %rdi
fivehundred:
	xor %r8, %r8
	mov $50, %r10
loop:
	xor %rdx, %rdx
	mov %rcx, %rax
	div %r10
	cmp %r11, %rax
	jbe fifty
	mov %rax, %rdx
	sub %r11, %rdx
	inc %rdx
	sar $1, %rdx
fifty:
	sar $1, %rax
	cmp %rsi, %rax
	jbe hundred
	mov %rsi, %rax
hundred:
	inc %rax
	sub %rdx, %rax
	cmp $0, %rax
	jle minus
	add %rax, %r8
minus:
	sub $500, %rcx
	dec %rdi
	cmp $0, %rdi
	jge loop
	mov %r8, %rax
	ret

https://atcoder.jp/contests/abc087/submissions/7424163

const char main_[] = {
	0x49, 0x89, 0xd3, 
	0x48, 0x31, 0xd2, 
	0x48, 0x89, 0xc8, 
	0x49, 0xc7, 0xc2, 0xf4, 0x01, 0x00, 0x00, 
	0x49, 0xf7, 0xf2, 
	0x48, 0x39, 0xf8, 
	0x73, 0x03, 
	0x48, 0x89, 0xc7, 
	0x4d, 0x31, 0xc0, 
	0x49, 0xc7, 0xc2, 0x32, 0x00, 0x00, 0x00, 
	0x48, 0x31, 0xd2, 
	0x48, 0x89, 0xc8, 
	0x49, 0xf7, 0xf2, 
	0x4c, 0x39, 0xd8, 
	0x76, 0x0c, 
	0x48, 0x89, 0xc2, 
	0x4c, 0x29, 0xda, 
	0x48, 0xff, 0xc2, 
	0x48, 0xd1, 0xfa, 
	0x48, 0xd1, 0xf8, 
	0x48, 0x39, 0xf0, 
	0x76, 0x03, 
	0x48, 0x89, 0xf0, 
	0x48, 0xff, 0xc0, 
	0x48, 0x29, 0xd0, 
	0x48, 0x83, 0xf8, 0x00, 
	0x7e, 0x03, 
	0x49, 0x01, 0xc0, 
	0x48, 0x81, 0xe9, 0xf4, 0x01, 0x00, 0x00, 
	0x48, 0xff, 0xcf, 
	0x48, 0x83, 0xff, 0x00, 
	0x7d, 0xbc, 
	0x4c, 0x89, 0xc0, 
	0xc3
};

とりあえずここまで

いかがだったでしょうか.初心者にも分かるような説明を心がけたつもりですが,少し難しくなってしまったかもしれません.ただ, C 言語というものがどういうものか,少しは分かってもらえたかと思います.実は,多くの競プロ er が, C 言語ないしこれをもとに作られた C++ という言語を使っているようです!この記事のような低レベルな内容でも,プログラミングにおいては大事なものなのですね.
drken さんの精選 10 問のうち 6 問が残っているので,もし続きができたらまた投稿したいと思います.では.

*1:AT&T記法を使います.

*2:リンクする場合は,単に int solve(); と宣言しておくだけで solve 関数が使えるようになります.

プログラミングへの想いを語る

僕にはいくつかの趣味があり,その1つがプログラミングです.主に書く言語はC/C++で,ちょっとしたアルゴリズムの知識を利用して小さなツールなどを作っています.

この記事では,主にプログラマー以外の人向けに,僕がプログラミングのどういう点に楽しさを感じているか話したいと思います.

ものを作る楽しさ

プログラミングは,傍から見ればコンピュータに向かってキーボードを叩いているだけですが,実際に行われているのは「小さな部品を組み立てて大きなものを作り上げる」という行為です.最終的に何かが完成した瞬間の達成感を味わううちに,1日中コンピュータと向き合ってゴリゴリとコードを書く作業も苦しくなくなります(個人差はあります).そういう意味ではプラモデルとかと似ているのかもしれません.あるいは,小さな歯車を並べて懐中時計を作る作業にたとえることも可能で,この場合,より洗練された精巧な時計を設計する試みは,リファクタリングと呼ばれる作業に対応することになります.
また,使える部品の種類は言語によって違います.例えば昔から使われている C という言語では非常に簡素な部品のみが与えられていますが,もっと新しい言語ではいくつかの部品が組み合わされて使いやすくなったものが多く提供されています.その組み合わせ方の差異が,ウェブ開発に向いている言語,ゲーム開発に向いている言語,スマホアプリ開発に向いている言語などの違いを生んでいます.

思い通りに動く楽しさ

組み立てたプログラムが正しく動くとは限りません.どこか一箇所が間違っているだけで,思いもよらない結果が出力されてしまうこともあります.しかしその分,うまく動いたときの感動は計り知れません.特に僕のやっているアルゴリズム系のプログラミングでは,ある計算をするために一見関係ないような複雑な途中経過を辿ることがあります.ナップザックに荷物を詰め込む最善のやり方を知るために突然大きなタテヨコの表を作ってみたり,文章中のいくつかの単語を置換するために突然文章の先頭から何文字か切り取った残りの部分を並べてみたり…….その途中経過が正しいことは当然理論的に証明できるのですが,それでも実際にやってみて上手く行くことが分かるととてもすっきりします.特にそのアイディアが自ら生んだものであれば,自分は天才なんじゃないかという錯覚に陥るくらいの快感を覚えることができます.

効率の良いコードが書ける楽しさ

プログラミングを始めて間もない頃は,無駄な変数や関数が増えたり,適切な書き方が選べなかったりして,書きにくく読みにくいコードを生んでしまうことがよくあります.しかし慣れてくると,言語のパラダイムに沿って利点を活かした設計などができるようになり,コードを書くのに必要な労力が減ってきます.そしてその分難しいプログラムも作れるようになるのです.語学学習などにも通じるところがあるでしょうか.英語を習いたての頃は適切な語彙選択ができないために冗長な表現ばかりしていたけれど,少しずつ洗練された文法や語法を身に付けることで表現の幅が広がった,というような感じです.

把握できる楽しさ

プログラミングができるようになると,様々なソフトウェアが動く仕組みが少しずつ理解できるようになってきます.ゲームプログラミングに親しめばゲームのバグの原因なども予測できることがあります.目の前で何が起こっているのか掌握できる気分はなかなか良いものです.

自分で決められる楽しさ

自分で作るプログラムの仕様は,自分で決めます.この自由さは趣味プログラミングならではの楽しさです.エディタを作るにしろ言語処理系を作るにしろOSを作るにしろ*1,そこには必ず何らかの仕様が生まれます.そのデザインを自ら考え,実際にプログラムとして作ることで,それが自分のアイデンティティとなります.

ネタとしての楽しさ

プログラミングは本来機械を動かすための「手段」ですが,プログラミング自体を「目的」として楽しむ人もいます.一見何をしているのか分からない難解なコードを書いてみたり,ソースコードで絵を書いてみたり.言語仕様を最大限活用してコードの短さを競うコードゴルフという競技もその1つです.当然そのような遊びにはしびれるほど高度な技術が要求され,他人のそれを見るだけでも大いに楽しめます.あなたの知らない超絶技巧プログラミングの世界 というタイトルの本が出版されるくらいです.

常に学習の余地がある楽しさ

最後に,学ぶことの楽しさについて話します.未知の領域に足を踏み入れるのはとてもわくわくすることです.もちろんプログラミングを始める瞬間にも感じることはできるのですが,実際にはプログラミングと呼ばれる領域はとても多岐に渡っており,その中で新しい分野に手を出すたびに新鮮な気分を味わうことができます.僕も,やりたいなぁと思っているけれどまだ本格的に始められずにいるものを挙げろと言われたら,言語だと Rust とか Haskell とか D とか Coq とか Prolog とか,分野だと Web 系とか機械学習とか,まぁキリがありません.このように目の前にわくわくする世界が広がっているのも,プログラミングの楽しさの1つだと思います.



僕が感じるプログラミングの楽しい点は以上の7つにまとめられます.おそらく今後もプログラミングは趣味としてずっと続けると思います.

これからプログラミングを始めようと思っている人にその楽しさが少しでも伝われば幸いです.

*1:この記事によると,これらはプログラマーの3大欲求なのだそうです.

ncurses への誘い

この記事は C / C++ プログラマーを対象として書かれています.ncurses というライブラリの紹介なのですが,調べてみると pythonRuby でも使えるようです(ここら辺の言語, C 用のライブラリなら何でも持ってますね……).

CUI vs GUI

C プログラムには, CUI (キャラクタユーザインターフェース) のものと,GUI (グラフィカルユーザインターフェース) のものがあります.ユーザにとっては GUI の方が圧倒的に直感的で分かりやすいため,何か開発する際に GUI の方が良いなぁと思うこともあるでしょう.しかし,プログラミング学習において GUI より先にまず CUI を学ぶことが多いことからも分かる通り,プログラマの目線から見れば CUI の方が簡単です.とくに入出力に関しては, CUI なら printf,scanf などの関数だけで事が大体済みます.一方 GUI だと,何かを表示したり,キーボード操作を受け付けたりするためには,少々長いコードが必要となってしまいます(どれくらい長くなるかはライブラリにもよりますが……).そのため,GUI であることが望ましいようなプログラムを作る際にも,面倒だからという理由で CUI を選択してしまう人がいることでしょう.

……ちょっと待って下さい.もう 1 つの選択肢を忘れていませんか.
CUIGUI と来たら,そうです, TUI (テキストユーザインターフェース) が残っています.

第3の選択肢,TUI

TUI は,CUI と同じくコンソール上で動きます.CUI では基本的に左上から順番に文字を出力することしかできませんが,TUI ではターミナル画面の好きな位置に文字を表示したり,ユーザの入力をリアルタイムで受け取ったりすることができます.コンソールを使って実質 GUI と同じことができるのです.しかも,ncurses というライブラリを使えば, CUI と同じくらい簡潔なコードで済むのです.

ざっと使い方の説明

とりあえず ncurses で画面の左上に Hello, world! と表示してみましょう. ncurses を使うには,ncurses.h ヘッダをインクルードし,コンパイル後に ncurses ライブラリとリンクします.

/* main.c */
#include <ncurses.h>
int main(){
    initscr();                  // 最初に書く
    addstr("Hello, world!");    // カーソルの位置に"Hello, world!"と表示する
    getch();                    // 何かのキーが押されるまで待つ
    endwin();                   // 最後に書く
    return 0;
}
$ gcc main.c -lncurses

実行すると,"Hello, world!"と表示されるはずです.(環境によっては,押されたキーの文字がプログラム終了後に残るかもしれません.)
カーソルは最初,画面左上(座標 (0, 0))の位置にあります.addstr 関数によって,最初の'H'が(0, 0)の位置に来てその右に残りの"ello, world!"が続くように,文字列"Hello, world!"が表示されます.このときカーソルは文字数分だけ右に動いています.
カーソルを特定の位置に動かすには,move 関数を使います.

move(5, 10);
addstr("Hello, world");

今度は'H'が上から5行目,左から10文字目(ただし上端を0行目,左端を0文字目とする)の位置に表示されます.
printf のようなフォーマット出力は printw 関数でできます.

printw("%d is prime.", 57);

getch 関数は,キーボード入力を1文字ずつ受けとります.

while(getch() != 'a');

'a' が押されるとループを抜けます.その間押されたキーの文字が画面に表示され続けます.これは noecho 関数を使うと表示しないようになります.

noecho();
while(getch() != 'a');

押されたキーは表示されず,カーソルも動きません.echo 関数でもとに戻ります.
また上下左右キーや特殊キーを受けとるためには keypad 関数を事前に呼び出しておきます.

keypad(stdscr, TRUE);
while(getch() != KEY_DOWN);

KEY_DOWN などの定数一覧は man getch で見られます.また今使った stdscr の意味について知りたい人は man ncurses から読んで下さい.
curs_set 関数を用いるとカーソルの表示非表示を切り替えられます.

curs_set(0); // invisible(表示されない)
curs_set(1); // normal(表示される)
curs_set(2); // very visible(環境によってはカーソルの形状が変わる)

getch(); はそのままだとキー入力を待っている間プログラム全体が止まってしまいます.nodelay 関数を使うと待たないようになります.

nodelay(stdscr, TRUE);
for(int i = 0;; ++i){
    move(0, 0);
    printw("%d", i);
    move(1, 0);
    if(getch() == 10) break;
}

また CUI のような入力受付けも可能です.

char buf[256];
getstr(buf);

実質 GUI

上で紹介したことを組み合わせれば,GUI っぽいことがかなりできるようになります.ゲームも作れます.特に学業・仕事の合間にプログラミングをする趣味グラマーは,労力をかけずにすむ TUI を第3の選択肢として頭に入れておくのも悪くないと思います.

この記事があなたの役に立てば幸いです.

学ぶということ

学ぶという行為について知人と話していて賛同を得られたのでここに少し記す.

何を学ぶにしても順序というものがあり,その順序に従って学ばなければ本当の理解は得られないというのは広く知られている.しかし,どういう順序で学べばよいのかを知っているのは,既にその学問を修めた人間だけであるから,初学者は何らかの形で師に教わる必要がある,というのが私の考えの根幹である.

(特に私独自の考えを展開するわけではなく,今まで自分が触れてきた考えをまとめているだけなので,こんな記事は見飽きたという方がいたら申し訳ない)

学ぶ順序を知らないことによる弊害は,数学のような積み重ねの学問において非常に顕著に現れる.たとえば大学数学に興味を持った高校生が何も知らずに本屋に行ったとする.代数学解析学数学基礎論ガロア理論多様体論,圏論,様々な分野の本が並んでいる中で,最初に学ぶべきもの(他の分野の基礎となっており前提知識が必要でないもの)を引き当てることは難しいだろう.特に興味を持ったきっかけが例えば「リーマン予想についてのテレビ番組を見た」というものだったりしたら,まずタイトルにリーマン予想という単語が含まれている本から探そうとするのも仕方ない.リーマン予想について一般人向けに分かりやすく説明した書籍もあるだろうが,そういうものを読んでも結局内容を「ざっくりと知る」だけであって「理解を得る」ことは当然できない*1.かと言ってちゃんとした専門書を買っても,要求される前提知識が高すぎて何も理解することができない.誰もが一度は経験する失敗である.

面白いのは,間違った学習法で生半可な知識を得た素人と,大学などで講義を受けた玄人が会話したときに,素人の浅はかさがいとも簡単に露呈してしまうことである.そしてこのような会話は,前者の態度によっては後者を非常に苛立たせる.特に「色々なことに興味を持って楽しく学ぶだけで良い結果が得られる」という甘い考えを信じている者は相手の苛立ちに気付きにくい.

さてここで独学には大きな障害があることが分かる.自分の学習を自分で管理するため,やりたくないこと,あるいはやる必要が無いと判断したことはやらなくてよい.その結果抜けている部分が生じてしまい,特に基礎が疎かになりやすい.どのようなやり方で学べば理解を得られるのか知らない以上これは仕方ないことである.

しかしここまでのことを知っていれば話は別である.いきなり学びたい内容に手を付けるのではなく,その前にまず「学ぶ順序」から知ろうとすることは可能である.例えば数学ならば,これまでに同じような失敗をした人が多くいるからだろうか,Google検索をかければ学ぶ順序について書いてあるブログ記事などがいくつか見つかる.またSNSなどで上級者に聞くこともできる(ここでも態度に気を付ける必要がある).このようにして得た「学び方」に従えば,少しは独学の限界を引き上げることができるだろう*2.個人的な意見としては,書籍は最初から最後までの内容が連続しているためインターネット上に散在する記事よりも学習に適していると思う.

私は,数度の挫折を経てここまでの内容を悟るまでに長い時間がかかった.みな,長い時間をかけて理想の学び方を探してゆくのだろう.この記事がそんな誰かの助けになれば幸いである.

*1:最悪のパターンは,ざっくりと知った知識をもとに,明後日の方向に独自の考えを展開し始めることである.「菅数論」をご存知だろうか……

*2:もちろんこれができない学問もある.例えば文献の少ない古代言語を順序立てて学習するのは難しいだろうから,右も左も分からないまま茨の道を歩くことになる.え,そういうのが好き?ぼくも好き

【闇】【黒魔術】【C++】絶対にやってはいけない inf テク

皆さんこんばんは.今回はちょっと好まれなさそうなC++の使い方を紹介します.

たとえばある int 型配列の最小値が知りたいとき,皆さんはどうしていますか.

std::vector<int> a = something;
int min = 100000000; /* なんか大きな値 */
for(auto i : a){
    min = std::min(min, i);
}

のようにすると思います.この記事のテーマはこの「100000000; /* なんか大きな値 */」のところです.
いつだったかテレビに登場したソースコード内に 1145141919810893364364 という数値が登場して話題になったことがありました(2chのスレ)が,このように「なんか大きな値」はプログラムを書いているとしばしば必要になります.
多くの場合 inf といった名前の constexpr 変数に格納(あるいはdefine)されることが多いですが, 32bit整数型や64bit整数型,浮動小数点型などによって異なる値を使わなければならないため,linf,INF などと変数が増えていってしまいます.

それを † 闇 C + + † の力で解決してしまおう,というのが今回の記事です.つまり

int a = inf;    // int型に収まる大きな値が代入される
long long b = inf;    // long long型に収まる大きな値が代入される
double c = inf;    // double型に収まる大きな値が代入される

というように,代入式の左辺の型によって代入する値を変えたいわけです.

これはキャスト演算子オーバーロードすることによって可能になります.

struct Inf{
    constexpr operator int(){
        return INT_MAX;    //INT_MAXは<climits>で定義されている int の最大値
    }
};

としておけば,

Inf inf;
int a = inf;

とすることで inf::operator int() が呼ばれて a にはその返り値である INT_MAX が代入されるわけです.ちなみに inf::operator int() を static にすることはできないみたいですね.
struct Inf の定義と inf の宣言をまとめると,

struct{
    constexpr operator int(){
        return INT_MAX;
    }
} inf;

となります.またconstexprが付いているので

constexpr int a = inf;

ということも可能です.

こうして色々な型の最大値に化けられる inf を作ることができました.

今度はこれに負号を付けて -inf とすると最小値が得られるようにしてみましょう.つまり

int a = -inf;

としたときに,-INT_MAX = -(2^31 - 1) ではなく INT_MIN = -2^31 が代入されるようにしたいわけです.
今度は inf.operator-() をオーバーロードして

constexpr auto operator-(){
    struct{
        constexpr operator int(){ return INT_MIN; }
    } ret;
    return ret;
}

とすれば良いです.inf::operator-() が呼ばれて ret が返る → ret.operator int() が呼ばれて INT_MIN が返る → a に INT_MIN が代入されるという流れになります.

ちなみに各型の最大値は次のようになっています.

最大値 最小値 ヘッダ
unsigned char UCHAR_MAX climits
signed char SCHAR_MAX SCHAR_MIN climits
char CHAR_MAX CHAR_MIN climits
unsigned short USHRT_MAX climits
short SHRT_MAX SHRT_MIN climits
unsigned int UINT_MAX climits
int INT_MAX INT_MIN climits
unsigned long ULONG_MAX climits
long LONG_MAX LONG_MIN climits
unsigned long long ULLONG_MAX climits
long long LLONG_MAX LLONG_MIN climits
float FLT_MAX cfloat
double DBL_MAX cfloat
long double LDBL_MAX cfloat

(訂正 浮動小数点型の最小値のところにFLT_MIN,DBL_MIN,LDBL_MINを書いていましたがこれらは正の最小値でした)

また,cstdintヘッダのint32_tなどはこれらの型のエイリアスとして定義されるため,例えば using int32_t = int; となっていた場合 operator int() と operator int32_t() を別々に定義することはできません.

これらを全てまとめると次のようになります.

struct Inf{
	constexpr operator unsigned char(){ return UCHAR_MAX; }
	constexpr operator signed char(){ return SCHAR_MAX; }
	constexpr operator char(){ return CHAR_MAX; }
	constexpr operator unsigned short(){ return USHRT_MAX; }
	constexpr operator short(){ return SHRT_MAX; }
	constexpr operator unsigned int(){ return UINT_MAX; }
	constexpr operator int(){ return INT_MAX; }
	constexpr operator unsigned long(){ return ULONG_MAX; }
	constexpr operator long(){ return LONG_MAX; }
	constexpr operator unsigned long long(){ return ULLONG_MAX; }
	constexpr operator long long(){ return LLONG_MAX; }
	constexpr operator float(){ return FLT_MAX; }
	constexpr operator double(){ return DBL_MAX; }
	constexpr operator long double(){ return LDBL_MAX; }
	constexpr auto operator-(){
		struct{
			constexpr operator char(){ return CHAR_MIN; }
			constexpr operator signed char(){ return SCHAR_MIN; }
			constexpr operator short(){ return SHRT_MIN; }
			constexpr operator int(){ return INT_MIN; }
			constexpr operator long(){ return LONG_MIN; }
			constexpr operator long long(){ return LLONG_MIN; }
		} ret;
		return ret;
	}
} inf;

追記

何人かの方に std::numeric_limits の使用を勧められたためそれを使って書き換えてみます.

std::numeric_limitsを使ってmax,minを得る方法としては

std::numeric_limits<int>::max() // INT_MAX
std::numeric_limits<double>::lowest() // double型の最も低い値

などのようになります.(訂正,minではなくlowestでした.)
ただこれをそのまま使ってしまうと「inf + inf でオーバーロードしてしまったため inf の値を半分にする」ということが即座にできないため実際に使用する場合やはりキャスト演算子をもつ構造体を作っておく必要があります.

maxについては次のようにすれば長かった部分を短くすることができます.

struct{
	template<class T>
	constexpr operator T(){
		return std::numeric_limits<T>::max();
	}
} inf;

ただしこのようにtemplateを使おうとすると,負号を付けたときの処理を上のようにローカル構造体で片付けることができないため,負の inf についても構造体を作る必要があります.

struct{
	template<class T>
	constexpr operator T(){
		return std::numeric_limits<T>::lowest();
	}
} negative_inf;

そしてこれらにメンバ operator-() を持たせて,-inf が negative_inf に,-negative_inf が inf になるようにすれば良いです.
全体では次のようになります.

struct{
	template<class T>
	constexpr operator T(){
		return std::numeric_limits<T>::max();
	}
	constexpr auto operator-();
} inf;

struct{
	template<class T>
	constexpr operator T(){
		return std::numeric_limits<T>::lowest();
	}
	constexpr auto operator-();
} negative_inf;

constexpr auto decltype(inf)::operator-(){
	return negative_inf;
}

constexpr auto decltype(negative_inf)::operator-(){
	return inf;
}

雑記

人は考える。
自分は常に思考し続ける人間を理想像として掲げている。
考えるという行為は人間において本質的であり,最も重要である。
しかし実際はいつでも十分な思考を巡らすことができるわけではなく,思考を放棄することもある。これは悪である。
考え続けていると疲れてくる。考えること自体が嫌になってくる。
考えることは良いことだとしても,頭が狂ってしまうほど考え続けることは果たして良いことだろうか。
人間である以上思考は完全ではない。間違えることもある。
自分がどれだけ思考できるのか,その限界は知っておかねばならない。さらにそれを忘れてはならない。
しかし限界がどこにあるのか客観的に記述するのは難しい。長い経験が必要。
未来は予測できることもあるが,予測できないこともある。
自分がどれだけ未来を正確に予測できるか把握しておかねばならない。
自分に未来を予測する能力があると思い込んでしまったことがあった。
自分の予測が当たるとさらに能力を信頼するようになり,自分の予測が外れるとその経験が能力の精度を高めたと言って喜んだ。
実際は当然未来を正確に予測することはできない。能力を過信して油断し,思考を止めるなど言語道断である。
予測が外れる可能性も常に覚えておかねばならない。外れたときに焦りすぎないように。
また,予測が外れることを当てにするのも間違っている。予測は当たるとも外れるとも言えない。当たるときは当たるし外れるときは外れる,それだけである。
人は過去をもとに未来を予測している。では過去のことはどれだけ覚えているか。
人は過去を記憶する。しかしその記憶は本当に正確か。
記憶はよく勝手に書き換えられる。自分の記憶力を過信してはならない。
人は様々な手段によって知識を増やす。しかし知識が増える瞬間を全て記憶することはできない。
今の自分が知識として持っていることを,自分がいつ学んだのか,思い出せないことが多い。
故に過去の自分を見返したときに,現在の自分の知識を当時の自分の知識と混同することも多い。
知識が蓄積されていくとき,知識の変化を記録することは難しい。
記録しようと努力するのではなく,記録できないと割り切るべきである。
人は忘れる。
しかし現在の出来事を未来の自分がどれだけ覚えているか考えるのは難しい。
ずっと覚えていたいと思っていたのになぜかいつのまにか忘れていたり,どうせ忘れているだろうと思っていたらなぜかちゃんと記憶に残り続けていたりする。思い出せるときと思い出せないときがあったりもする。
注意,逆もまた然り。覚えていたいと思っていたことをずっと覚えていられることもあるし,忘れたいと思っていることを案外忘れられることもある。
また「記憶,覚えたこと」に対して「知識,知っていること」は消えないと思いがちだが,実際は時間が経てば知識そのものが失われることもある。
特に自分の思考によって生まれた知識の変化には気づきにくい。
人は常に自分が正しいと思っている。
自分の間違いを認めるときでさえ,その瞬間の自分(つまり間違いを認める自分)は正しいと思っている。
これは当然であり,それが正しいという言葉の本質である。
過去の自分が正しいと思っていたことが正しいかどうか疑うことは重要である。
さらに現在の自分が正しいと思っていることを未来の自分が正しくないと思う可能性も考えておく方が良いだろう。
人は精神状態を一定に保つことができない。
上述のような思考を永遠に続けることはできない。
どれだけ思考を続けることができるのか正確に判断し,適度な休息をとる必要がある。
人は感情を持つ。
ここから先,感情の存在を事実と認めた上で話を進める。
感情について考えたり,感情を制御したりしようとすることで,それまでの感情が失われる[ことがある]。
感情は人間社会の中で刷り込まれることによって生まれる[のではないだろうか]。
そういった意味で,何もない状態から発生する真実の感情は欲以外に存在しない[と思っている]。
一度失った感情も,同じように刷り込むことによって取り戻すことができる[気がする]。
それらを偽物の感情として否定することは必ずしもできない[可能性がある]。