AtCoder に登録したら解くべき精選過去問 10 問を PostgreSQL で解いてみた

はじめに

この記事は，次のQiita記事に「過去問精選 10 問！」として示されている10問の問題をPostgreSQLを用いて解いたものである．
qiita.com

また，AtCoderではこれらの問題をまとめた初心者向け問題集として「AtCoder Beginners Selection」を用意している．

問題

これらの問題では，PostgreSQLで標準入出力を取り扱うことが困難であるため，入力は共通表式(WITH句)を用いていくつかのテーブルとして与え，出力もまたテーブルとするよう，問題を変形している．

また，各問題の解答方針についての解説はすでに公式に公開されているため，本記事では解答方針についての解説を詳しく行うことはせず，主にSQL特有の事情についての解説を中心とする．

0. PracticeA - はじめてのあっとこーだー（Welcome to AtCoder）

問題文の冒頭に「高橋君はデータの加工が行いたいです。」とあるが，SQL(DML)はすでに構造化されたテーブルデータの操作を行うために作られた言語であり，未だ構造化されていない段階のデータを取り扱うのは容易ではないため，この冒頭のみで「はじめてのあっとこーだー」というには難易度の高い問題であることが予感される．果たしてその予感は的中するのだ．

テーブルtblに，標準入力の文字列と「何行目に入力された文字列か」という情報を与える．テーブルは順序を保持しないため何行目であるかの情報が必要である．解答には，テーブルtbl内の情報から必要な部分の文字列を正規表現を用いて切り出し，数値に変換する操作と，文字列の結合操作が必要である．

WITH tbl(num, str) AS
(
  VALUES
  (1, '72'),
  (2, '128 256'),
  (3, 'myonmyon')
)
SELECT
  (
    TO_NUMBER((SELECT str FROM tbl WHERE num = 1), '9999') +
    TO_NUMBER(SUBSTRING((SELECT str FROM tbl WHERE num = 2) FROM '^.*\ '), '9999') +
    TO_NUMBER(SUBSTRING((SELECT str FROM tbl WHERE num = 2) FROM '\ .*$'), '9999')
  )::TEXT ||
  ' ' ||
  (SELECT str FROM tbl WHERE num = 3) AS result

次の問題以降は，テキストの構造化は問題の解法には大きく関わらないので，問題ごとに与えられる数値などの値はテーブルを経由し，SQLで操作しやすい形式で与える．

1. ABC086A - Product

2つの数の積を計算し，その偶奇を判定する問題である．CASE句の入門的問題であると考えられる．

余談であるが，この問題は制約と解法次第でオーバフローを起こすことが考えられる．PostgreSQLでは数値型の演算でオーバフロー，アンダフローを起こした場合は即座に演算エラーとなる．もしAtCoderで提出言語としてPostgreSQLが採用されたら，オーバフローを起こした場合は「WA」ではなくゼロ除算と同じ「RE」となるだろう．

WITH a(num) AS
(
  VALUES(3)
),
b(num) AS
(
  VALUES(4)
)
SELECT
  CASE WHEN (SELECT num FROM a) * (SELECT num FROM b) % 2 = 0 THEN 'Even'
  ELSE 'Odd'
  END AS result

2. ABC081A - Placing Marbles

入力を数値として受け取り，各桁の和を計算することで答えを得る．

PostgreSQLの数値リテラルはC言語などと異なり，最上位桁に0が置かれても基数は変わらない(C言語では8進数になる)．

WITH tbl(num) AS
(
  VALUES(011)
)
SELECT
  (num / 100 + num / 10 % 10 + num % 10) AS result FROM tbl

3. ABC081B - Shift only

与えられる $N$ 個の整数全てが $2^k$ で割り切れるような最大の $k$ を求める問題．与えられたそれぞれの整数を2進数で表記した文字列を作成し，末尾に連続している「0」を削除したときの文字列の長さの変化を見ることで答えを得る．

WITH n(num) AS
(
  VALUES(6)
),
a(num) AS
(
  VALUES
  (382253568),
  (723152896),
  (37802240),
  (379425024),
  (404894720),
  (471526144)
),
t(num) AS
(
  SELECT 32 - CHAR_LENGTH(TRIM(TRAILING '0' FROM num::BIT(32)::TEXT)) FROM a
)
SELECT MIN(num) AS result FROM t

4. ABC087B - Coins

全探索を行う問題．PostgreSQLのGENERATE_SERIES関数を使うと大変便利．

WITH a(num) AS
(
  VALUES(30)
),
b(num) AS
(
  VALUES(40)
),
c(num) AS
(
  VALUES(50)
),
x(num) AS
(
  VALUES(6000)
)
SELECT COUNT(*) AS result
  FROM
    GENERATE_SERIES(0, (SELECT num FROM a)) AS sa,
    GENERATE_SERIES(0, (SELECT num FROM b)) AS sb,
    GENERATE_SERIES(0, (SELECT num FROM c)) AS sc
  WHERE 500 * sa + 100 * sb + 50 * sc = (SELECT num FROM x)

5. ABC083B - Some Sums

各桁の和による検索を行い，その結果の総和を取ることで答えを得る．

WITH n(nnum) AS
(
  VALUES(100)
),
a(anum) AS
(
  VALUES(4)
),
b(bnum) AS
(
  VALUES(16)
),
t(tnum) AS
(
  SELECT GENERATE_SERIES(1, (SELECT nnum FROM n))
)
SELECT SUM(tnum) AS result
  FROM t, a, b
  WHERE (tnum / 1000 + tnum / 100 % 10 + tnum / 10 % 10 + tnum % 10) BETWEEN anum AND bnum

6. ABC088B - Card Game for Two

入力された $a_i$ を降順に並べ替えて番号を付け，その番号の偶奇ごとに総和をとると，各プレイヤの得点がわかる．

WITH n(num) AS
(
  VALUES(4)
),
a(num) AS
(
  VALUES
  (20),
  (18),
  (2),
  (18)
),
t(ord, num) AS
(
  SELECT ROW_NUMBER() OVER(ORDER BY num DESC), num FROM a
)
SELECT
  (SELECT SUM(num) FROM t WHERE ord % 2 = 1) -
  (SELECT SUM(num) FROM t WHERE ord % 2 = 0) AS result

7. ABC085B - Kagami Mochi

入力された値に互いに相異なる値が何種類あるかを考える．SQLではDISTINCTオプションで行の重複を排除できるので，本記事で取り扱う問題のなかではこの問題が最も実装が容易．

WITH n(num) AS
(
  VALUES(7)
),
d(num) AS
(
  VALUES
  (50),
  (30),
  (50),
  (100),
  (50),
  (80),
  (30)
)
SELECT COUNT(DISTINCT num) AS result FROM d

8. ABC085C - Otoshidama

3種類のお札のうち1種類の枚数を固定すると，お札の枚数と合計金額の条件とあわせて，ほかの2種類のお札の枚数も定まる．ただし，求まったお札の枚数が整数でない場合や負の値の場合は実行できないので注意が必要である．次のSQL文では，合計金額についての制約から考えられる10000円札の枚数のそれぞれについて，ほかの2種類のお札の枚数を求める方法をとっている．与えられた $N, Y$ を実現する3種類のお札の枚数の組み合わせが存在しない場合の処理は， $\texttt{-1 -1 -1}$ を番兵として用いることで実現している．

WITH n(num) AS
(
  VALUES(1000)
),
y(num) AS
(
  VALUES(1234000)
),
a(num) AS
(
  SELECT GENERATE_SERIES(0, (SELECT num FROM y) / 10000)
),
t(a, b, c) AS
(
  SELECT
    a.num,
    (- n.num + y.num / 1000 - 9 * a.num) / 4,
    (5 * n.num - y.num / 1000 + 5 * a.num) / 4
  FROM n, y, a
),
s(a, b, c) AS
(
  SELECT a, b, c
  FROM t, y
  WHERE
    a >= 0 AND
    b >= 0 AND
    c >= 0 AND
    10000 * a + 5000 * b + 1000 * c = num
  UNION
    VALUES(-1, -1, -1)
)
SELECT a::TEXT || ' ' || b::TEXT || ' ' || c::TEXT AS result
  FROM s 
  ORDER BY a DESC
  LIMIT 1;

9. ABC049C - 白昼夢 / Daydream

与えられた文字列の末尾に「dream」「dreamer」「erase」「eraser」がある場合にマッチングする正規表現を作成し，これらの文字列を空文字列に置き換えることを繰り返す．マッチしなくなった時の文字列全体が空文字列であるとき，かつそのときに限り， $\texttt{YES}$ を表示する．WITH RECURSIVE句のUNIONが重複を排除することに注意．

WITH s(str) AS
(
  VALUES('dreameraser')
)
SELECT * FROM
(
  WITH RECURSIVE t(str) AS
  (
    SELECT str FROM s
    UNION
    SELECT REGEXP_REPLACE(str, '(dream|dreamer|erase|eraser)$', '') FROM t
  )
  SELECT
    CASE
      WHEN EXISTS(SELECT str FROM t WHERE str = '') THEN 'YES'
      ELSE 'NO'
    END AS result
) AS r

10. ABC086C - Traveling

点 $P_i = (x_i, y_i)$ から点 $P_{i+1} = (x_{i + 1}, y_{i + 1})$ に移動するときにかかる最小の時間は， $c(P_i, P_{i + 1}) = |x_{i+1} - x_i| + |y_{i+1} - y_i|.$ また， $t_{i + 1} - t_i - c(P_i, P_{i + 1})$ が非負の偶数のとき，かつそのときに限り，時刻 $t_i$ に点 $P_i$ を出発し，時刻 $t_{i+1}$ に点 $P_{i+1}$ を訪れることが可能である．これが $0 \leq i < N - 1$ で成り立つとき，かつそのときに限り，旅行プランは実行可能である．ただし， $P_0 = (0, 0).$

この問題は実行時間に特に注意して解く必要がある．制約内で $N$ が最大のケースでは旅行プランの行数(すなわち次のSQL文のテーブルpの行数)が $N=10^5$ 行にもなる． $c(P_i, P_{i + 1})$ や $t_{i + 1} - t_i$ の計算でつい自己相関クエリを書きたくなってしまうかもしれないが，入れ子ループ法における自己相関クエリの実行時間は $O(N^2)$ だから，この方法では時間がかかりすぎる．入力に共通表式を用いているので，索引を張ることもかなわない．このような場合はPostgreSQL 8.4から導入されている窓関数LAGを利用するのがよい．窓関数を利用した場合は差分の計算を $O(N)$ 時間で行うことができる．

ただし，テーブルは順序を保持しないためテーブルをソートする必要があり，テーブルのソートに $O(N \log N)$ 時間かかるので，プログラム全体の実行時間は $O(N \log N)$ 時間となる．

WITH n(num) AS
(
  VALUES(2)
),
p(t, x, y) AS
(
  VALUES
  (3, 1, 2),
  (6, 1, 1)
),
plan(t, x, y) AS
(
  SELECT * FROM
  (
    SELECT t, x, y FROM p
    UNION
    VALUES(0, 0, 0)
  ) AS a
  ORDER BY t
),
delta(t, c) AS
(
  SELECT
    t - LAG(t, 1, 0) OVER (), 
    ABS(x - LAG(x, 1, 0) OVER ()) + ABS(y - LAG(y, 1, 0) OVER ())
  FROM plan
)
SELECT
  CASE
    WHEN EXISTS(SELECT * FROM delta WHERE t - c < 0 OR (t - c) % 2 = 1) THEN 'No'
    ELSE 'Yes'
  END AS result

まとめ

SQLはプログラミング言語である．

nkhrlab~

140字超の記事