【AtCoder-Ruby】ARC012 C - 五目並べチェッカー

個人的に、「これが解ければ業務任せてもロジック部分は安心だな！」って思える問題は五目並べチェッカーなのよね。https://t.co/wIKuygqlzs

— chokudai(高橋 直大)🍆🍡🌸 (@chokudai) 2019年6月17日

これを見て挑戦！

「白と黒の合計のチェック」と「5個連続のチェック」でうまくいくと思ったが、うまくいかず。。。

とりあえず、この助言を参考に実装

• 黒石と白石の数は、一致しているか黒石が１つ多くなければらない。そうでなければ到達不可。
• 最後に石を打った番の方は、１つ石を取り除くと５石連続しない（そうしないと途中で対戦が終了しているから）
• 最後に石を打った番でない方は、５石連続しない。

出典

碁のルールを知らず、5個以上の塊と勘違いしていた。。。
連続なのだから直線！

こちらを参考にさせて頂きました。m(__)m
betrue12

回答

# - 白と黒の石は同じか黒が1つ多い
# - 白と黒両方が勝つことはない
# - 5石連続は1つ（2つはない）
# - 勝った方は、１つ石を取り除くと５石連続しない（そうしないと途中で対戦が終了しているから）

CHAIN = 5
N = 19
W = "x"
B = "o"

LINE = [
  [0, N - CHAIN, 0, N - 1, CHAIN.times.map { |i| [i, 0] }],          # 右
  [0, N - 1, 0, N - CHAIN, CHAIN.times.map { |i| [0, i] }],          # 下
  [0, N - CHAIN, 0, N - CHAIN, CHAIN.times.map { |i| [i, i] }],      # 斜め右下
  [CHAIN - 1, N - 1, 0, N - CHAIN, CHAIN.times.map { |i| [-i, i] }], # 斜め左下
]

@bord = N.times.map { gets.strip }

def fin(yes)
  puts yes ? "YES" : "NO"
  exit
end

def is_win(bw)
  win = false
  N.times do |i|
    N.times do |j|
      LINE.each do |x1, x2, y1, y2, ary|
        next unless i.between?(x1, x2) && j.between?(y1, y2)
        if ary.all? { |x, y| @bord[i+x][j+y].eql?(bw) }
          win = true
          break  
        end
      end
      break if win
    end
    break if win
  end
  win
end

bc = 0
wc = 0

N.times do |i|
  bws = @bord[i].scan(/[xo]/)
  next if bws.size.zero?
  bc += bws.count(B)
  wc += bws.count(W)
end

# 白と黒の石は同じか黒が1つ多い
if bc.eql?(wc) || bc.eql?(wc + 1)
  b_win = is_win(B)
  w_win = is_win(W)

  # 白黒両方勝ちはない
  fin(false) if b_win && w_win

  # 継続中（勝ち負けなし）の場合
  fin(true) if !b_win && !w_win

  # 白黒どちらかが勝っている
  bw = b_win ? B : W

  # 黒勝ちの時、白は黒の数 -1（黒勝ちの時、黒白同じ数はない）
  fin(false) if bw.eql?(B) && bc.eql?(wc)
  
  # 白勝ちの時、白は黒は同じ数
  fin(false) if bw.eql?(W) && bc.eql?(wc + 1)

  # 勝った方は、１つ石を取り除くと５石連続しない状態がある（そうしないと途中で対戦が終了しているから）
  N.times do |i|
    N.times do |j|
      if @bord[i][j].eql?(bw)
        @bord[i][j] = '.'
        fin(true) unless is_win(bw)
        @bord[i][j] = bw
      end
    end
  end
end

fin(false)

だめなやつだけど貼っておく

だめなところは、連続の捉え方が間違っているところ。
塊ではだめ。

# - 白と黒の石は同じか黒が1つ多い
# - 白と黒両方が勝つことはない
# - 5石連続は1つ（2つはない）
# - 勝った方は、１つ石を取り除くと５石連続しない（そうしないと途中で対戦が終了しているから）

N = 19
W = "x"
B = "o"

@bord = N.times.map { gets.strip }

def fin(yes)
  puts yes ? "YES" : "NO"
  exit
end

def get_chains(bw)
  map = Array.new(N) { Array.new(N) { true } }

  mv = [[1, 0], [-1, 0], [0, 1], [0, -1], [1, 1], [1, -1], [-1, 1], [-1, -1]]

  chains = []

  N.times do |i|
    N.times do |j|
      if @bord[i][j].eql?(bw)
        queue = [[j, i]]     
        chain = 0
        until queue.size.zero?
          x, y = queue.shift
          mv.each do |m|
            next_x = m.first + x
            next_y = m.last  + y
            if next_x >= 0 && next_x < N &&
               next_y >= 0 && next_y < N && 
               map[next_y][next_x] && @bord[next_y][next_x].eql?(bw)

                chain += 1
                map[next_y][next_x] = false

                queue.push([next_x, next_y])
            end
          end
        end
        chains << chain if chain >= 5
      end
    end
  end
  chains
end

bc = 0
wc = 0

N.times do |i|
  bws = @bord[i].scan(/[xo]/)
  next if bws.size.zero?
  bc += bws.count(B)
  wc += bws.count(W)
end

# 白と黒の石は同じか黒が1つ多い
if bc.eql?(wc) || bc.eql?(wc + 1)
  b_chains = get_chains(B)
  w_chains = get_chains(W)

  # 5石連続は1つ以上ない
  fin(false) if b_chains.size > 1 || w_chains.size > 1

  # 白黒両方に5石連続はない
  fin(false) if b_chains.size.eql?(1) && w_chains.size.eql?(1)

  # 継続中（勝ち負けなし）の場合
  fin(true) if b_chains.size.eql?(0) && w_chains.size.eql?(0)

  # 白黒どちらかが勝っている
  bw = b_chains.size > 0 ? B : W
  bw_max = b_chains.size > 0 ? b_chains.first : w_chains.first

  # 黒勝ちの時、白は黒の数 -1（黒勝ちの時、黒白同じ数はない）
  fin(false) if bw.eql?(B) && bc.eql?(wc)
  
  # 白勝ちの時、白は黒は同じ数
  fin(false) if bw.eql?(W) && bc.eql?(wc + 1)

  # 勝った方は、１つ石を取り除くと５石連続しない状態がある（そうしないと途中で対戦が終了しているから）
  N.times do |i|
    N.times do |j|
      if @bord[i][j].eql?(bw)
        @bord[i][j] = '.'
        fin(true) if get_chains(bw).size.zero?
        @bord[i][j] = bw
      end
    end
  end
end

fin(false)

考察

強い人のソースは参考になる。

【AtCoder-Ruby】ABC130 振返り & しゃくとり法

ABC130 振返り

とりあえず、A, B のタイムは「10:47」。（A:01:36）
概ね目標（10分）に届いてた。

Cは一旦飛ばして最後に実施したが、よくよく見ると簡単な問題だった。。。
ただ、他の人のコメントをみたのでそう思うだけだろう。
ここも、もう少し問題を解いていけば自然に解けるようになると思う。
C - Rectangle Cutting

Dに関しては累積和で実装したが "TLE"
実装している時も O(N ^ 2) なので無理だろうなと思った。
また、ふと「しゃくとり法」ならできるのかなと思ったが、それまだ詳しくしらないので、タイムアウト
（そう思えるようになったので少しは進化しているかなと自分を慰める）

これはダメなやつ。

N, K = gets.strip.split.map(&:to_i)
a = gets.strip.split.map(&:to_i)
 
s = Array.new(N + 1) {0}
 
N.times do |i|
  s[i + 1] = a[i] + s[i]
end
 
c = 0
(1..N).each do |l|
  (l..N).each do |r|
    c += 1 if (s[r] - s[l - 1]) >= K
  end
end
 
puts c

しゃくとり法

ということで、調べたらけんちょんさんがアップしてくれていました。
早い！

• AtCoder ABC 130 D - Enough Array (400 点)
• しゃくとり法 (尺取り法) の解説と、それを用いる問題のまとめ

彼の解説は本当にわかりやすい。
基本的なしゃくとり法の考え方、実装方法は理解できた。
後は数問解いてみればOK!

実装サンプル

int right = 0;     
for (int left = 0; left < n; ++left) {
    while (right < n && (right を 1 個進めたときに条件を満たす)) {
        /* 実際に right を 1 進める */
        // ex: sum += a[right];
        ++right;
    }

    /* break した状態で right は条件を満たす最大なので、何かする */
    // ex: res += (right - left);

    /* left をインクリメントする準備 */
    // ex: if (right == left) ++right;
    // ex: else sum -= a[left];
}

出典: しゃくとり法 (尺取り法) の解説と、それを用いる問題のまとめ

回答

N, K = gets.strip.split.map(&:to_i)
a = gets.strip.split.map(&:to_i)

res = 0
sum = 0
r = 0
N.times do |l|
  while r < N && sum < K
    sum += a[r]
    r += 1
  end
  
  break if sum < K

  res += N - r  + 1

  if l.eql?(r)
    r += 1
  else
    sum -= a[l]
  end
end

puts res

考察

今は「チータ本」で DP の基本がわかってきた。
もう少し理解を進めれば正解率が上がりそうな気がする。

この投稿をInstagramで見る

虎太朗さん(@kotazon)がシェアした投稿 - 2019年 6月月14日午後9時43分PDT

【AtCoder-Ruby】C - Typical Stairs（& ABC129 振返り）

ABC129 振返り

とりあえず、A, B のタイムは「20:17」。
10分を目標にしていたが、問題によって時間がかかる。。。

課題は練習の回答数が少ない。（現在100問弱というところ）
とりあえず、ABC AB 全問は解いてみようと思う。

C に関しては法則がピンとこなかった。
正解を見て、なるほど（フィボナッチとDP）と納得できたが、これも勉強と経験両方不足しているということだろう。

C - Typical Stairs 理解

参考にさせて頂きました。

• 動的計画法（DP）について学ぶ。
• トップダウン形式とボトムアップ形式と2種類のDPのうち、今回はボトムアップ形式の説明。

アルゴリズムのお勉強（３）- 動的計画法(DP) : ボトムアップ形式

ただ、ボトムアップ方式（配るDP）より、トップダウン（貰うDP）の方が好みなので、こちらで実装。

参考: 動的計画法超入門！ Educational DP Contest の A ～ E 問題の解説と類題集

問題

問題文

N 段の階段があります。高橋君は現在、上り口( 0 段目)にいます。 高橋君は一歩で 1 段か 2 段上ることができます。
ただし、a1, a2, a3, .... aM 段目の床は壊れており、その段に足を踏み入れることは危険です。
壊れている床を踏まないようにしながら、最上段( N 段目)にたどりつくまでの移動方法は何通りあるでしょうか？ 総数を 1 , 000 , 000 , 007 で割った余りを求めてください。

制約

• 1 ≦ N ≦ 10 ** 5
• 0 ≦ M ≦ N − 1
• 1 ≦ a 1 < a 2 < ... < a M ≦ N − 1

問題リンク

回答

N, M = gets.strip.split.map(&:to_i)

mod = 10 ** 9 + 7

# bf: broken floors
bf = {}
M.times.map { bf[gets.strip.to_i] = 1 }

dp = Array.new(N + 1){0}

dp[0] = 1
dp[1] = 1 if bf[1].nil?

(2..N).each do |i|
  next unless bf[i].nil?
  # 自動型変換 version
  # dp[i] = dp[i - 1] + dp[i - 2]
  dp[i] = (dp[i - 1] + dp[i - 2]) % mod
end

# 自動型変換 version
# puts dp[N] % mod
puts dp[N]

考察

Ruby では演算結果により自動で型変換されるので、最後にあまりの計算して実行結果を確認したところ、3倍程度の差が出た。（コメント # 自動変換 version）

RubyではFixnumクラスとBignumクラスで整数値を、Floatクラスで浮動小数点を扱うことができます。
またMathモジュールでは三角関数や対数などを計算する関数が提供されます。
Fixnumは31ビットまたは63ビットの固定長整数を扱うクラスですが、演算結果をこの範囲を超える場合、自動的にBignumに拡張されます。
Bignumは無限多倍長整数でメモリの許す限りの大きな値を扱うことができます。

Fixnum: 32bit 符号付き整数なので、取りうる範囲は「−2,147,483,648 から 2,147,483,647」

自動変換 version

自動変換 なしversion

早く茶色になりたいなー

www.instagram.com

【AtCoder-Ruby】ABC B - Bumble Bee（落葉拾い）

AB 問題の Time Atack のため、歯抜けになっている問題を埋めていたが、Hash 構文がうろ覚えでタイムロスした。。。
備忘のため記録しておく。

問題

問題文

高橋君はマルハナバチ(Bumblebee)という種類のミツバチです。 今日も花の蜜を求めて異なる N 個の花を訪れました。
高橋君が i 番目に訪れた花の種類は Ai です。
i 番目の花は、 i > j かつ i 番目の花の種類と j 番目の花の種類が同じになるような j が存在すれば受粉します。
高橋君が訪れた N 個の花の種類の情報が与えられるので、そのうちいくつの花が受粉したか求めてください。
なお、高橋君以外による受粉や自家受粉を考える必要はありません。

問題リンク

間違い

N = gets.strip.to_i

h = {}
N.times { h[gets.strip.to_i] += 1 }
# => null エラー

sum = 0
h.values do |v|
  sum += v - 1
end

puts sum
# => 0 のまま do end の処理がされていない？

Null エラーは Hash.new でデフォルト値を設定することで回避

# 0で初期化
h = Hash.new(0)

# 空の配列で初期化したい場合はこれ
h = Hash.new([])

sum が 0 問題は values は配列を返すので each が必要

sum = 0
h.values.each do |v|
  sum += v - 1
end
puts sum

# => 等価
puts h.values.inject(0) { |sum, v| sum += v - 1 }

回答

N = gets.strip.to_i

h = Hash.new(0)
N.times { h[gets.strip.to_i] += 1 }

puts h.values.inject(0) { |sum, v|  sum += v - 1 }

考察

配列、文字列操作、ハッシュは定期的に復習すること！
特にハッシュは出番が少ないので意識して復習が必要！

www.instagram.com

【AtCoder-Ruby】ABC Time Attack（88-90）

ABC A, B を 10分以内に回答する課題に取り組んでいる。

サマリー

Contest	A Time	B Time	Total
ABC088	02:41	05:32	08:13
ABC089	01:56	03:25	05:21
ABC090	03:52	04:54	08:46

回答

ABC088

自分の提出

N = gets.strip.to_i
A = gets.strip.to_i

puts (N % 500) <= A ? 'Yes' : 'No'

_n = gets.strip.to_i
a = gets.strip.split.map(&:to_i).sort.reverse

sum_even = 0
sum_odd = 0
a.each_with_index do |n, i|
  if i.even? 
    sum_even += n
  else
    sum_odd += n
  end
end
  
puts sum_even - sum_odd

ABC089

自分の提出

puts gets.strip.to_i / 3

_n = gets.strip.to_i
puts gets.strip.split.uniq.size.eql?(3) ? 'Three' : 'Four'

ABC090

自分の提出

puts gets.strip[0] + gets.strip[1] + gets.strip[2]

A, B = gets.strip.split.map(&:to_i)
 
c = 0
(A..B).each do |i|
  c += 1 if i.to_s.eql?(i.to_s.reverse)
end
puts c

考察

落ち着いてやれば、10分以内は十分可能。
この処理で問題ないか、リファレンスなどで確認するとその分時間がかかる
やはり、読解力（問題文からロジックへの変換）が一番の課題だと思う。

C 以降は、もう少しアルゴリズムよりの思考が必要だが、ABに関しては問題文をそのままロジックにおこせればOK。

ばんばりやー

www.instagram.com

【AtCoder-Ruby】累積和をマスターする

累積和を何も考えずに書けるようにする！ を自分なりに理解する。

考え方

サンプル実装

puts "L R N"
puts "a1 a2 a3 a4 .. aN"
puts
puts "input: " 

L, R, N = gets.strip.split.map(&:to_i)
a = gets.strip.split.map(&:to_i)

# 累積和の初期化
s = Array.new(N + 1) {0}

N.times do |i|
  s[i + 1] = a[i] + s[i]
end

puts "ans: #{s[R] - s[L - 1]}"

$ ruby cumulative_sum.rb
L R N
a1, a2, a3, a4, .. an

input:
3 5 7
1 2 3 4 5 6 7

ans: 12

練習問題

ABC122 C - GeT AC を解いてみる。

問題文

A, C, G, T からなる長さ N の文字列 S が与えられます。
以下の Q 個の問いに答えてください。

• 問 i ( 1 ≤ i ≤ Q): 整数 l i , r i ( 1 ≤ l i < r i ≤ N) が与えられる。 S の先頭から l i 文字目から r i 文字目までの (両端含む) 部分文字列を考える。この文字列に AC は部分文字列として何回現れるか。

考え方

回答

N, Q = gets.strip.split.map(&:to_i)
S = gets.strip

lr = Q.times.map { gets.strip.split.map(&:to_i) }

a = Array.new(N + 1) {0}

N.times do |i|
  a[i + 1] = S[i..(i+1)].eql?('AC') ? a[i] + 1 : a[i]
end

lr.each do |l, r|
  puts a[r - 1] - a[l - 1]
end

考察

2次元の累積和は一旦概念だけ理解。
あとで実装する。

この投稿をInstagramで見る

どや

虎太朗さん(@kotazon)がシェアした投稿 - 2019年 4月月21日午前5時19分PDT

【AtCoder-Ruby】ABC095 B - Bitter Alchemy

問題文文字列 S が与えられます。 S のそれぞれの文字は英大文字または英小文字です。 S が次の条件すべてを満たすか判定してください。 - S の先頭の文字は大文字の A である。 - S の先頭から 3 文字目と末尾から 2 文字目の間（両端含む）に大文字の C がちょうど 1 個含まれる。 - 以上の A, C を除く S のすべての文字は小文字である。制約 4 ≤|S| ≤10（|S| は文字列 S の長さ） S のそれぞれの文字は英大文字または英小文字である 問題リンク

https://kotazon.hatenablog.com/entry/2019/05/22/064009

問題

問題文

パティシエの赤木さんは、「お菓子の素」という粉のみを材料として N 種類のドーナツを作ることができます。
これらのドーナツはドーナツ 1 、ドーナツ 2 、 . . . 、ドーナツ N と呼ばれます。 ドーナツ i ( 1 ≤ i ≤ N) を 1 個作るには、お菓子の素 m i グラムを消費する必要があります。 なお、 0.5 個など整数でない個数のドーナツを作ることはできません。 いま、赤木さんはお菓子の素を X グラム持っています。 これを使って、今夜のパーティーに向けて可能な限りたくさんのドーナツを作ることにしました。 ただし、来客の味の好みは様々なので、次の条件を守ることにしました。

• N 種類のドーナツそれぞれを少なくとも 1 個は作る。

このとき、最大で何個のドーナツを作ることができるでしょうか？お菓子の素を使い切る必要はありません。 また、この問題の制約のもとでは、条件を守ることは必ず可能です。

制約

• 2 ≤ N ≤ 100
• 1 ≤ m i ≤ 1000
• m1 + m2 + ... + mN ≤ X ≤ 10 ** 5
• 入力中のすべての値は整数である。

問題リンク

考えたこと

別種類のものを1個づつ作り、その後は一番安いものを作り続ける

はじめに作ったもの（13:20）

N, X = gets.strip.split.map(&:to_i)
a = N.times.map { gets.strip.to_i }

c = a.size
sum = X - a.inject(:+)
m = a.min

while sum > 0
  break if sum < m
  sum -= m 
  c += 1
end

puts c

回答

もっとシンプルにできるので2回目作成（3:30）

N, X = gets.strip.split.map(&:to_i)
a = N.times.map { gets.strip.to_i }

puts N + ((X - a.inject(:+)) / a.min)

考察

ABC095 A - Something on It は、2:50 だったので、16:10 で AB 完了。