2022.01.30

競プロ典型90問 001:Yokan Partyをやってみた

競プロ典型90問の第1回『Yokan Party』をやってみた。難しいけどこれは面白い。

今年からAtCoderを再開するにあたって、とりあえず水色を目指したいと思い、E869120さんの競プロ典型90問をやっていくことにした。今自分は茶色なので、先頭から順に★5以下の問題を片付けていく方式で進める。

第1回のYokan Partyは★4なのでちょうどいい。と思ったら普通に難しすぎたので解説を見た。

問題概要

普通に問題文を書こうと思ったら、ブログにKaTexのCSSを当てていないことに気付いたので問題文のリンクだけ貼っておく。近々数式表記できるようにしておきたい。

考え方

スコアが最大になるように分割するときのスコアを求める。

スコアはその時切り分けられた中で最も短いピースの長さなので、切り分けられたピースすべての長さがスコア以上になっている。と言える。

なので、スコアMを仮決めしておいて、ようかんをK+1個に切り分けてそれぞれがMcm以上になっているかを見る。
条件に合致した中で最も高いMの値が答え。

この仮決めしていく過程には二分探索を使う。
例えばようかんが50cmだとして、仮決めしたスコア25が大きすぎた場合は26〜50cmを試す意味はない。逆に仮決めしたスコアでようかんを切り分ける事ができたら、もう少し大きなスコアを狙えないかを試す。こうして2分探索を終えた時のスコアが最大スコアになる。

二分探索でスコアを決めた後の問題は『じゃあN個の切れ目のうちどこで切ればいいの？』になる。ここは貪欲法を使う。

切れ目を順番に左から見ていって、左端からのようかんの長さがスコアを超えたところで切る。最後まで切っていってK回切ることができない、または最後のピースの長さがスコア未満であれば、そのスコアは実現不可能ということになる。

書いたコード(Ruby)

理解力に自信がなかったのでコメント大量に書いた。

N,L = gets.split.map(&:to_i)
K = gets.to_i
A = gets.split.map(&:to_i) # Aは予め累積和配列になっている
 
# 2分探索用の左端と右端
l = -1
r = L+1
m = 0
 
loop do
  # 中央値を試す
  m = (l+r)/2
 
  # rとlの差が1であればmが確定している
  break if r - l == 1
 
  # 切り離された羊羹の長さ
  cutlen = 0
  # 切った回数
  cutnum = 0
 
  # 左から貪欲法でm以上になるように切る
  N.times do |i|
    # 左端からの長さ - 切り離した分の長さ が m以上であればそこで切る
    if A[i] - cutlen >= m
      cutnum += 1 # 切った回数を加算
      cutlen = A[i] # 切り離した分の長さを記録
    end
 
    # K回切ったら判定へ
    break if cutnum == K
  end
 
  # 次の2分探索をlとrどちらで進めるか決める
  if cutnum != K
    # K回切れなかったのでmが大きすぎた
    # 次の探索はmを上限に行う
    r = m
  elsif L - cutlen < m
    # K回切れたが、最後の1ピースがm未満なのでmが大きすぎた
    # 次の探索はmを上限に行う
    r = m
  else
    # K回切れたがすべてのピースがm以上なのでもっと大きいmを探す
    # 次の探索はmを下限に行う
    l = m
  end
end
 
puts m

所感

1回目からこんなに難しくて、90問いつになったら終わるんだろう？と思ったけど、解説読んで理解できると『ははぁ、なるほど』と報酬系が刺激されるのでいい問題(上から目線)。

競プロの解説ACには二段階あると思っていて

解説を読んで考え方がわかれば書ける
解説を読んだ上でコード例も読んでようやく書ける

今回は解説あり、コード例なしで終えられたので1の方になる。2でも勉強にはなるんだけど、敗北感と劣等感が大分重たいのでできれば解説読んで実装できるようにしたい。