ham-capのブログ

プログラミング学習の記録

【Ruby素振り】AtCoder過去問 347B - Substring

Ruby素振り？

AtCoder Problemsの過去問でAB問題をRubyを使用してひたすら解いていくことを個人的にRuby素振りと名付けて取り組んでいます。

せっかくなので、苦戦したものや勉強になったものをブログに載せていきます。

Rubyを手に馴染ませるというのが主目的なので、競プロっぽい変態的な効率的な書き方を追い求めることはしません。

百人組手的なスタンスなので、あまり綺麗な解法ではないことが多いです。

飽きたらやめます。

今日の問題

atcoder.jp

問題文

英小文字からなる文字列 S が与えられます。S の空でない部分文字列は何種類ありますか？

ただし、部分文字列とは連続する部分列のことを指します。例えば、xxx は yxxxy の部分文字列ですが、xxyxx の部分文字列ではありません。

制約

  • S は英小文字からなる長さ 1 以上 100 以下の文字列

    入力

S

入力例

yay

出力

答えを出力せよ。

解法

s = gets.chomp.chars

def count_substring(strings)
  buff = []
  (1..strings.size).each do |n|
    strings.each_cons(n) { |x| buff << x }
  end
  buff.uniq.size
end

p count_substring(s)

感想

個人的に使い所が難しいと感じるメソッドTop10に入るeach_consを珍しくうまく使えたと思う。

1..strings.sizeの範囲オブジェクトを使ってeach_consで扱う文字数を増やしていくというのも、自分としてはよく思いついたなと思う。

【Ruby素振り】AtCoder過去問 355B - Piano 2

Ruby素振り？

AtCoder Problemsの過去問でAB問題をRubyを使用してひたすら解いていくことを個人的にRuby素振りと名付けて取り組んでいます。

せっかくなので、苦戦したものや勉強になったものをブログに載せていきます。

Rubyを手に馴染ませるというのが主目的なので、競プロっぽい変態的な効率的な書き方を追い求めることはしません。

百人組手的なスタンスなので、あまり綺麗な解法ではないことが多いです。

飽きたらやめます。

今日の問題

atcoder.jp

問題文

長さNの数列A=(A1,A2,…,AN) と、長さM の数列B=(B1,B2,…,BM) が与えられます。ここで、A,B のすべての要素は互いに相異なります。A,B のすべての要素を昇順に並べた長さN+M の数列C=(C1,C2,…,CN+M) において、A に現れる要素が2つ連続するかどうか判定してください。

制約

  • 1≤N,M≤100
  • 1≤Ai,Bj≤200
  • A1,…,AN,B1,…,BM は相異なる
  • 入力はすべて整数

入力

入力は以下の形式で標準入力から与えられる。

N M
A1 A2 … AN
​B1 B2 … BM

入力例

3 2
3 2 5
4 1

出力

A に現れる要素がC において2つ連続するならば Yes を、そうでないなら No を出力せよ。

解法

n, m = gets.chomp.split.map(&:to_i)
a = gets.chomp.split.map(&:to_i)
b = gets.chomp.split.map(&:to_i)
c = (a + b).sort
positions = []

c.each_with_index do |num, idx|
  positions << idx if a.include?(num)
end

ans = []

positions.each_with_index do |pos, idx|
  break if idx == n - 1

  if positions[idx + 1] - pos == 1
    ans << true
    break
  else
    ans << false
  end
end

puts ans.any? ? 'Yes' : 'No'

感想

なんか愚直解で満足しちゃってる感じがして釈然としない。 Rubyのメソッドにしても、手持ちの駒でやりくりしている感が漂っているので、馴染みのないメソッドを積極的に使っていきたい。

【Ruby素振り】AtCoder過去問 366B - Vertical Writing

Ruby素振り？

AtCoder Problemsの過去問でAB問題をRubyを使用してひたすら解いていくことを個人的にRuby素振りと名付けて取り組んでいます。

せっかくなので、苦戦したものや勉強になったものをブログに載せていきます。

Rubyを手に馴染ませるというのが主目的なので、競プロっぽい変態的な効率的な書き方を追い求めることはしません。

百人組手的なスタンスなので、あまり綺麗な解法ではないことが多いです。

飽きたらやめます。

今日の問題

atcoder.jp

問題文

横書きの文章が与えられます。縦書きに直してください。空白を * で埋めてください。

N 個の、英小文字からなる文字列S1,S2,…,SNが与えられます。これらの文字列の長さの最大値をM とします。

以下の条件を満たすM 個の文字列T1,T2,…,TMを出力してください。

  • 各Tiは英小文字および * からなる
  • 各Tiの末尾は * でない
  • 各1≤i≤N について、次が成り立つ
    • 各1≤j≤∣Si∣ についてTjのN−i+1 文字目が存在し、T1, T2,…,T ∣Si∣それぞれのN−i+1 文字目をこの順に連結したものは Si と一致する
    • 各∣Si∣+1≤j≤M について、Tj の N−i+1 文字目は存在しないか、 * である

ただし、∣Si∣で文字列 Si の長さを表します。

制約

  • N は 1 以上100 以下の整数
  • Siは長さ1 以上100 以下の英小文字からなる文字列

    入力

    入力は以下の形式で標準入力から与えられる。

N
S1
​S2 
⋮
SN

入力例

3
abc
de
fghi

出力

答えを以下の形式で出力せよ。

T1
T2 
⋮
TM

解法

n = gets.chomp.to_i
strings = []
n.times do
  strings << gets.chomp
end

filled = []
max = strings.map(&:size).max
strings.each_with_index do |s, i|
  filled << if i.zero?
              s
            else
              s.ljust(max, '*')
            end
end
longest = filled.map(&:size).max
aligned = filled.map { |s| s.ljust(longest, '*') }
transposed = aligned.map(&:chars).reverse.transpose
transposed.each do |t|
  t.pop while t[-1] == '*'
end
transposed.map { |s| puts s.join }

感想

Array#transposeパイセンのおかげで楽勝かと思いきや結構苦戦しました。

変にスマートにしようとして自分流の解釈で書いたコードはいくつかのケースで落ちちゃってうまくいきませんでした。

特に「各Tiの末尾は * でない」という制約は特に難しいものでもないはずなので、最初から愚直にTiの末尾をチェックして削除すればよかったなぁと反省。

それと、そのTiの末尾は*が一個だけではない場合もあると思うので、末尾に*がない状態まできっちり持っていく必要があり、whileを使えばできそうというのに気付くまでややかかりました。

以下の部分ですね。

transposed.each do |t|
  t.pop while t[-1] == '*'
end

whileは繰り返し処理のためのものという固定観念に支配されていましたが、今回のように条件分岐のような使い方もできるということにようやく思い至りました。

「ある状態になるまで処理をn回繰り返したいが、nは毎回異なる」みたいな時、ifだとちょっと厳しいので、whileは非常に便利だなと感じました。

【Ruby】ローカル変数は実行されなくても宣言される

＊この記事の中にはRubySilverの過去問の一部についてネタバレがありますのでご注意ください。

はじめに

数日前から、RubySilver受験に向けて学習を始めました。

こういう試験の定石通り、とりあえず過去問を解いてみて自分の現在の実力を把握しつつ、解説を読んで足りない知識をインプットしているのですが、その中でかなり驚いたことがあったので書いておきます。

ローカル変数の宣言が実行されていない場合にその変数を参照するとどうなるか

公式の過去問に以下の設問があります。（解答も込みなので折りたたんでいます。）

ネタバレ注意

m = true
m or n = true
p n

実行結果として正しいものを選択してください。(1つ選択)

  • (a) true
  • (b) false
  • (c) nil
  • (d) 文法エラーが発生する

<答え>　(c)

ふぁ！？

なんで！！？（僕は(d)を選んで不正解でした。）

この場合ならundefined local variableでエラーになると思ったのに、答えはnil。

irb上で試してみても確かにnilが返ってくる。

最大の疑問は「orの左辺がtrueなら右辺は実行されないはずでは？」ということ。

なので調べてみました。

ローカル変数は実行されなくても宣言される

Rubyリファレンスマニュアルの変数と定数のページ内にあるローカル変数に関する項に、ほんの一文ですが記載がありました。

宣言は、たとえ実行されなくても宣言とみなされます。

v = 1 if false # 代入は行われないが宣言は有効
p defined?(v)  # => "local-variable"
p v            # => nil

マジか…。

また、stackoverflowにある質問では、Rubyはコードの実行前にすでにローカル変数がどのスコープにあるかを把握してるとか、parse時には把握してる的なことも書いてある。

parseという単語も出てきて、Rubyがどういう仕組みで動いているかの話って感じがしたのでもうちょい調べてみると、とても良い記事を発見。

zenn.dev

詳しくはリンクから記事を読んでいただきたいのですが、今回大事なところを引用させていただきます。

Rubyのコンパイル過程は以下の手順で行われています。

  1. Rubyコードをレクサーが字句解析してトークン(単語のかたまり)を作る
  2. トークンをパーサーが構文解析して抽象構文木を作る
  3. 抽象構文木からYARV命令列が生成される
  4. YARV命令列をRubyVMが逐次実行する YJITが有効化されていた場合、実行時にネイティブコード(機械語)が生成され、最適化が行われる

ここで昨年の大阪Ruby会議に参加した時の記憶が一気に蘇ってきました。

パーサー！そして抽象構文木！！！

うおぉぉぉ、、、知ってるぞその言葉ぁぁぁ！！！

詳しくみてみると、たしかにパーサーによる構文解析の段階で元のコード内にある変数が:var_fieldという名前で分類されているように見えます。（それ以前に:on_identというトークン？が割り当てられて、既に変数として仕分けされているっぽい。）

というわけで、ここまでの話を踏まえて最初の話に戻ると、コードが実行された時にorの短絡評価によって右辺n = trueが実行されなかったとしても、それ以前にパーサーによって構文解析がなされた段階で既にn = trueは宣言されており、Ruby的にはnというローカル変数は存在していることになる。

しかしコードが実行されていない以上、代入は行われていないため、結果としてnを参照しようとするとnilになるということらしい。

すげぇ。なんかテンション上がってきた。

インスタンス変数の場合はどうなのか

これも先ほどの変数と定数のページ内にあるインスタンス変数の項に書いてありました。

初期化されていないインスタンス変数を参照した時の値はnilです。

あ、そうなんすね。

このあたり、ローカル変数とインスタンス変数ではそもそもの扱いが全然違うっぽいのですが、この記事の主旨から外れるのでインスタンス変数については挙動が違うってことだけおさえて、一旦ここまでにします。

まとめ

というわけで、資格の勉強をしていたら思いがけず昨年参加したイベントの内容と繋がって妙にテンションが上がったという話でした。

パーサーとか構文木とか、自分には遠い世界の話だと思っていたのになんだかんだ出会ってしまった。

近所のスーパーに出かけたら知ってるお笑い芸人見かけたぐらいの気持ち。

FBCを卒業してからはもっぱらRubyの基礎を学び直しているのですが、Rubyの構造を知ること自体が楽しくなってきたので、コツコツやっていけたらなと思っています。

自由に好きなことを学べるって最高。

おわり！

【Ruby素振り】AtCoder過去問 377B - Avoid Rook Attack

Ruby素振り？

AtCoder Problemsの過去問でAB問題をRubyを使用してひたすら解いていくことを個人的にRuby素振りと名付けて取り組んでいます。

せっかくなので、苦戦したものや勉強になったものをブログに載せていきます。

Rubyを手に馴染ませるというのが主目的なので、競プロっぽい変態的な効率的な書き方を追い求めることはしません。

百人組手的なスタンスなので、あまり綺麗な解法ではないことが多いです。

飽きたらやめます。

今日の問題

atcoder.jp

問題文

縦 8 マス、横 8 マスの 64 マスからなるマス目があります。 上から i 行目(1≤i≤8)、左から j 列目(1≤j≤8) のマスをマス(i,j) と呼ぶことにします。

それぞれのマスは、空マスであるかコマが置かれているかのどちらかです。 マスの状態は長さ 8 の文字列からなる長さ 8 の列(S1​, S2, S3, …, S8) で表されます。 マス (i,j) (1≤i≤8,1≤j≤8) は、Si の j 文字目が . のとき空マスで、# のときコマが置かれています。

あなたは、すでに置かれているどのコマにも取られないように、いずれかの空マスに自分のコマを置きたいです。

マス(i,j) に置かれているコマは、次のどちらかの条件を満たすコマを取ることができます。

  • i 行目のマスに置かれている
  • j 列目のマスに置かれている

あなたがコマを置くことができるマスがいくつあるか求めてください。

制約

  • Si は ., #からなる長さ 8 の文字列(1≤i≤8)

入力

入力は以下の形式で標準入力から与えられる。

S1
​S2
​S3
​S4
​S5
​S6
​S7
​S8​

入力例

...#....
#.......
.......#
....#...
.#......
........
........
..#.....

出力

すでに置かれているコマに取られずに自分のコマを置くことができる空マスの個数を出力せよ。

解法

board = []
8.times do
  board << gets.chomp.split('')
end

empty_i = []

board.each_with_index do |line, idx|
  empty_i << idx unless line.include?('#')
end

transposed = board.transpose

empty_j = []

transposed.each_with_index do |line, idx|
  empty_j << idx unless line.include?('#')
end

p empty_i.size * empty_j.size

感想

一見ややこしそうに思えたものの、既存のコマが取れる範囲が単純だったので、各行・各列で#が含まれていないポイントを見つけてそれらの交差するところが空マス、という考え方で上手くいった。

久しぶりにRubyのArray#transposeの存在を思い出して使ってみたのだけど、こういう時めちゃ便利。

というかもうRubyが便利すぎて、Rubyに解かせていただいてる感すらある。

参考

Array#transpose (Ruby 3.4 リファレンスマニュアル)

【Ruby素振り】AtCoder過去問 379B - Strawberries

Ruby素振り？

AtCoder Problemsの過去問でAB問題をRubyを使用してひたすら解いていくことを個人的にRuby素振りと名付けて取り組んでいます。

せっかくなので、苦戦したものや勉強になったものをブログに載せていきます。

Rubyを手に馴染ませるというのが主目的なので、競プロっぽい変態的な効率的な書き方を追い求めることはしません。

百人組手的なスタンスなので、あまり綺麗な解法ではないことが多いです。

飽きたらやめます。

今日の問題

atcoder.jp

問題文

高橋君は歯が左右一列に N 本生えています。現在の高橋君の歯の状態はある文字列 S によって表されます。

S の i 文字目が O のとき、左から i 番目の歯が丈夫であることを表します。 S の i 文字目が X のとき、左から i 番目の歯が虫歯にかかっていることを表します。丈夫である歯は虫歯にかかっていません。

高橋君はある連続する K 本の歯が丈夫であるとき、その K 本の歯を使ってイチゴを 1 個食べることができます。イチゴを食べると、その K 本の歯が虫歯にかかり丈夫でなくなります。

このとき、高橋君は最大で何個のイチゴを食べることができるか求めてください。

制約

  • 1≤K≤N≤100
  • N,K は整数
  • S は O と X からなる長さ N の文字列

    入力

    入力は以下の形式で標準入力から与えられる。

N K
S

入力例

7 3
OOXOOOO

出力

答えを出力せよ。

解法

n, k = gets.chomp.split.map(&:to_i)
s = gets.chomp.split('')
count = 0

s.each_with_index do |t, i|
  next unless t == 'O'

  if s[i..i + k - 1].all?('O') && s[i..i + k - 1].size == k
    count += 1
    s.fill('X', i..i + k - 1)
  end
end

puts count

感想

k個連続Oがあるのをどう確認するかで手間取ってしまった。

それと、fillに置換後の値と範囲オブジェクトを渡すことで、ある配列の一部だけをその値で埋めるという使い方を初めてやってみた。

るりまにはちゃんと説明が載っているのだけど全然読めてなかった。

参考

Array#fill (Ruby 3.4 リファレンスマニュアル)

【Ruby素振り】AtCoder過去問 381A - 11/22 String

Ruby素振り？

AtCoder Problemsの過去問でAB問題をRubyを使用してひたすら解いていくことを個人的にRuby素振りと名付けて取り組んでいます。

せっかくなので、苦戦したものや勉強になったものをブログに載せていきます。

Rubyを手に馴染ませるというのが主目的なので、競プロっぽい変態的な効率的な書き方を追い求めることはしません。

百人組手的なスタンスなので、あまり綺麗な解法ではないことが多いです。

飽きたらやめます。

今日の問題

atcoder.jp

問題文

文字列Tが以下の条件を全て満たすとき、Tを11/22文字列と呼びます。 - ∣T∣ は奇数である。ここで、∣T∣ は T の長さを表す。 - 1 文字目から ∣T∣+1 / 2 −1 文字目までが 1 である。 - (∣T∣+1) / 2文字目が / である。 - ∣T∣+1 / 2 + 1 文字目から∣T∣ 文字目までが 2 である。

例えば 11/22, 111/222, / は 11/22 文字列ですが、1122, 1/22, 11/2222, 22/11, //2/2/211 はそうではありません。

1, 2, / からなる長さ N の文字列 S が与えられます。S が 11/22 文字列であるか判定してください。

制約

  • 1≤N≤100
  • S は 1, 2, / からなる長さ N の文字列

入力

入力は以下の形式で標準入力から与えられる。

N
S

入力例

5
11/22

出力

S が 11/22 文字列であれば Yes を、そうでなければ No を出力せよ。

解法

n = gets.chomp.to_i
strings = gets.chomp.split('')
if n == 1 && strings[0] == '/'
  puts 'Yes'
  return
end

if strings[(n + 1) / 2 - 1] == '/' &&
   strings[(0..(n + 1) / 2 - 2)].size == strings[((n + 1) / 2)..(n - 1)].size &&
   strings[(0..(n + 1) / 2 - 2)].all? { |s| s == '1' } &&
   strings[((n + 1) / 2)..(n - 1)].all? { |s| s == '2' }
  puts 'Yes'
else
  puts 'No'
end

感想

毎度のことではあるものの、今回も愚直に条件を満たすように書いたらとりあえずOKでした。

ただ、A問題であるということを踏まえると、もっとシンプルに書けるはずと思い他の方の回答も見てみることに。

自分と同じように愚直に書いている方が割と多くてちょっと安心したのも束の間、以下の書き方を発見。

思考が柔軟で素晴らしいなと思ったので引用させていただきます。

n = gets.to_i
s = gets.chomp
if "#{'1' * (n / 2)}/#{'2' * (n / 2)}" == s
  puts 'Yes'
else
  puts 'No'
end

https://atcoder.jp/contests/abc381/submissions/62481201

このコード読んだ瞬間「う…、うわぁぁぁあぁぁあぁぁぁぁあぁあぁ！！！！」ってなりました。

あやかりたい。