LoginSignup
60
26

More than 3 years have passed since last update.

@yuchiki1000yen(ゆーちき)

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

Last updated at Posted at 2019-11-27

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は . + 10というフィルターの入力となり、12が出力されます。
  • 12はtostringというフィルターの入力となり、 "12"が出力されます。
  • "12"は"数字は" + .というフィルターの入力となり、 最終的に"数字は12"が出力されます。

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

フィルターには複数のデータが入力として渡され得ます。複数のデータと１つの配列を渡すのは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])"

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

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

ABC086A - Product 

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

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

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

ABC081A - Placing Marbles 

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

文字列中の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が２で何回割り切れるかを返す関数twos(n)を再帰で定義しています。
２行目では、入力の数列部分のみを抜き出し、 配列の各数に対してtwosを適用して２で割り切れる回数の数列に変換し、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

５００円玉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)で１以上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円であることがありえるかどうか、ありえたらその組み合わせを一つ答える問題です。
１行目から７行目までの大きな[]でありえる組み合わせの配列を手に入れ、ありえる組み合わせが１個以上あるかどうかで場合分けしています。

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コマンドの使いやすさ、言語としての面白さが伝わってくれたら幸いです。

60
26
0

Register as a new user and use Qiita more conveniently

  1. You get articles that match your needs
  2. You can efficiently read back useful information
  3. You can use dark theme
What you can do with signing up
Sign upLogin
60
26