はじめに

ImageMagickというプログラミング言語があることを皆さんはご存知でしょうか？

この言語は汎用的なプログラミング言語のはずなのに、何故か画像処理用途としてしか使われていないようです。もったいないですよね。そこで、プログラミング言語 ImageMagickの汎用性を広めるべく、競プロ入門に最適な問題が集まっている AtCoder Beginners Selection - AtCoder をImageMagickで解いてみました！この記事を読んでぜひ皆さんもImageMagickで競技プログラミングを始めてみてください！

0問目 cat

まずは前提として入出力処理の書き方から始めましょう。 ImageMagick では入力のバイト列を受け取ってそのまま出力するcatプログラムは以下のように書くことができます。

convert -depth 8 -size 1x1 gray:- -

実際に echo "いめーじまじっく" | convert -depth 8 -size 1x1 gray:- - と実行すると いめーじまじっく と表示されます。各コマンド・引数の意味は以下の通りです。

convert : ImageMagickが提供するコマンドの一つ。画像変換をしたそうなコマンド名前ですが、そんなことはさせてあげません。
-depth 8 : 入力文字列を1バイト単位で処理するための引数です。何も指定しない場合 -depth 16 となり 2バイトずつ処理してしまうので注意です。
-size 1x1 : 1x1毎に区切るための引数です。
gray:- : - は入力を(ファイルでなく)標準入力から取るという意味です。 gray:- とフォーマットを指定(raw gray)しています。

1問目 ABC081A - Placing Marbles

それでは早速解いていきましょう。この問題は、0 or 1 の $s_0,s_1,s_2$ が与えられるので、足し算をするだけの問題です。例えば入力101には 2 を、入力 000 には 0 を出力します。この問題のImageMagickでの解答コードは以下になります。

convert \( -size 1x1 -depth 8 gray:- \) \( -resize '2x1!' -fx '
sum = (u[0] - 48/256) + (u[1] - 48/256) + (u[2] - 48/256);
i == 0 ? sum + 48/256 : 10/256
'  \) -

このコードを code.sh として保存し、実際に echo "101" | sh code.sh と実行すると 2\n が表示されます。各引数の意味は以下の通りです。

$ -size 1x1 -depth 8 gray:- $ : 先程の例と同じく入力を1バイト単位でパースします。
$ -fx '...' -resize '2x1!' $ : ↑のパースにより、入力は配列 u の中に保存されています。これを -fx というオペレータを使って頑張って望む出力に変換します。ImageMagickでは予め出力のサイズを定数で定めておく必要があるので -resize '2x1!' として出力は2バイト(答えと改行)であると宣言します。¹

さて、-fx の中身は以下でした。

sum = (u[0] - 48/256) + (u[1] - 48/256) + (u[2] - 48/256);
i == 0 ? sum + 48/256 : 10/256

u[0] などの中身は[0,1]の範囲で正規化されたASCIIコードとして入っており、'0' なら 48/256 が、 '1' なら 49/256 が格納されています。 i == 0、つまり出力の1文字目ならその総和sumを正規化されたASCIIコードとして出力し、そうでない場合、つまり出力の2文字目なら '\n' のASCIIコードである 10 を正規化されたASCIIコード 10/256 として出力しています。直感的ですね！

2問目 PracticeA - Welcome to AtCoder

以下のようにスペース区切りの3つの数字(範囲は[1,1000])と文字列(長さは最大100) が与えられるので、その数字3つの和と文字列を出力する問題です。

72
128 256
myonmyon

があれば

456 myonmyon

と出力するわけですね。この問題のImageMagickでの解答コードは以下になります。

convert \( -size 1x1 -depth 8 gray:- \) \( -resize '110x1!' -fx '
for((qa=0,qx=0),abs(u[qa]-10/256)>=1/256,(qx=qx*10+floor(u[qa]*256-48),qa++));
for((qb=qa+1,qy=0),abs(u[qb]-32/256)>=1/256,(qy=qy*10+floor(u[qb]*256-48),qb++));
for((qc=qb+1,qz=0),abs(u[qc]-10/256)>=1/256,(qz=qz*10+floor(u[qc]*256-48),qc++));
sum=qx+qy+qz;
txt=i+qb+1<n?u[i+qb+1]*256:0;
ia=floor(sum>=1000?sum/1000:sum>=100?sum/100:sum>=10?sum/10:sum)+48;
ib=floor(sum>=1000?sum%1000/100:sum>=100?sum%100/10:sum>=10?sum%10:-16)+48;
ic=floor(sum>=1000?sum%100/10:sum>=100?sum%10:sum>=10?-16:txt-48)+48;
id=floor(sum>=1000?sum%10:sum>=100?-16:txt-48)+48;
ie=floor(sum>=1000?-16:txt-48)+48;
(i==0?ia:i==1?ib:i==2?ic:i==3?id:i==4?ie:txt)/256
'  \) -

このコードを code.sh として保存し、実際に echo "72\n128 256\nmyonmyon" | sh code.sh と実行すると 456 myonmyon\n と表示されます。各引数については先程の問題と同様の仕組みです。出力の長さは最大110文字なので、-resize '110x1!' とし、なにもない場合は '\0' を出力しています。このコードの -fx は冗長ですが、本質的には以下のようなコードとなります。

for((qa = 0, qx = 0), u[qa] != 10/256, (qx = qx*10+u[qa]*256-48, qa++));
for((qb = qa+1, qy = 0), u[qb] != 32/256, (qy = qy*10+u[qb]*256-48, qb++));
for((qc = qb+1, qz = 0), u[qc] != 10/256, (qz = qz*10+u[qc]*256-48, qc++));
sum = qx+qy+qz;
txt = i+qb+1<n ? u[i+qb+1]*256 : 0;
ia = sum>=1000 ? sum/1000 : sum>=100 ? sum/100+48 : sum>=10 ? sum/10+48 : sum+48;
ib = sum>=1000 ? sum%1000/100+48 : sum>=100 ? sum%100/10+48 : sum>=10 ? sum%10+48 :32;
ic = sum>=1000 ? sum%100/10+48 : sum>=100 ? sum%10+48 : sum>=10 ? 32 : txt;
id = sum>=1000 ? sum%10+48 : sum>=100 ? 32 : txt;
ie = sum>=1000 ? 32 : txt;
(i==0 ? ia : i==1 ? ib : i==2 ? ic : i==3 ? id : i==4 ? ie : txt) / 256

ImageMagickでは内部的にはQ16で処理するので素朴に書くと精度の問題で想定と少し異なった出力をしてしまいます。そこで元のコードでは適宜floorを入れたりしているわけですね。コツとして、128/256と129/256あたりの境界に注意しておくと吉です。 ImageMagickの変数名には数字が使えないので適宜a,b,c,とアルファベット順でこのコードでは変数を宣言しています。変数の説明は以下の通りです。

qa : 最初の改行文字のindex
qx : 1つめの数字を10進数としてパースした値
qb : 2つ目の区切り文字である空白文字のindex
qy : 2つめの数字を10進数としてパースした値
qc : 3つ目の区切り文字である改行文字のindex
qz : 3つめの数字を10進数としてパースした値
sum : 答えとなる3つの数字の和
txt : 文字列を出力する場合、その出力場所で出力すべき文字。 n は入力の長さが入っています。
ia..ie : 1文字目から5文字目までは文字列を出力するか数字を出力するか入力に依存するので、それに応じて分岐して計算した出力文字。

最後に

画像処理だけでなく競プロまでできるなんて、ImageMagick は最高のプログラミング言語ですね。みなさんもぜひImageMagickで競プロをしてみてください！

なお、僕はここまで解いただけでやる気力が失せたので、もうImageMagickを画像処理用途以外には使わないと思います。

実は頑張れば出力を可変長にできるかもしれません。↩

(/^^)/⌒●~*$ a(){ a|a& };a

\e[i

AtCoder Beginners Selection を ImageMagick でやってみた！

はじめに

0問目 cat

1問目 ABC081A - Placing Marbles

2問目 PracticeA - Welcome to AtCoder

最後に