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
こうして rax レジスタに商， rdx レジスタに余りが格納されます．使える 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 問が残っているので，もし続きができたらまた投稿したいと思います．では．
