Ruby 問題集

Updated:

過去「計算数学実習資料集」に私が書いたものを体裁を整えて転載します。

この記事は?

2016 年度 計算数学 II の 4 班は Ruby 入門というテーマで学習をしている。『たのしい Ruby』第 5 版を読んでいる。これは優れた書物である。一方で、書物のプログラムを写して学習していると、自力でコードを書く機会がほしくなるかと思う。この問題集は、その機会を受講生に提供するものである。前回までの受講生の進度に準拠して AtCoder の問題を選び、まだ学習が進んでいない部分のメソッドを補足する。こうすることで、先週まで学んだことの定着を図る。

10 月 27 日の問題

整数の加減乗除や if 文を勉強したので、 ABC031 A - ゲームを解く。

a, d = gets.chomp.split(" ").map{|i| i.to_i}

とすると、 ad に問題文の $A$ と $D$ が入る。

Ruby では大文字から始まる変数は定数であるので、普通の変数がほしいときは、小文字からはじめる。

11 月 8 日の問題

文字列の比較や for 文や while 文を勉強したので、 ABC041 B - 文字列大好きいろはちゃんイージー を解く。

入力については、

n, l = gets.chomp.split(" ").map{|i| i.to_i}

s = Array.new(n)

for i in 0...n
  s[i] = gets.chomp
end

とするとよい。

s は配列である。配列がないと for 文で入力を受け取るのが著しく困難になる。先取りになるが、『たのしい Ruby』の第 13 章の最初の方を読んで理解してほしい。

問題の解き方はいくつかある。

  • for 分を使う配列の中から辞書順最小の文字列をその都度選んでくる。選んだら消す。while 文で s が空欄になるまで繰り返す。
    • s.delete_at(i) をつかうと s の $i$ 番目の要素を削除できる。
    • s が何も入っていない配列かどうかを判定するには s.empty? と書く。
  • s の要素を並べ替える。
    • 第 13 章からやり方を探す。

後者のほうが計算量が少ないが、この問題ではどちらでも間に合う。文字列の結合は + を使う。詳しくは第 14 章。

11 月 10 日の問題

関数の定義が今日できっと終わるので、 ABC047 B - すぬけ君の塗り絵 2 イージー を解く。入力については、以下のようにする。

w, h, n = gets.chomp.split(" ").map{|i| i.to_i}
x, y, a = Array.new(3){Array.new(n)}
for i in 0...n
  x[i], y[i], a[i] = gets.chomp.split(" ").map{|h| h.to_i}
end

まず 2 次元配列の説明をする。2 次元配列 field を用意する。2 次元配列は、配列の配列である。だから field[i] のようにすると、これが 1 次元配列(普通の配列)になっている。ゆえに、 field[i][j] のようにすると、要素にアクセスできる。2 次元配列は以下のようにすると作成できる。

field = Array.new(w){Array.new(h){false}}

さて、問題の制約の塗り方では、必ず 1 辺 1 の正方形を単位として塗られる。そこで field の各要素は truefalse をとるものとして、

$field[i][j] = (i, j), (i+1, j), (i, j+1), (i+1, j+1)$ の 4 点を頂点とする正方形が黒く塗られいるときに true 、白いときに false

を意味することにしよう。上のコードで、全ての要素が false である 2 次元配列ができている。あとは制約に添って順番に、黒く塗るべきマス目に true を代入していけばよい。最後まで動作を続けると、一度黒く塗られたマスはずっと黒いままだし、一度も黒く塗られなかったマスは白い。

入力の指示通りに順番に field のマス目を塗っていく。ここで問題となるのが、 $a[k]$ の値による場合分けである。この部分をコードの直接書くと、可読性が失われる可能性が高い。そこで次のような関数を定義する。

def ok(i, j, _x, _y, _a)
  # _x, _y, _a の条件のもとで、field[i][j] を黒く塗るなら true、そうでないなら false を返すコードをここに書く。
end

_x のようにアンダーバーが付いているものは、普通のローカル変数である。普通の変数と何ら変わりないが、「あとでここに $x[k]$ を代入する」ような目印になるのでわかりやすい。

さて、上の ok という関数をソースコードの冒頭に定義しておけば、黒く塗る処理は、$k, i, j$ についての 3 重ループで、以下のように簡潔に記述される。

for k in 0...n
  for i in 0...w
    for j in 0...h
      if ok(i, j, x[k], y[k], a[k])
        field[i][j] = true
      end
    end
  end
end

黒く塗り終わったら、 field のうち白いマスを数えれば、それが答えとなる。

参考:関数について

Ruby では関数のことをメソッドという(とひとまず理解して良い)。プログラミング言語でいうところの「関数」は、手続きの集まりのようなものである(第 2 章参照)。

その一方で、数学の関数のような性質も備えている。

  • 引数を取ることができる。例えば上で定義した ok(i, j, _x, _y, _a) は、 i , j , _x , _y , _a の 5 つの変数を引数として取っている。
  • 返り値を返すことができる。明示的に返り値を返すならば、return を使う。例えば return true と書けば、true を返すことができる。
  • 原則として、関数の外の変数を参照できない。参照できる変数は、引数で引いた変数のみである。したがって、上で定義した ok という関数の中で使えるのは、 i, j, _x, _y, _a のみである。 fieldk は使ってはならない。というより、使おうとしている時点で正しく理解していない。この場合、本をよく読むか TA に聞いて納得する。
    • 補足:関数の中から外の変数を参照するには、例えば、グローバル変数、インスタンス変数、クラス変数などを使う。

発展的補足

Ruby の場合、引数は次のように処理される。

引数の変数を使って関数の内部で計算しても、引かれた外の変数には影響を与えない。 ところが、ポインタを渡すと、引かれた外の変数に影響を与える。例えば以下のコードを実行するとわかる。

class Artist
  attr_accessor :hp, :mp

  def initialize(_hp, _mp)
    @hp = _hp
    @mp = _mp
  end

  def media(ch) # 回復魔法
    if @mp >= 10
      @mp -= 10
      ch.hp += 100
    end
  end

end

tsubasa = Artist.new(100, 30)
itsuki = Artist.new(10, 50)

puts "tsubasa.mp = #{tsubasa.mp}"
puts "itsuki.hp = #{itsuki.hp}"

tsubasa.media(itsuki)

puts "tsubasa.mp = #{tsubasa.mp}"
puts "itsuki.hp = #{itsuki.hp}"

tsubasa.media(itsuki)tsubasamp に影響が出るのは、納得されよう。しかし itsukihp に影響があるのは納得しにくいかもしれない。しかし itsuki で渡されるのは Charator クラスのインスタンス itsuki のアドレス(ポインタ)であるので、 heal の中の ch.hp += 100 では itsukihp そのものが参照され、変更がなされる。

11 月 17 日の問題

文字列の取扱については慣れておいたほうがよいので、やや易しいが AGC006 A - Prefix and Suffix を解く。

今日は入力も易しいので、入力についても説明してみたいと思う。Ruby の場合、 gets と書くと、標準入力から「 1 行」を受け取ることができる。だから今回の場合、おおよそ、 (変数) = gets と 3 行書けばよいことになる。

しかし、型を変換するのが大事である。 gets の返り値は、 末尾に改行コードが入った文字列 (String クラスのインスタンス) である。これは整数 (Integer クラスのインスタンス) とは違うし、改行コードが入っていない文字列とも違う。 gets で受け取った型を変換するには、 gets の後に String クラスのメソッドを書く。

  • gets.to_i とすると、gets の返り値を整数に加工することができる。
  • gets.chomp とすると、gets の返り値の末尾の改行コードを削除することができる。「削除することができる」と書いてあるが、このへんはもう少し正確に理解するべきなので、後の補足も読むことをおすすめする。

詳しくは、あとでメソッドを勉強してほしい(『たのしい Ruby』第 7 章)。ローカル変数は小文字から始まることに注意。

さて、問題の解法だが、今回の場合、$s$ と $t$ を単純に繋げた $s + t$ が条件(始めの $N$ 文字が $s$ 、末尾の $N$ 文字が $t$ )をみたすことは明らか。よって条件をみたす最小の文字列は、これよりも短い文字列に限られる。考えうる最も短いパターンは $s$ そのもので、 $s$ と $t$ が一致している場合である。

ここでは、 $N \leq 100$ しかない。だから、可能性のある文字列を全部列挙し、短い文字列から条件をみたしているかをチェックすれば十分である。具体的には以下の手順を踏めばよいだろう。(以下、$N$ は $n$ と記載する)

  • 可能性のある文字列 str の配列をつくる。 str は、長さ $n + 1$ の配列として宣言する。
  • str[i] は $s$ に、 $t$ の末尾 $i$ 文字を結合したものとする。
  • 一般に文字列 $t$ の 末尾から数えて $x$ 番目の文字から $y$ 文字を切り出したいときは、 t.slice(-x, y) とすればよい。配列の宣言や文字列の結合の方法は以前のサンプルコードにかかれている。
  • あとは順番に str[i] が条件をみたしていることを確認すれば良い。作り方から、始めの $n$ 文字が $s$ に一致するのは自動的にみたされている。だから $str[i]$ の末尾 $n$ 文字が $t$ に一致していかどうかを確かめれば良い。この処理も slice で実装できる。文字列 $x$ の文字数は x.size() で得られる。
  • プログラムを途中で終了したいときは exit とする。その行の到達した瞬間に終了する。参考:関数の中で「終了」したい場合は、それは返り値を返すということなので、この場合は return とする。

補足:非破壊的メソッド・破壊的メソッドの違い

Ruby のメソッドには、ときどき、非破壊的メソッドと破壊的メソッドの 2 バージョンが用意されている。次の例をみてほしい(注:pry は irb の高機能版のようなものである)。

[1] pry(main)> s = "abcde"
=> "abcde"
[2] pry(main)> t = s.slice(-2, 1)
=> "d"
[3] pry(main)> s
=> "abcde"

これをみると、次のことがわかる。

  • s.slice(-2, 1) の返り値は、指示通りにスライスした “d” である。
  • しかし、スライスされた s は、変化がない。

このように、メソッドを適用されたインスタンス側に何の影響もないようなメソッドを、非破壊的メソッドという。しかし全てのメソッドが非破壊的だと、インスタンスを変化させるときに一手間必要になる。適用されたインスタンスを変化させるメソッドを破壊的メソッドという。慣例的には、Ruby の組み込み関数や標準ライブラリのメソッドは、以下のようになっている。

  • 何も断りがなければ、たいてい非破壊的メソッドである。(例外も多い。 Array.delete など。)
  • 非破壊的メソッドと破壊的メソッドの両方が用意されているときは、メソッド名に ! がついているほうが破壊的である。
    • たとえば、slice の破壊的メソッド版は slice! である。前者も後者も引数は同じであるが、後者は破壊的になっている。上のサンプルの sliceslice! に変えるとどうなるかやってみてほしい。

この違いはどこかで通る道なので、今のうちに説明しておいた。

免責事項

  • 筆者は高橋です。『たのしい Ruby』の権利者や AtCoder 社とは関係ありません。
  • TA は後藤さんと私・高橋ですが、偶然にも同じ苗字の『たのしい Ruby』の作者様とは全く関係ありません。
  • サンプルプログラムには元ネタがあるかもしれませんが、版権元とは全く関係ありません。
  • 内容は正確であるように努力していますが、この文章を読んだ方がこの文章の情報によりいかなる不利益を得ようとも、筆者は責任を負いません。

謝辞

  • 受講生の S さん、TA の後藤さんには、この教材に添って問題を解いていただき、多くの反応を得ています。ありがとうございます。
  • 筆者のプログラミングコンテストの腕前のほとんどすべては、教養学部の全学自由研究ゼミナール「実践的プログラミング」で培われました。厳密には既に履修資格がなかった私をかまわず指導してくださった金子先生に感謝したいと思います。