🦧

Rubyではじめる競技プログラミング入門 ~ AtCoder Beginners Selection編(後編) ~

2024/06/10に公開

Ruby

競技プログラミング

AtCoder

tech

プログラミング言語Rubyを使って競技プログラミングを始めようシリーズのうちの1つです。AtCoderを始めたいと思った人がおそらく最初に挑戦するであろう「AtCoder Beginners Selection」を題材にしてRubyの文法の説明や、問題を解くにあたっての基本的な考え方を説明します。対象者はRubyを始めたばかりの人やRubyはある程度知っているが競技プログラミングをしたことがない方向けの、いわゆる入門者向けの記事となっています。

前回は前半の問題について説明しました。

今回は後半部分の以下の5問を扱います。B問題やC問題があるので1度で理解できないことも多いかもしれません。全てを理解しようとせずできる問題から取り組んでいきましょう。

ABC088B - Card Game for Two

問題の概要

$N$ 枚のカードがあり、整数が書かれている。
プレイヤーはAliceとBobの二人。
互いにカードを1枚ずつ取っていく。
カードに書かれた数の合計が得点となる。
お互い得点が最大化されるように動く
AliceがBobより難点多くとったかを求める。

です。

考え方

「得点を最大化するように動く」ということは自分の手番になったら必ず残ったカードの中から一番大きい数のカードを取ると言い換えることができます。

カードの残りから一番大きい数を取るにはどうすれば良いでしょうか？
あらかじめ得点の配列を降順(大きい順)にソートして、先頭の要素から取ってくると良いです。そうすることで最も大きい値のカードを取得することができます。もちろん昇順にソートし、末尾から取得しても良いです。

AliceとBobの動きをシミュレーションしましょう。(下の「解答例(言われた通りシミュレーション)」を参照)

解答例

解答例(言われた通りシミュレーション)

# 入力の受け取り(整数に変換)
n = gets.to_i
a = gets.split.map(&:to_i).sort.reverse # 降順にソート

# アリスとボブの得点の初期化
alice = 0
bob = 0

while a[0] # 要素があれば処理を続ける
  # 配列の先頭を削除し、得点を加算する
  alice += a.shift

  # 配列の先頭があれば、それを削除し得点を加算する
  bob += a.shift if a[0] # 要素があるかどうかの確認
end

puts alice - bob

<主なメソッド>
sortは配列を昇順(小さい順)に並び替えます。reverseメソッドを使うことで逆順に並びを変更できます。つまり降順(大きい順)になります。

ary = [10, 4, 23, 16]
ary.sort #=> [4, 10, 16, 23]
ary.sort.reverse #=> [23, 16, 10, 4]

shiftメソッドは配列の先頭を破壊的に取り出します(削除)。

ary = [10, 4, 23, 16]
ary.shift #=> 10 戻り値は先頭の取り出した要素
p ary #=> [4, 24, 16]

<要素があるかどうかの判定>
if a[0]というコードがありますが、配列に対して添え字でアクセスした時要素がなければnilを返します。

ary = [1]
ary[100000] #=> nil

Rubyはnilとfalseの時は条件式がfalseとなります。それ以外の場合は12などの整数値でもaなどの文字列でももちろんtrueでも条件式がtrueになるのでこの性質を使って要素があるかどうかの判定をしています。

if a[0] # 要素がなければnilとなりfalse、要素があればtrueとなる
   ...
end

別解1

「解答例(言われた通りにシミュレーション)」は配列から実際に要素を削除していくという破壊的操作でシミュレーションしました。

別の考え方として、カードを降順に並べた時、0始まりで偶数番目のカードをAliceが手に入れる。逆に奇数番目のカードをBobが手に入れると考えると、非破壊的に配列の操作ができます。(下記画像参照、例は[23, 18, 15, 9, 4]のカードがあると仮定)
その方針でプログラムを書いてみると下の解答例の「別解(非破壊的な操作)」のようになります。
alt text

別解(非破壊的な操作)

# 入力の受け取り(整数に変換)
n = gets.to_i
a = gets.split.map(&:to_i).sort.reverse # 降順にソート

# アリスとボブの得点の初期化
alice = 0
bob = 0

# カードを順番に見ていき、偶数番目ならaliceに加算、奇数番目ならbobに加算
a.each_with_index { |score, i| i.even? ? alice += score : bob += score }
puts alice - bob

別解2

もう少し工夫する余地もあります。

手番の最初はAliceからなので

(Aliceのスコア) \ge (Bobのスコア)

となり、

(Aliceのスコア) - (Bobのスコア)

と計算すれば良いことから、先ほどの入力例で考えると

\begin{aligned} (23 + 15 + 4) - (18 + 9) &= 23 + 15 + 4 - 18 - 9 \\ &= 23 - 18 + 15 - 9 + 4 \\ \end{aligned}

と式変形できます。
つまり、Aliceのとるカードの点数は正の数、Bobの取るカードの点数は負の数として足し合わせれば良いことになります。この方針で書いたプログラムが「別解(数学的な工夫)」となります。

別解(数学的な工夫)

n = gets.to_i
a = gets.split.map(&:to_i).sort.reverse # 降順にソート

puts a.each_with_index.sum { |score, i| i.even? ? score : -score }

ABC085B - Kagami Mochi

問題の概要

円形の餅が $X$ 枚ある。
積み重ねていくが上にいくほど直径が小さくなっていく必要がある。同じ大きさの餅は積み重ねても段数が増えない。
最大で何段重ねの餅が作れるか？という問題。

考え方

実際に積み重ねていくときは餅の大きさでソートして大きい方から積み重ねていき段数を数えれば良いですが、この問題は言い換えると「与えられた餅の直径が何種類あるか？」となります。同じ大きさは1つとして数えましょう。

解答例

n = gets.to_i
d = Array.new(n) { gets.to_i }

puts d.uniq.size # uniq使って同じ大きさをまとめる

<uniqメソッド>
uniqメソッドは重複した値を1つにまとめてくれます。破壊的なメソッドとしてはuniq!があります。

ary = [1, 2, 3, 1, 2, 3, 2, 2]
ary.uniq #=> [1, 2, 3]

ABC085C - Otoshidama

問題の概要

10000円札、5000円札、1000円札の3種類のお札がある。
祖父からもらったお年玉袋に $N$ 枚のお札が入っていて合計で $Y$ 円だった(らしい)。
嘘の可能性もあるので、合計 $Y$ 円となる可能性があるか判定し、ありうる場合お年玉袋の中身の例を1つ挙げよ。
また、あり得ない場合は-1 -1 -1と出力する。

考え方

全探索の考え方

一番シンプルな考え方は各お札の枚数のパターンを全探索することです。ここでは入力3 7000で考えてみましょう。
お札は全部で9枚なので以下のような組み合わせがあります。

10000円札(枚)	5000円札(枚)	1000円札(枚)	合計	判定
3	0	0	30,000	NG
2	1	0	25,000	NG
2	0	1	21,000	NG
1	2	0	20,000	NG
1	0	2	12,000	NG
1	1	1	16,000	NG
0	3	0	15,000	NG
0	2	1	11,000	NG
0	1	2	7,000	OK🙆‍♂️
0	0	3	3,000	NG

この中で可能性としてあり得るのは0 1 2という組み合わせです。今回の例ではこの組み合わせしかありませんでしたが複数通りある場合もあります。その場合はどれか1通りだけ出力すれば良いです。

単純に問題を解くという場合はこの方法で解けるのですが、実はこの方法で解いた場合はTLEという実行時間制限に間に合わないという現象が起きます。これは (時間)計算量 が大きすぎることが問題となります。

計算量について

計算量についてはいろんな種類があり、また正確な定義となると小難しいのですがここでは問題を解くにあたって必要な知識の説明に絞ります。

以下は実装の概観です。お札の枚数の組み合わせを全探索するためのコードです。

# n は札束の枚数, ブロックパラメータa, b, c はそれぞれ10000円札、5000円札、1000円札の枚数を表す。

(0..n).each do |a| # (n+1)回のループ処理
  (0..n).each do |b| # (n+1)回のループ処理
    (0..n).each do |c| # (n+1)回のループ処理
      # 合計n枚出なければ処理しない
      next if a + b + c != n

      # なんらかの処理
    end
  end
end

上のコードで $0 \sim n$ の $(n+1)$ 回のループを3セット行うことになるので

(n+1) \times (n+1) \times (n+1) = (n+1)^{3}

つまり、

\Omicron(N^{3})

となります。

で今、制約をみると入力Nの範囲は $1 \le N \le 2000$ ですのでざっと $2000^3 = 8,000,000,000$ となります。
これは $8 \times 10^9$ なのですが、大きい計算量です。
言語にもよりますが、今のところRubyでは実行時間制限2secという制約のもとでは $10^6$ もしくは $10^7$ 程度がボーダーだと考えてください。ということでこのままではTLEとなります。

ループ回数を減らす

どうにか計算量を落とさないといけません。ここでボトルネックとなっている箇所は3重ループです。これを2重ループにできないか？という視点で見ていくと、札束の合計枚数、10000円札の枚数、5000円札の枚数がわかれば1000円札の枚数は計算できることに着目します。

# n は札束の枚数, a, b, c はそれぞれ10000円札、5000円札、1000円札の枚数を表す。
c = n - a - b

この考えを用いて2重ループで問題を解こうとすると計算量は $\Omicron(N^2)$ となり具体的には $4 \times 10^6$ ですので実行時間制限2secに間に合います。

解答例

# 入力の受け取り(整数に変換)
n, y = gets.split.map(&:to_i)

# 二重ループで10000円札、5000円札の組み合わせを全探索。(1000円札の枚数候補は計算で出す)
(0..n).each do |a|
  (0..n).each do |b|
    c = n - a - b　# 1000円札の枚数候補
    next if c < 0 # c が負の数になれば不適切なのでnext

    if 10000 * a + 5000 * b + 1000 * c == y
      puts [a, b, c].join(' ')
      exit # exitはプログラムの終了
    end
  end
end

puts '-1 -1 -1'

exitは枚数の組み合わせが見つかったらプログラムを終了するために使用しています。
これがないと枚数の組み合わせが複数あるときに複数個出力することになります。exitの代わりにreturnを使っても(この場合は)同じです。

ABC049C - 白昼夢

問題の概要

英小文字からなる文字列 $S$ がある。
Tの末尾に以下の文字列のいずれかを追加する操作を好きなだけ繰り返し、SとTを一致させることができるかどうか判定する問題。

<末尾に追加できる文字列>

dream
dreamer
erase
eraser

考え方

4つの単語に一致する文字をどんどん削除していけば良いです。
問題文ではTの末尾に加えるとありますが、Sの末尾を消していき全て消せたら(空文字列になったら)同じと考えます。

つまり、末尾から4つの単語に一致するか調べて削除していく方針で解きましょう。

解答例

# 入力の受け取り(文字列)
s = gets.chomp

# 4つの単語の配列（順番に調べていく)
words = ['dream', 'dreamer', 'erase', 'eraser']

loop do
  # 削除したかどうか(4つの単語のどれかに一致したかどうか)。
  deleted = false

  words.each do |word|
    if s.end_with?(word)
      s.delete_suffix!(word)
      deleted = true
      break
    end
  end

  break unless deleted
end

puts s.empty? ? 'YES' : "NO"

ead_with?は文字列に対して引数で指定した文字列と末尾が一致するかどうか判定するメソッドです。一致すればtrue、一致しなければfalseを返します。

'abcedf'.end_with?('edf') #=> true
'abcedf'.end_with?('abc') #=> false

別解

その他に単語に一致する文字列の部分を順番に空文字列で置換していく方法でも解けますが、この場合は置換する単語の優先順位を気にしなければなりません。

例えば入力がdreameraseでdreamよりもdreamerの優先度を上げて置換していくとaseが残ってしまいます。

dreamerase
    ↓
[dreamer]ase
    ↓
   ase # 残る

逆にdreamerよりもdreamの優先度を上げると

dreamerase
    ↓
[dream]erase
    ↓
 [erase]
    ↓
  　　　　　　　　　# 空文字列となる

[dream][erase]となり全て置換することができます。

よって、dreamerとdreamの優先度を考慮する必要があります。
その方針で解いたのが下の「別解(置換)」です。

別解(置換)

s = gets.chomp

# 単語にマッチする部分を空文字列で置換
remain = s.gsub('eraser', '')
      .gsub('erase', '')
      .gsub('dreamer', '')
      .gsub('dream', '')

puts remain.empty? ? 'YES' : "NO"

ABC086C - Traveling

問題の概要

旅行プランを立てたい。

二次元平面がある
時刻 $0$ に点 $(0, 0)$ を出発
N箇所訪れる予定
時刻 $t_{i}$ に点 $(x_{i}, y_{i})$ を訪れる。
時刻1進むと上下左右のいずれかに 1 だけ移動できる(問題文にはもっと厳密に書いてあります)
その場にとどまることもできない。

以上の条件から旅行プランが実行可能かどうかを判定する問題。

考え方

この問題は縦方向と横方向の全体の移動量に着目するのと偶奇(パリティ)に着目します。

入力例1を参考に考えてみましょう。

2
3 1 2
6 1 1

まず時刻 $3$ の時に点 $(1, 2)$ の地点へと向かいたいです。
時刻 $0$ から時刻 $3$ の間に移動できる距離は上下左右合わせて3移動できます。また、点 $(0, 0)$ から点 $(1, 2)$ まではx軸方向に1, y軸方向に2の合計3移動する必要があります。

移動できる距離が3に対して移動したい距離が3なのでこれは適切に上下左右を選べば移動することができます。(右、上、上の組み合わせ)

alt text

次に時刻 $6$ の場合を考えます。
時刻 $3$ から時刻 $6$ の間に移動できる距離は上下左右合わせて $3$ です。また点 $(1, 2)$ から点 $(1,1)$ まではx軸方向0、y軸方向に1の合計1移動する必要があります。

移動できる距離が3で移動したい距離が1となります。この場合目的地へ移動することはできるでしょうか？その場にとどまることはできないという問題文の制約もありますので必ずどこかの方向へは移動する必要があります。

2ターン(時刻の量が2)使えば元いた場所へと戻ってくることができます(下の画像水色の部分)。「→、←」や「↑、↓」のような移動ですね。また、この移動を連続回行うと、偶数ターン使うことで元の位置に戻ることができます。

alt text

なので最短で目的地に行き、残り偶数ターン残っていればその場にとどまり、目的地へ移動できると判定して良さそうです。

<パリティの別の考え方>
先ほど(移動したい距離) - (移動できる距離)が偶数かどうかを判定すると言いましたが、移動できる距離と移動したい距離の偶奇が一致するかどうか？という判定も同じ意味です。

これは

$(偶数) - (偶数) = (偶数)$
$(奇数) - (奇数) = (偶数)$

という性質から明らかです。このパターン以外で差が奇数になる偶奇の組み合わせはありません。

解答例

n = gets.to_i

# 現在時刻と現在の位置の合計
now = 0
point = 0

n.times do
  t, x, y = gets.split.map(&:to_i)

  time = t - now # 移動に使う時刻量(移動できる距離)
  dist = ((x + y) - point).abs # 移動したい距離

  # 1つ目の条件がfalseだったら移動できる距離が足りないということ
  # 2つ目の条件は最短で目的地に行ってから、残りの移動できる距離が偶数かどうか
  can = (time - dist) >= 0 && (time - dist).even?
  unless can
    puts 'No'
    exit
  end

  # 現在時刻と位置の合計の更新
  now = t
  point = x + y
end

puts 'Yes'

距離の計算でabsというメソッドを使ってますがこれは絶対値を取るメソッドです。距離の差分は負の数になることがあるため使っています。

最後に

2回にわたってAtCoder Beginners Selectionの問題を解いていきました。中には難しい問題もあったと思います。最初の頃はA問題やB問題から練習していくのがおすすめです。(計算量を考慮しなくて良いことが多いので)

また、AtCoder Problemsといって過去のコンテストの問題をコンテスト別に紹介してくれているサイトもあるのでこちらで難易度を確認しながら解いていくとよいでしょう。

https://kenkoooo.com/atcoder/#/table/

GitHubで編集を提案

ABC088B - Card Game for Two

問題の概要

考え方

解答例

別解1

別解2

ABC085B - Kagami Mochi

問題の概要

考え方

解答例

ABC085C - Otoshidama

問題の概要

考え方

全探索の考え方

計算量について

ループ回数を減らす

解答例

ABC049C - 白昼夢

問題の概要

考え方

解答例

別解

ABC086C - Traveling

問題の概要

考え方

解答例

最後に

Discussion