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の場合は０を出力した。
- 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を再計算する。そして、ｍ>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
