kotazon.com

虎太郎の備忘録

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

AtCoder 振返り しゃくとり法

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

しゃくとり法

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

彼の解説は本当にわかりやすい。
基本的なしゃくとり法の考え方、実装方法は理解できた。
後は数問解いてみれば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 の基本がわかってきた。
もう少し理解を進めれば正解率が上がりそうな気がする。