Help us understand the problem. What is going on with this article?

jqコマンドでAtCoder Beginners Selectionを解いてみた

TL; DR

jqコマンドって?

主にJSONを加工するのに使われるコマンドです。
例えば、以下のjsonを考えます。

input.json
[{ "shop": "横浜", "area": "関東", "sales": 100 },
 { "shop": "盛岡", "area": "東北", "sales": 300 },
 { "shop": "前橋", "area": "関東", "sales": 500 }]

このjsonに対して、関東エリアの売り上げの合計を求めて、末尾に「万円」をつけて出力したいと思います。
jqを使うと、以下のような短いコマンドで実現することができます。

$ jq 'map(select(.area == "関東") | .sales) | "\(add)万円"' input.json
"600万円"

jqコマンドの細かい機能についてはjq Manual(英語)と、このドキュメントの日本語訳記事である『軽量JSONパーサー『jq』のドキュメント:『jq Manual』をざっくり日本語訳してみました』に大変詳しいです。
本記事では、jqコマンドの説明はAtCoder Beginners Selectionを解くための最低限の説明に留めます。

jqのフィルターの仕組み

jqコマンドの一つ目の引数をフィルターと呼びます。

フィルターは パイプ(|)で繋がれた複数のフィルターの形をしています。

フィルター := フィルター | フィルター | フィルター ...

単一のデータが入力として渡される例

以下の例は、フィルターの入力として1が渡され、最終的に"数字は12"が出力される例です。

$ echo 1 | jq ' . * 2 | . + 10 | tostring | "数字は" + .'
"数字は12"

以下のように処理が進みます。

  • 1はまず最初に . * 2というフィルターの入力として渡されます。このフィルター中の.は入力を表します。出力は入力を2倍した値、すなわち2になります。
  • その次に2. + 10というフィルターの入力となり、12が出力されます。
  • 12tostringというフィルターの入力となり、 "12"が出力されます。
  • "12""数字は" + .というフィルターの入力となり、 最終的に"数字は12"が出力されます。

複数のデータが入力として渡される例

フィルターには複数のデータが入力として渡され得ます。複数のデータと1つの配列を渡すのはjqでは区別されていることに注意してください。

$ echo '1 2 3' | jq ' . * 2 | . + 10 | tostring | "数字は" + .'
"数字は12"
"数字は14"
"数字は16"

今回よく出てくる機能

.

データ自身を表します。

$ echo 1 | jq '.'
1

select(条件)

データを下流に流すかどうかを振り分けます。
条件が真のときはデータを素通りさせ、条件が偽のときはデータを流しません。

$ echo '1 2 3 4 5' | jq 'select(. > 2)'
3
4
5

range(begin; end)

begin (begin+1) (begin+2) ... (end-1)の複数の数値データを生成します。

$ echo '{}' | jq 'range(1;5)'
1
2
3
4

[複数のデータ]

複数のデータを一つの配列にまとめ上げます。

$ echo '{}' | jq '[range(1;5)]'
[
  1,
  2,
  3,
  4
]

[]

配列複数のデータに分解します。

$ echo '[1, 2, 3]' | jq '.[]'
1
2
3

as $name

データを変数に束縛します。

$ echo 3 | jq '. as $input | . * 10 | . + $input'
33

map(フィルター)

配列のそれぞれの要素にフィルターを適用します。

$ echo '[1, 2, 3]' | jq 'map(. * 10)'
[
  10,
  20,
  30
]

[i]

配列のi番目の要素を取り出します。

$ echo '[1, 2, 3]' | jq '.[2]'       
3

あとは問題の解答を見ながら解説していきます。

問題&解答

断り書き

Otoshidamaは間違いなくTLEします。
実行コマンドはjq -rRs -f code.jq inputで、入力コードはファイルcode.jqとして保存され、テストケース入力はファイルinputにあるとします。

それではAtCoder Beginners Selectionの問題の解答を載せていきます。問題へのリンクは各セクションのタイトルをクリックすると辿れます。

PracticeA - Welcome to AtCoder

split("\n") as $input |
($input[0] | tonumber) as $a |
($input[1] | split(" ")) as $second_line |
($second_line[0] | tonumber) as $b |
($second_line[1] | tonumber) as $c |
"\($a + $b + $c) \($input[2])"

数を3つ、文字列を1つ受け取り、数の和と文字列を1行にまとめて出力する問題です。

入力を改行で区切って得られた配列を、$inputという変数に束縛しています
1行目を数値に変換して $aに束縛し、
2行目を空白で区切って数値に変換して$b, $cに束縛します。
jqでは、文字列補間"a + b = \($a + $b)"のような形をとり、\()で囲まれた範囲が式として計算されて埋めこまれます。

ABC086A - Product

split(" ") | map(tonumber) |
if (.[0] + .[1]) % 2 == 0 then "Even" else "Odd" end

2数の和の偶奇を判定する問題です。

入力を空白区切りで配列にし、それぞれの要素を文字列型から数値型に変換します。
2行目には要素が2つの配列データが1つ渡っています。
jqではifが使えるので、ifで偶奇を場合わけしています。
.[0], .[1]でその配列の最初の値、2番目の値を取り出し足し合わせて、2で割ったあまりが0かどうか評価しています。

ABC081A - Placing Marbles

split("") | map(select(. == "1")) | length

文字列中の1の数を数える問題です。

入力文字列を文字ごとに分解し、"1"と等しい要素のみを残し、最後に定義済みフィルターlengthで配列の長さを取得しています。

ABC081B - Shift only

def twos(n): if n % 2 == 1 then 0 else 1 + twos(n / 2) end;
split("\n") | .[1] | split(" ") | map(tonumber | twos(.)) | min

与えられた数列のうち、2で割り切れる回数が一番少ない数について、その割り切れる回数を答える問題です。

jqでは関数/フィルターが定義できます。
1行目は、引数nを受け取り、nが2で何回割り切れるかを返す関数twos(n)を再帰で定義しています。
2行目では、入力の数列部分のみを抜き出し、 配列の各数に対してtwosを適用して2で割り切れる回数の数列に変換し、minフィルターで最小の数を返しています。

ABC087B - Coins

split("\n") | map(select(. != "") | tonumber) as $input |
[
    range(0; $input[0] + 1) as $a |
    range(0; $input[1] + 1) as $b |
    range(0; $input[2] + 1) as $c |
    select($a * 500 + $b * 100 + $c * 50 == $input[3])
] | length

500円玉A枚、100円玉B枚,50円玉C枚を持っている中で、X円の払い方が何通りあるかを数える問題です。

select(. != "")は、split("\n")が末尾の改行の後を読んで空文字列を最後に生成するため、それを除くために必要になっています。
range(0; $input[0] + 1)により、0~Aのそれぞれのデータを生成し、それぞれを$aと名付けています。
そのそれぞれが$aに束縛された状況に対して、またさらに0~Bの$bを定義しています。$cも同様です。
全体として、(A+1)*(B+1)*(C+1)通りのデータが処理されています。
このうち、 select($a * 500 + $b * 100 + $c * 50 == $input[3] で、X円ぴったり払える($a, $b, $c)の組み合わせのみを残しています。
ここまで全体が[]に囲まれていることによって、この払える組み合わせの数列が生成され、最後にlengthでその数を数えています。

ABC083B - Some Sums

split(" ") | map(tonumber) as $input |
[
    range(1; $input[0] + 1) |
    select(
        tostring | split("") | map(tonumber) | add | $input[1] <= . and . <= $input[2]
    )
] | add

1以上N以下の整数のうち、各桁の和がA以上B以下であるものの和を求める問題です。
range(1; $input[0] + 1)で1以上N以下の整数それぞれのデータを生成しているのですが、問題は次のselectの中身です。

それぞれのデータに対し、 「文字列化して、文字ごとに区切って、それぞれを数値にして、合計にして、 A以上B以下になっている」ようなものだけを残しています。あくまでも和を取ろうとしているのは加工した後の数ではなく、加工前の数なので、ここまでの加工処理を全部selectの中身に押し込めて、外では元の数字がパイプに流れるようにしています。
あとはこれを[]で配列にまとめ上げて、addで合計するだけです。

ABC088B - Card Game for Two

split("\n") | .[1] | split(" ") | map(tonumber) |
sort | reverse | to_entries |
(map(select(.key % 2 == 0) | .value) | add) - (map(select(.key % 2 == 1) | .value) | add)

配列を降順にソートして、偶数番目の和から奇数番目の和を引いて出力する問題です。
肝は to_entriesです。これは、配列に用いると、それぞれの要素を {key: 添字, value: 配列の値}に変換して新たな配列を作ってくれます。
この新たな配列に対し(map(select(.key % 2 == 0) | .value) | add)で、それぞれの要素に対し「偶数番目の要素のみを残し、それぞれに対しvalueキーの値を取り出す」ことをして、その後配列の値を合計しています。奇数番目も同様です。

ABC085B - Kagami Mochi

split("\n") | map(select(. != "")) | .[1:] | unique | length

与えられた数列が、何種類の異なる数からなっているか数える問題です。

まさにそれをするuniqueというフィルターがあるので、これを適用して配列の長さを数えるだけです。

ABC085C - Otoshidama

split(" ") | map(tonumber) as $input | [
    range(0; $input[0] + 1) as $man_yen |
    range(0; $input[0] + 1 - $man_yen) as $gosen_yen |
    ($input[0] - $man_yen - $gosen_yen) as $sen_yen |
    [$man_yen, $gosen_yen, $sen_yen] |
    select(10000 * $man_yen + 5000 * $gosen_yen + 1000 * $sen_yen == $input[1])
] | if length > 0 then "\(.[0][0]) \(.[0][1]) \(.[0][2])" else "-1 -1 -1" end

合計N枚のお札で、合計金額がY円であることがありえるかどうか、ありえたらその組み合わせを一つ答える問題です。
1行目から7行目までの大きな[]でありえる組み合わせの配列を手に入れ、ありえる組み合わせが1個以上あるかどうかで場合分けしています。

ABC049C - 白昼夢 / Daydream

if test("^(dream(er)?|erase(r)?)*$") then "YES" else "NO" end

与えられた文字列がある正規表現に一致するか判定する問題です。

jqにはまさに正規表現を扱うtestというフィルターがあります。

ABC086C - Traveling

def abs: [., -.] | max;
def reachable:
    (.[1] | abs) + (.[2] | abs) <= .[0] and
    (.[0] - (.[1] | abs) - (.[2] | abs)) % 2 == 0;

split("\n") | map(select(.!="")) |
(.[0] | tonumber) as $n |
.[1:] | map(split(" ") | map(tonumber)) as $constraints |
[$constraints[0]] +
[
    range(0; $n - 1) |
    [
        $constraints[. + 1][0] - $constraints[.][0],
        $constraints[. + 1][1] - $constraints[.][1],
        $constraints[. + 1][2] - $constraints[.][2]
    ]
] |
all(reachable)

最初に地点(0, 0)にいます。
「t秒後に地点(x, y)にいなければならない」という形の制約が複数与えられるので、それが満たせるかどうか判定する問題です。

ある制約と次の制約の繋がりを考えるのがめんどくさいので、制約間の差分をとって、全ての制約を
「(0, 0)からt秒後に地点(x, y)に移動できるか?」という形の制約に変換しています。
これに対し、ちょうどt秒後にその地点に到達可能であるかどうかのboolを返すreachableというフィルターを作り、all関数で、全ての制約がreachableであるかどうかをチェックしています。

まとめ

jqコマンドは主にjsonの整形をするために使われるコマンドですが、そのフィルターの表現力はかなり高く、また、フィルターはかなり書きやすいし、記述量も少なくてすみます。そのおかげで、この記事に示したようにAtcoder Beginners Selectionの問題をかなり簡単に解くことができました。

jqコマンドの使いやすさ、言語としての面白さが伝わってくれたら幸いです。

Why not register and get more from Qiita?
  1. We will deliver articles that match you
    By following users and tags, you can catch up information on technical fields that you are interested in as a whole
  2. you can read useful information later efficiently
    By "stocking" the articles you like, you can search right away
Comments
No comments
Sign up for free and join this conversation.
If you already have a Qiita account
Why do not you register as a user and use Qiita more conveniently?
You need to log in to use this function. Qiita can be used more conveniently after logging in.
You seem to be reading articles frequently this month. Qiita can be used more conveniently after logging in.
  1. We will deliver articles that match you
    By following users and tags, you can catch up information on technical fields that you are interested in as a whole
  2. you can read useful information later efficiently
    By "stocking" the articles you like, you can search right away
ユーザーは見つかりませんでした