okuzawatsの日記

Android / Kotlin / GitHub Actions Enthusiast 🤖

LuaでAtCoderの過去問精選10問を味わう

profile

書いている人 モバイルアプリケーションアーキテクト(Android)として働いています。モバイルアプリケーションのアーキテクチャ、自動テスト、CI/CDに興味があります。もっと詳しく

プログラミング言語Luaを使って、AtCoderの過去問精選10問を味わってみました。こういった問題を解く時、Luaは美しく書けるな〜という感想です。

AtCoder に登録したら次にやること ~ これだけ解けば十分闘える!過去問精選 10 問 ~ #AtCoder - Qiita

第1問 ABC 086 A - Product

問題の内容は、AtCoderの出題ページ(A - Product)を参照してください。以下9問についても同様に出題ページへのリンクのみ提示します。

ABCのA問題という感じの難易度の問題ですが、Luaの文法を学ぶには丁度良いです。最終的な自分の回答は以下のコードです。

a, b = io.read("n", "n")
print(a * b % 2 < 1 and "Even" or "Odd")

まず、1行目のコードでは、標準入力から数値型の値を2個読み取り、変数 ab に分割代入しています。io.read に文字列 n を渡すわけですが、可変長の引数を取ることが可能で、標準入力から複数の値を読み取る時に重宝します。自分の場合、プロダクト開発では分割代入を使うことはあまりありませんが、こういった問題を解く時は簡潔に記述することができて嬉しいです。

a, b = io.read("n", "n")

2行目のコードでは、andor を用いた、Luaでの頻出イディオムを使っています。and の左辺値に真偽値を取り、真偽値が真である場合は and の右辺値が評価されます。真偽値が偽である場合は and の右辺値は評価されず、or の右辺値が評価されます。一部の言語における三項演算子のような使い方をするイディオムとなっています。

print(a * b % 2 < 1 and "Even" or "Odd")

第2問 ABC 081 A - Placing Marbles

A - Placing Marbles

こちらも難易度は低いですが、Luaのコードとしてはなかなか味わい深いです。

io.read を用いて、今度は1文字ずつ標準入力から読み取り、分割代入しています。驚くべきことに、読み込んだ文字をそのまま加算することで数値型の加算として計算が実行されます。

a, b, c = io.read(1, 1, 1)
print(a + b + c)

自分にとっては驚くべきコードでしたが、結果として非常に簡潔にコードを書くことができ、美しいです。

第3問 ABC 081 B - Shift only

B - Shift only

精選問題も3問目に入り、ABC B問題の難易度になります。1問目、2問目と比較すると本格的な感じになってきます。本文では、配列やループの処理が必要になります。最終的な自分の回答は以下のコードです。

a, n = {}, io.read("n")
for i = 1, n do
  a[i] = io.read("n")
end

c = 0
while true do
  f = false
  for i = 1, n do
    if a[i] % 2 > 0 then
      f = true
      break
    end
  end
  if f then
    break
  end
  for j = 1, n do
    a[j] = a[j] // 2
  end
  c = c + 1
end
print(c)

Luaでは、配列のインデックスは1からです。これは便利なことが多いですが、慣れないと戸惑うかもしれません。配列の初期化は以下のように行なっています。

for i = 1, n do
  a[i] = io.read("n")
end

配列の更新処理も同様です。

for j = 1, n do
  a[j] = a[j] // 2
end

第4問 ABC 087 B - Coins

B - Coins

3重ループです。1問目から3問目までの知識で解けます。

a, b, c, x = io.read("n", "n", "n", "n")

count = 0
for i = 0, a do
  for j = 0, b do
    for k = 0, c do
      sum = 500 * i + 100 * j + 50 * k
      if sum == x then
        count = count + 1
      end
    end
  end
end
print(count)

第5問 ABC 083 B - Some Sums

B - Some Sums

こちらの問題も基本的にはここまでの知識で解けます。整数の各位の和を求める処理は算術的に求める方が美しいと感じますが…楽をして文字列として処理しています。前述のように、Luaでは文字列が整数であれば算術演算を適用できます。

n, a, b = io.read("n", "n", "n")

count = 0
for i = 1, n do
  s, sum = tostring(i), 0
  for j = 1, #s do
    sum = sum + s:sub(j, j)
  end
  if b >= sum and sum >= a then
    count = count + i
  end
end
print(count)

文字列への変換は tostring です。

s, sum = tostring(i), 0

文字列から部分文字列を抽出するには、string:sub を使います。以下のコードは string.sub(s, j, j) と同じです。

s:sub(j, j)

第6問 ABC 088 B - Card Game for Two

B - Card Game for Two

ソートです。Luaでは table.insert を用いたソートができます。デフォルトでは昇順でソートされるので、今回のように降順でソートしたいような場合は、第2引数にラムダを渡します。

a, n = {}, io.read("n")
for i = 1, n do
  table.insert(a, io.read("n"))
end

table.sort(a, function(a, b) return a > b end)

count = 0
for i = 1, #a do
  if i % 2 > 0 then
    count = count + a[i]
  else
    count = count - a[i]
  end
end
print(count)

第7問 ABC 085 B - Kagami Mochi

B - Kagami Mochi

参考文献1においてバケット法として紹介されている手法を使います。本文では、配列の添え字として直径の整数値を用いて、その値が真か偽かを判定することにより問題を解きます。Luaの配列(というかテーブル)はこのような用途を扱う場合にとても便利で、スマートに解くことができました。

k, c, n = {}, 0, io.read("n")
for i = 1, n do
  d = io.read("n")
  if not k[d] then
    k[d], c = 0, c + 1
  end
end
print(c)

配列 k に対して直径 d を添え字にしてアクセスした場合、値が格納されていなければ nil が返ります。これを利用して、k[d] に対する真偽を判定します。構文としては、k[d] == nil または not k[d] となります。

if not k[d] then

k[d] の真偽を判定するためにLuaで用意されている真偽値(true/false)を使うこともできますが、本文ではnil/0で判定すれば十分であることに気付きました。そのため、配列にtrueを入れる代わりに0を入れて文字数の節約を試みています。こういった、ちょっとした気付きが得られた時は嬉しくなります。

k[d], c = 0, c + 1

第8問 ABC 085 C - Otoshidama

C - Otoshidama

ついにABCにおけるC問題です。が、本文については左程難しくはありません。3重のループを2重のループに書き直すことができることに気付けば解くことができます。

n, y = io.read("n", "n")
for i = 0, n do
  for j = 0, n - i do
    k = n - i - j
    if 10000 * i + 5000 * j + 1000 * k == y then
      print(i.." "..j.." "..k)
      os.exit()
    end
  end
end
print("-1 -1 -1")

Luaにおける文字列の連結には、.. という演算子を使うことができます。"abc".."def""abcdef" と評価されます。面白いですね。

print(i.." "..j.." "..k)

条件を満たす整数の組が見つかった時に、以下のコードでプログラムを強制終了しています。個人的にはあまり美しくないな〜とは思いますが、今回のような問題を解くためには os.exit() を使うのがスマートだと思います。

os.exit()

第9問 ABC 049 C - Daydream

C - 白昼夢

貪欲法です。文字列を逆順にする、という解説を読むまではうまく解けませんでした。正規表現を用いて文字列を置き換えていく、という解答例もありました。自分としては、Luaを味わう、というような解答はまだできておりません…。

s = io.read()
s = s:reverse()

w = { "dream", "dreamer", "erase", "eraser" }
for i = 1, #w do w[i] = w[i]:reverse() end

f = true
while true do
  f2 = false
  for j = 1, #w do
    w2 = w[j]
    if s:sub(1, #w2) == w2 then
      f2 = true
      s = s:sub(#w2 + 1, #s)
      break
    end
  end
  if s == "" then
    break
  end
  if not f2 then
    f = false
    break
  end
end

print(f and "YES" or "NO")

第10問 ABC 086 C - Traveling

C - Traveling

ここまでの知識を総動員してバリバリ書く感じで解答しました。

x, y, z, f, n = 0, 0, 0, true, io.read("n")
for i = 1, n do
  t, a, b = io.read("n", "n", "n")
  d = math.abs(a - x) + math.abs(b - y)
  if t - z < d or (z - t - d) % 2 > 0 then
    f = false
    break
  end
  x, y, z = a, b, t
end
print(f and "Yes" or "No")

まとめ

楽しかったです。

Reference

  1. AtCoder に登録したら次にやること ~ これだけ解けば十分闘える!過去問精選 10 問 ~ #AtCoder - Qiita(最終アクセス日:2024年2月17日)
  2. A - Product(最終アクセス日:2024年2月17日)
  3. A - Placing Marbles(最終アクセス日:2024年2月17日)
  4. B - Shift only(最終アクセス日:2024年2月17日)
  5. B - Coins(最終アクセス日:2024年2月17日)
  6. B - Some Sums(最終アクセス日:2024年2月17日)
  7. B - Card Game for Two(最終アクセス日:2024年2月17日)
  8. B - Kagami Mochi(最終アクセス日:2024年2月17日)
  9. C - Otoshidama(最終アクセス日:2024年2月17日)
  10. C - 白昼夢(最終アクセス日:2024年2月17日)
  11. C - Traveling(最終アクセス日:2024年2月17日)

Related