【AtCoder-Ruby】ABC104 C - All Green

問題

問題文

現在、1 以上 D 以下のそれぞれの整数 i に対して、100i点を付けられた問題が pi 問存在します。
これらの p1 + … + pD 問が AtCode に収録された問題のすべてです。
AtCode のユーザーは 総合スコア と呼ばれる値を持ちます。
ユーザーの総合スコアは、以下の 2 つの要素の和です。

• 基本スコア: ユーザーが解いた問題すべての配点の合計です
• コンプリートボーナス: 100i 点を付けられた pi 問の問題すべてを解いたユーザーは、基本スコアと別にコンプリートボーナス ci 点を獲得します ( 1 ≤i ≤D)

AtCode の新たなユーザーとなった高橋くんは、まだ問題を 1 問も解いていません。 彼の目標は、総合スコアを G 点以上にすることです。
このためには、少なくとも何問の問題を解く必要があるでしょうか？

制約

• 1 ≤D ≤10
• 1 ≤pi ≤100
• 100 ≤ ci ≤ 10 ** 6
• 100 ≤ G 入力中のすべての値は整数である
• ci, G はすべて 100 の倍数である
• 総合スコアを G 点以上にすることは可能である。

問題リンク

考えたこと

むずい。。。
多分貪欲法で、一番点数の高い問題から順に実行すると思うけど、ボーナスはどうする。
すべてのパターンをチェックするだと間に合わない。

神に聞いてみよう。

全完する難易度帯を 2D 通り決め打ちする

• それだけで G 点に到達する場合はそれで OK
• それだけでは到達しない場合は、全完対象でないもののうち Greedy に高難易度から順に解いて行けば OK

ここで全完対象でないものを結果的に全完してしまう場合などへの不安が頭をよぎるが、
そういうやつは「そういうやつについても全完するように決め打ちした場合」できちんと考慮されるはずなので気にしなくて OK！

出典: AtCoder ABC 104 C - All Green (300 点)

なるほど。

回答

答え見ちゃいましたが、おいらなりに書いてみました。

def chmin(a, b) a < b ? a : b end

D, G = gets.strip.split.map(&:to_i)

counts = []
points = []
D.times { |i| counts[i], points[i] = gets.strip.split.map(&:to_i) }

res = 10 ** 6
(1<<D).times do |mask|
  sum = 0
  count = 0
  D.times do |i|
    unless (mask & (1<<i)).zero?
      sum += (counts[i] * (i + 1) * 100) + points[i]
      count += counts[i]
    end
  end

  if sum < G
    (D - 1).downto(0) do |i|
      next unless (mask & (1<<i)).zero?
      (0...counts[i]).each do
        break if sum >= G
        sum += (i + 1) * 100
        count += 1
      end
    end
  end
  res = chmin(count, res)
end

puts res

考察

bit 全探索 について

けんちょんさんの回答で 1をシフトする処理があり、これが何かわからなかった。。。
調べた結果これもけんちょんさんのエントリーだが「bit 全探索」アルゴリズムで、数十件であれば、この手法が適用可能。

bit 全探索とは、n 個の要素からなる集合 {0,1,…,n−1} の部分集合をすべて調べ上げる手法のことです。以下のように実施できます: 　・ この解法では例えば n=100 となると計算時間的に破綻してしまいます。

bit 全探索

だから「これはなんか結構大変な Greedy になりそうな予感がするところに、制約 D≤10 が目に入る。」という件がでてくるのか。なるほど。

もっと良い書き方は？（正解者を参照）

一番短いやつを参照してみました。
Ruby とか Perl とか直感で書けると気持ちい良いけど、後から見直した時に思い出せる程度には見やすさも大切と感じる。
バランスが大切。

eval"D,G,*A="+`dd`.split*?,
p (0..1023).map{|b|n=e=0;s=G;D.times{|i|q,c=A[i*2,2];e+=100;b[i]>0?(n+=q;s-=q*e+c):Q=q*E=e};s>0?s>Q ? G: n--s/E: n}.min

【AtCoder-Ruby】ABC104 B - AcCepted

問題

問題文

文字列 S が与えられます。 S のそれぞれの文字は英大文字または英小文字です。
S が次の条件すべてを満たすか判定してください。

• S の先頭の文字は大文字の A である。
• S の先頭から 3 文字目と末尾から 2 文字目の間（両端含む）に大文字の C がちょうど 1 個含まれる。
• 以上の A, C を除く S のすべての文字は小文字である。

制約

• 4 ≤|S| ≤10（|S| は文字列 S の長さ）
• S のそれぞれの文字は英大文字または英小文字である

問題リンク

考えたこと

• 1, 2番目の条件はスライスで
• 3番目は正規表現で判定
• ふるいに掛けるようにダメな条件を先にチェックし余ったものを正解にする
• 正規表現で一行でできそうだが、時間内には思いつかない

回答

S = gets.strip

if !S[0].eql?('A')
  puts 'WA'
elsif !(S[2, S.size - 3].count('C') == 1)
  puts 'WA'
elsif !S[1..-1].match(/[ABD-Z]/).nil?
  puts 'WA'
else
  puts 'AC'
end

考察

もっと良い書き方は？（正解者を参照）

なるほど。シンプルに正規表現でかけばOKか。

s = gets.strip
puts s.match(/^A[a-z]+C[a-z]+$/) ? 'AC' : 'WA'

【AtCoder-Ruby】ABC105 B - Cakes and Donuts

問題

問題文

ABC 洋菓子店では, 1個 4ドルのケーキと 1個 7ドルのドーナツが売られている。
このとき, 合計金額が Nドルとなる買い方はあるか, 判定せよ。
ただし, 同じ商品を二個以上買っても良く, 買わない商品があっても良いものとする。

制約

N は 1 以上 100 以下の整数

問題リンク

考えたこと

• DFS（深さ優先探索）

回答

CP = 4
DP = 7

N = gets.strip.to_i

def dfs(c, d, p)
  return c + d if p == 0
  return 0 if p < 0 

  res = 0
  res += dfs(c + 1, d, p - CP)
  res += dfs(c, d + 1, p - DP) if res == 0
  return res
end

res = dfs(0, 0, N)
p res
puts res > 0 ? 'Yes' : 'No'

考察

もっと良い書き方は？（正解者を参照）

他の人の回答を見ていると全探索で解いている。
ループの最大値は、ケーキの料金（4）を合計金額で割ったもの +1 で良さそう。
また、金額の計算は一方の金額と合計金額にて算出

CP = 4
DP = 7

N = gets.strip.to_i

is_exist = false
((N / CP) + 1).times do |i|
  rem = N - (i * CP)
  if rem >= 0
    if (rem % DP) == 0
      is_exist = true
      break
    end
  else
    break
  end
end
puts is_exist ? 'Yes' : 'No'

まずは、全探索を検討するが定石。

【AtCoder-Ruby】ABC106 B - 105

問題

問題文

1 以上 N 以下の奇数のうち、正の約数をちょうど 8個持つようなものの個数を求めよ。

制約

N は 1 以上 200 以下の整数

問題リンク

考えたこと

• 制約もゆるいので、入力以下の奇数のデータで約数が8個のものを探す
• 約数を取得する処理は関数化

回答

def factor(n) 
  (1..n).select { |i| (n % i) == 0 }
end

n = gets.strip.to_i
puts 1.step(n, 2).select { |i| factor(i).size == 8 }.size

考察

約数の取得処理はよくできたと思うので、少し修正してライブラリ化してもいいかも。

【AtCoder-Ruby】はじめての投稿と振り返り（ポエム）

Ruby で AtCoder 参戦中。

Ruby マスターのために4月から初めたのだけれど、自分のダメさ加減に絶望。。。

 今日は AtCoder ABC126 開催日と定刻（21:00）を迎えた。

が、「開始まであと 23:59:59」。。。明日ガンバ。

ということで、振り返って見る。

なぜはじめたのか

まずなぜ初めたかというと、お仕事で RoR を使うことになり、とりあえずチュートリアルを1周したが、実際に書くとかなり辛い。（ここ2月頃）

実装時間もかかるし、コードと動作がうまく結びつかずモヤモヤが続いた。

Rubyからやらないとダメだということで「プロを目指す人のための Ruby 入門」（チェリー本）、「たのしい Ruby」、「メタプログラミング Ruby」を購入。

チェリー本で Ruby 開眼！（ここ3月頃）

「メタプログラミング Ruby」はまだ目次だけ。後のお楽しみ。

「たのしい Ruby」はパラパラっと見た程度。リファレンスで十分な気がする。 

プロを目指す人のためのRuby入門 言語仕様からテスト駆動開発・デバッグ技法まで (Software Design plusシリーズ)

メタプログラミングRuby 第2版

この頃、AtCoder やってて Google 入りました系のブログが話題になっていた。

やるしかない。

AtCoder ABC デビュー

まずは、ここからスタート

Ruby的な書き方は理解できたと思うが、アルゴリズム理解とかなり残念。。。

あり本読んだり（ DP（動的計画法）の初めまで）、何題か過去問を回答して「AtCoder Beginner Contest 123」（ABC123）デビュー。

とりあえず、3問解けたが、おいらの実力ってこれかと絶望。。。

 2019年4月 

 週に過去問を数問解いて、ABC 参加を繰り返す。

A、B は普通に解けるが C は解けるか解けないかの繰り返しを続ける。 

diverta 2019 Programming Contest

1問正解。これでエンジニアを名乗って良いのかと落ち込む。。。

2019年5月

年号が令和に変わり新しい時代が幕を開けました。

10連休は忍殺に明け暮れる日々を送り。ある意味平和を満喫しておりました。 

#PS4share pic.twitter.com/qGDrsBGYhO

— 虎太郎 (@kharigai) May 2, 2019

 そして、一心を不死斬りした後、

#PS4share pic.twitter.com/16bLIS0zhv

— 虎太郎 (@kharigai) May 9, 2019

SEKIRO: SHADOWS DIE TWICE - PS4

 心新たに AtCoder の過去問を回答しそれをブログに残すことにしました。

note は良いサービスだと思いますが、表現力がいまいちかなと感じました。

はじめの選択肢が絞られていてシンプルで、すぐに初められる気軽さはあるものの、「これできないのかな」というのを調べるのが少しストレスに感じました。

これから

まずは、緑を目指します！

アウトプットはここ（はてなブログ）に。

おっす！オイラ虎太郎

ブログデビューーー