はじめに
2020年に行われた言語アップデートの前に書いた記事なので、いくつか現在のAWKには当てはまらない記述があります。
drken さんの記事で紹介されていた AtCoder に登録したら解くべき精選 10 問 をAWKで解いてみました。
AtCoder Beginners Selection コンテストトップ
注意点として、AtCoderのAWK (mawk) はオーバーフローを起こします。いろいろ試してみましたが、$2,147,483,647$ (=INT_MAX) よりも大きな値は $2,147,483,647$ になるようです。
（追記）整数値として出力する際は $2,147,483,647$ になるようですが、AWKの数値は内部的には浮動小数点数なので、大きな値も精度を落として保持できます。よって、大小比較程度なら可能な場合もあります。
（さらに追記）整数値として出力する際、printfのフォーマット文字列として"%d"を使っていたために $2,147,483,647$ にされていました。"%.f"とすればさらに大きな値も整数として出力でき、double型の有効桁数通りに9e15くらいまでの整数なら誤差なく保持できます。
入力について
AWKの入力は少し特殊です。なぜなら、AWKはテキスト、特にデータファイル処理に特化した言語だからです。
一行読み込んでスクリプトを実行するのを繰り返し、BEGIN ブロックや END ブロックを使って特別な操作をするのが基本的な使い方になります。
一行読み込まれると、行全体を $0 に代入し、そのあと行全体を空白・タブ・改行で区切って先頭から順に $1 , $2 , ……に代入し (これをフィールドと呼びます) 、フィールドの数を変数 NF に代入し、変数 NR をインクリメントします。
これにより、変数 NR は現在処理している行の番号を表すようになります。
実は、この「行の更新」とでもいうべき操作を手動で行う方法があります。getline という組み込み関数 (厳密には関数とは区別されるべきだと思います、それは呼び出しに括弧が必要ない、逆にあると構文エラーになるからです) を呼び出すと、その時点で上で紹介した変数たちがすべて次の行の内容に更新されます。(Nobuyukiさん、ご指摘ありがとうございます。)
問題の解答
第0問:PracticeA - はじめてのあっとこーだー
AWKの入力は少し特殊です。ここで問題になるのが、入力が複数行にわたる場合はどうすればいいのか？ということです。
二つの方法を紹介します。
- 入力を一気に読み込む
RS という、入力全体を行に区切るための区切り文字を表す変数があります。初期値は改行文字です。
これを空文字列にするとどうなるでしょう？……少なくとも今回の場合、入力すべてが一行と解釈されます。実際には、改行文字が二つ並ぶまでを一行としているようです。
これを利用した回答コードは次のようになります。
BEGIN{RS=""}{print $1+$2+$3,$4}
{} が一つの命令のかたまりで、先頭につく式があればそれの真偽により、なければ常にそのブロックが実行されます。
BEGIN , END は特別扱いで、それぞれ入力を読み込みだす前、すべての処理が終わった後に実行されます。
上のコードは、まず BEGIN ブロックで RS に空文字列を代入し、入力の全体を読んで二番目のブロックを実行しています。
二番目のブロックでは、$1 , $2 , $3 を足し合わせ (ここで型を気にする必要はありません、AWKがうまくやってくれます) 、$4 とともにカンマ区切りで print に渡しています。
print はカンマを空白文字に置き換えつつ標準出力に書き出し、最後に改行します。ファイルに書き出すこともできますが、競技プログラミングでは使いません。
- 入力を変数にためておいて、
ENDブロックで処理する
ブロックの前に式を書いておくと、それが真のときだけそのブロックが実行されます。これと変数 NR を組み合わせると、(少し面倒ですが) 入力に合わせて変数に代入したりができます。
NR==1{a=$1}NR==2{a+=$1+$2}NR==3{print a,$1}
END ブロックで処理すると書きましたが、三行目の処理のときに出力してしまって問題ありません。
変数は初期化せずに使うと空文字列 (=0) で勝手に初期化されるので、もう少し処理をまとめてこのようにも書けます。
NR<=2{a+=$1+$2}NR==3{print a,$1}
NR==1 のとき $2 は空文字列です。また、フィールド変数は一行ごとにすべて更新されるので、NF<=4 のときに $5 にアクセスしたら前の行の $5 が出てきた！なんてことも起こりません。
第1問:ABC086A - Product
AWKにも三項演算子があります。
{print $1*$2%2?"Odd":"Even"}
AWKで false とされるのは、数値の 0 と空文字列のみです。(驚くべきことに、文字列 "0" はAWKでは true です。)
さて、上のコードは縮みます。
$0=$1*$2%2?"Odd":"Even"
ブロックが見当たりませんが、これは何が起こっているのでしょうか？
「AWK ワンライナー」などと検索するとよく出てくる事実なのですが、省略されたブロックは自動的に {print $0} とみなされます。
つまり、上のコードはこう解釈されるということです。
( $0=$1*$2%2?"Odd":"Even" ){ print $0 }
ここで、 $0 を print しているのがミソで、上のコードでは $0 に出力したい文字列を代入することで、print と書くのを避けているのです。"Odd" も "Even" も真ですから、うまくブロックが実行されます。
ブロックの外でも代入が書けるのか、ならば……と思って書いた次のようなコードは構文エラーとなります。
print $1*$2%2?"Odd":"Even"
ブロックの外側では print は使えません。組み込み関数の int などは使えるので、このことは print がただの関数ではない、いっそ for や if と似たような扱いであることを示しています。(AWKにも for 文などは用意されています、そしてブロックの内側でのみ使えます。)
上の getline と同じく、print にも括弧が必要ないことからもわかります。
第2問:ABC081A - Placing Marbles
$1$ をカウントするのには、元の文字列にいくら変更を加えてもよいので、組み込み関数 gsub を使うと簡単でしょう。これは第三引数 (なければ $0) 中の第一引数にマッチする部分文字列を全て第二引数の文字列に置換し、置換の回数を返します。
0<=($0=gsub(1,0))
gsub の第一・二引数が数値ですが、AWKがうまくやってくれます。具体的には、"1" と "0" という扱いになります。
$0 \le$ はなぜ必要かというと、gsub が 0 を返したときに、そのままでは false 扱いとなり {print $0} が実行されないからです。
実は、演算子の優先順位的に必要に見える括弧を外しても動きます。
0<=$0=gsub(1,0)
Rubyと同じですね、AWKは頭がいい
ところで、先ほど少し言及しましたが、"0" は true です。ということは、gsub の返り値を文字列にできれば、$0 \le$ はいらなくなるということです。
文字列と数値を連結すると、文字列になります。これを使えばよさそうですが、連結の演算子はどのようなものでしょう？
これはかなり特殊で、「並べて書けば連結される」が正解です。優先順位は四則演算より下、比較演算より上です。当然構文エラーになると動かないので、例えば変数 a と b を連結したいときは a b とスペースを空けて (そのスペースは無視されます) 書く必要があります。今回は gsub 右の括弧の横にスペースを空けず書いてもちゃんと動きます。
$0=gsub(1,0)""
最後の一押しです、初期化されていない変数を使うと空文字列になるのですから、適当に未使用の変数 a でもくっつけておけば動きます。
$0=gsub(1,0)a
第3問:ABC081B - Shift only
一行目の情報はいりません、二行目で各フィールドごとに $2$ で割れる回数をカウントし、それの最小値を出力します。
上で少し触れた for 文などですが、文法はC言語とほとんど変わりません。(配列の要素でループを行う文法がありますが、触れません。)
NR==2{
ans=1e9;
for(i=1;i<=NF;i++){
cnt=0;
while($i%2==0){$i/=2;cnt++}
ans=ans<cnt?ans:cnt;
}
print ans
}
1e9 は指数表記で $10^9$ を表します。
$i とすると i 番目のフィールドにアクセスできます。また、フィールドの値は変更することができます。
AWKでは数値はすべて浮動小数点数ですが、% も問題なく動作します。(これにより、a%1==0 で a が整数か小数かを判定することができます。)
第4問:ABC087B - Coins
これは第0問で紹介した、入力を一気に読み込む方法がよいでしょう。
BEGIN{RS=""}
{
for(i=0;i<=$1;i++){
for(j=0;j<=$2;j++){
for(k=0;k<=$3;k++){
cnt+=i*500+j*100+k*50==$4
}
}
}
print cnt
}
比較演算は true または false として 1 または 0 を返します。
第5問:ABC083B - Some Sums
数値の各桁の和を求めるのに、$10$ で割りながら計算する方法をとっても良いのですが、せっかく数値⇔文字列の柔軟な変換があるのですから、一文字ずつ部分文字列を切り出して計算しましょう。
{
for(i=1;i<=$1;i++){
sum=0;
for(j=1;j<=length(i);j++)sum+=substr(i,j,1);
if($2<=sum&&sum<=$3)ans+=i;
}
print ans
}
length は引数の文字列の長さを返す関数、substr は第一引数の部分文字列を返す関数です。
substr の第二引数は切り出す位置 (1-indexd) 、第三引数は切り出す長さです。
第6問:ABC088B - Card Game for Two
AtCoderのAWKではソートが使えません。なので、自分で実装する必要がありますが、幸い今回は $1 \le a_i \le 100$ なのでバケツソートが使えます。(ちなみに、AWKの配列は連想配列です。)
入力の一行目は、今回も読み飛ばして構いません。
NR==2{
for(i=1;i<=NF;i++)a[$i]++;
for(i=100;i>0;i--){
while(a[i]){
ans+=flag++%2?-i:+i;
a[i]--
}
}
print ans
}
まず二行目で、全ての値を配列 a でカウントします。
次に、三行目のループですが、これは値の大きいものから順に使っていくことと対応します。
a[i] の値が $0$ より大である間、ans に値を足し引きしつつ、使ったことを示すために a[i] をデクリメントしています。
変数 flag を用意して、これが偶数のとき (flag%2==0 (==false)) はAliceがカードを取るので +i 、奇数の時はBobがカードを取るので -i を ans に足しています。後置インクリメントのせいで少し読みにくいかもしれませんが、わかりやすく書き下すと
ans+=flag%2==1?-i:+i;flag+=1;
と同値です。
第7問:ABC085B - Kagami Mochi
二行目以降の値のユニークをとります、これにも配列が使えます。
出力は END ブロックで行いましょう。
NR>=2{ans+=!a[$1]++}END{print ans}
配列の値は、初めてアクセスしたとき空文字列ですから、論理否定をとれば $1$ になります。
これを ans に足すと同時に a[$1] をインクリメントしておけば、以後同じ値にアクセスしても ans+=0 となるだけです。
第8問:ABC085C - Otoshidama
解が見つかったときは、for 文から break で抜けるより、exit でプログラムの実行を終了してしまったほうが手っ取り早いでしょう。
{
for(i=0;i<=$1;i++){
for(j=0;j<=$1;j++){
k=$1-i-j;
if(k>=0&&i*10000+j*5000+k*1000==$2)
{
print i,j,k;
exit
}
}
}
print -1,-1,-1
}
実行時間は $1380{\rm ms}$ でした、速度に難がありますね……(Perl6よりはマシですが)
第9問:ABC049C - 白昼夢 / Daydream
正規表現が使えるので一発です。
$0=/^(dream|dreamer|erase|eraser)*$/?"YES":"NO"
ただ、AWKの正規表現は他の言語に比べて機能面で貧弱なので、どんな機能が使えてどんな機能が使えないのかをしっかり調べて書く必要があります。
また、gsub を四回使っても解けます。
{
gsub("eraser","");
gsub("erase","");
gsub("dreamer","");
gsub("dream","");
print $0?"NO":"YES"
}
gsub で置換する文字列の順番に注意しましょう。
gsub を繰り返した最後に $0 が空文字列になっていれば "YES" 、そうでなければ "NO" です。
(追記) 嘘解法でした。 MMNMMさん、ご指摘ありがとうございます。
dreaerasem を入力すると YES を出力しますが、正しい答えは NO です。
gsub で空文字列に置換すると、前後が連結してしまうので、適当な文字 (入力に含まれない) を代わりに入れておいて、最後に消すとよさそうです。
{
gsub("eraser","!");
gsub("erase","!");
gsub("dreamer","!");
gsub("dream","!");
gsub("!","");
print $0?"NO":"YES"
}
これは dreaerasem に対してもちゃんと NO を出力します。
第10問:ABC086C - Traveling
AWKには abs の機能を持つ組み込み関数はありません。自分で定義しましょう。
function abs(a){return a>0?a:-a}
NR>=2{
T=$1-t;
X=abs($2-x)+abs($3-y);
t=$1;x=$2;y=$3;
flag+=T<X||T%2!=X%2
}
END{print flag?"No":"Yes"}
関数定義の文法は見たままです。
一回でも T<X||T%2!=X%2 が成り立てば、変数 flag は非ゼロになります。
${\rm abs}(a) = {\sqrt{a^2}} = (a^2)^{0.5}$ が成り立つので、関数 abs は次のように書くこともできます。
function abs(a){return (a^2)^.5}
$.5 = 0.5$ です。また、べき乗演算子 ^ の結合方向の関係で、括弧が必ず必要です。
この方法だと、演算子の優先順位が高いので、abs 関数を定義しなくても式中に簡単に埋め込めます。
X=(($2-x)^2)^.5+(($3-y)^2)^.5;
おわりに
上で紹介した問題群はなかなかシンプルに書くのが難しいですが、ほんの少しの四則演算で簡単に答えが出せる問題は、AWKで書くとコードが非常に短くなります。
ただ、第1問と第2問のように $0 に代入して答えを出力しようとするとき、うっかり計算結果が $0$ になってしまうと、出力されずWAになってしまうので、気を付けましょう。
（追記） こうしてABS11問の回答コードを眺めてみると、どうも第0問だけが行ごとにちまちま処理を切り替えて面倒なように感じます。これを何とかしましょう。
a+=$1+$2 は削れないので、これを使って今三行目かどうかの判定をしてみます。
数値と文字列の足し算、例えば 6 + "test" はどういう値になるでしょう？実は、数値に変換できない文字列はすべて $0$ になります。
このことを使うと、例えば、元の a と更新後の a+=$1+$2 の値が等しいか異なるかを確認することで、今三行目かどうかを判定できます。
$0=a==(a+=$1+$2)?a" "$1:""
三行目以外で出力しないよう、$0 には空文字列を代入しておきます。
もう少し縮みます。
$a = b \Leftrightarrow a - b = 0$ ですから、真偽を逆転させると == → - となって1Byteの短縮です。
これと未使用の変数は空文字列であることを利用して24Byteのコードが作れました。
$0=a-(a+=$1+$2)?s:a" "$1
もう一つ、方法があります。$1 を数値として評価して $0$ であれば三行目です。
$0=0+$1==0?a" "$1:0>a+=$1+$2
数値として評価するために $1 に $0$ を足しています。
0>a+=$1+$2 としているのは、これも三行目以外で出力されないよう、式全体の評価結果を false にするためです。
実は、数値として評価するには接頭辞 + をつけるだけで充分です。真偽を逆転させて、これも偶然24Byteになりました。
$0=+$1?0>a+=$1+$2:a" "$1
このように、AWKは変数の更新などを上手く調整することで、入力が複数行にわたるときでも最短コードになりえる可能性を秘めています。
（さらに追記）20Byteまで縮みました！
a~a+=$1+$2,$0=a" "$1
元の a と更新後の a+=$1+$2 の値が等しいか異なるかを確認する部分は本来ならば==を使うところですが、文字列マッチング~を使っても正しく動きます。a~(a+=$1+$2)は括弧を外しても正しく解釈され、a~a+=$1+$2とできます。
加えて範囲パターンを用いることで、三項演算子と余計な0>aを省くことに成功しました。