鉄分は大事。(特にヘム鉄)

研究とか開発とかプログラミングとか趣味とかを備忘録的な感じで気が向いたときに.

ABC032に参加した

 Atcoderで行われているAtcoderBeginnerContest,通称ABCに参加した。

Welcome to AtCoder Beginner Contest 032 - AtCoder Beginner Contest 032 | AtCoder

 今までいくつかこういうのに参加してたけど、参加記ってめんどくさかったので書いたことなかった。他の人が書いてるのを見て、思考の整理になりそう&後々振り返るときなどに役に立ちそうと思ったので試しに書いてみることにした。

A. 高橋君と青木君の好きな数

 A,B二つの数で割れる,N以上の数を出力せよ、という問題。

 最小公倍数を使って・・・とか考えたが,制約を見て全探索すればいいやと思って妥協して実装した。AC時間は開始6分ぐらい。

a = gets.to_i
b = gets.to_i
n = gets.to_i
ans = n
loop do
 if ans % a == 0 && ans % b == 0
 break
 end
 ans += 1
end
puts ans

B. 高橋君とパスワード

 文字列Sに対して、長さKの部分文字列の数Tを数え上げる問題。

  • K > Sの場合は0を出力した。
  • K ≦ S の場合、見つけた部分文字列を配列Tに保存していく。
    i 文字目から i + K 文字目までの部分文字列 tmp を切り出す。
    これが新しい部分文字列の場合、 T に保存する。
    最後に T の長さを計算する。

AC時間は開始14分ぐらい。

s = gets
k = gets.to_i
t = []
if s.length < k
    puts 0 
else
    for i in 0..(s.length - k - 1)
        tmp = s[i..(i + k - 1)]
        if t.include?(tmp)
            next
        else
            t.push(tmp)
        end
    end
    puts t.length
end

C 列

 長さNの数列S、整数Kがある。Sのうち、すべての要素の値の積がK以下となるような、連続した部分列の最長の長さを求める問題。

 Sに0が含まれる場合、解はNとなる。

 Sに0が含まれ、かつK>0の場合、要素の積がK以下となるような配列sと、その積mを作成する。数を一つ取得するたびにmを再計算する。そして、m>Kの間、先頭の要素をpopしてmを再計算する。この際、sの長さの最大値を保存しておく。

 だいたいの方針は上の通り。再計算に関して、はじめ、数の出入りがあるたびにすべての要素について再計算していてTLEした。考えて、出入りする数に関してだけ計算すれば良いと気づき変更した。変更の際、出入りする要素が0のとき、mがnilのときに注意する必要があった。(2REした)

 尺取り法なるアルゴリズムがあって、それに似たようなものになったと思う。

AC時間は開始65分ぐらい。(一回目の提出は30分ぐらい)

n, k = gets.split.map(&:to_i)
s = []
max = 0
m = 0
n.times do
    s.push(gets.to_i)
    if s[-1] == 0
        max = n
        break
    end
 
    if m == 0 || m == nil
        m = s.inject(:*)
    else
        m *= s[-1]
    end
 
    while m.to_i > k
        t = s.shift
        if t.to_i != 0 && m.to_i != 0
            m /= t
        else
            m = s.inject(:*)
        end
    end
 
    if s.length > max
        max = s.length
    end
end
puts max

D ナップサック問題

 3つの条件があって、それらの条件に応じて適切なアルゴリズムを用いてナップサック問題を解く問題。できなかった。

 ナップサック問題の解法は蟻本を写経したものが手元にあったので、それをコピペしたらいけるやろとか思ってたらそんな甘くなかった。要復習。

 条件によってアルゴリズムが変わるのは面白いと思った。

さいごに

 できれば全完したかったができなかったので悔しい。ただ、まだまだ初心者でやることがたくさんあるのはわかっているので(蟻本、チーター本、ABCの過去問など)、練習を重ねて上達していきたい。

 余談だが、サンプルケースをコピペするのがめんどくさいと思いrubyでそのへんやってくれるatcoder_greedyなるgemを作ったんだが、本番でうまくサンプルを取得してくれなかった。