AtCoder 射撃王 考察と証明っぽいもの
abc023.contest.atcoder.jp
AtCoder Beginner Contest 023 解説
ABC23回のD問題とその解説より引用
問題文
高橋君は最近、射撃にハマっている。高橋君は N 個の風船すべてを射撃で割り、得られる得点をできるだけ小さくする競技に参加している。
風船には 1 から N までの番号が付けられていて、風船 i(1≦i≦N) は競技開始時に高度 Hi のところにあり、1 秒経過するにつれて高度が Si だけ増加する。
高橋君は競技開始時に 1 個風船を割ることができ、そこから 1 秒ごとに 1 個の風船を割ることができる。どの順番で風船を割るのかは高橋君が自由に決定できる。
どの風船についても、その風船を割ることによるペナルティが発生する。ペナルティはその風船が割られたときの高度と等しい整数値となる。高橋君が最終的に得る得点は N 個の風船のペナルティのうちの最大値となる。
高橋君が得ることのできる得点として考えられる最小値を求めよ。
Opt > X ならばどうやっても達成できない
Opt <= X ならば貪欲法で達成できる
本当にそうか？
なにが疑問か、というと、
貪欲法で得たペナルティの最小値が、本当に全ケースの最小値なの？<=>（同値） ペナルティ最小値となる打ち方の中に貪欲法の打ち方が存在するの？
ようするに
この問題の解法は、↓を前提にしてるんですよ
でも↓のようになってた場合、この解法じゃ正しい解にならなくね？ってこと
というわけで、一枚目の画像のようになっていることの説明を必死こいて考えました
定義:
風船の集合 B (要素数はnとする)
その打った順番 τB
k番目に打った風船 (τB)k*1
k番目に打つはずの風船を打たずにt-1秒立った時の高さ h( (τB)k,t)*2
補題1:
風船集合Bの全ケースを考慮したペナルティ最小値を取るような、ある打ち方τを考える。このk番目に割った風船が、他のどの風船よりも高いとこで割られてペナルティとなったとする。このとき
j < k番目の風船はk-1秒目の時点でk番目に割られた風船より高くなければならない。すなわち
j< k => h((τB)j,k) >= h((τB)k,k)
背理法で証明する
j
わった順番は前提より
(τB)1,(τB)2,(τB)3,...,(τB)j,...,(τB)k,...,(τB)n
その高さは
h((τB)1,1),h((τB)2,2),h((τB)3,3),...,h((τB)j,j),...,h((τB)k,k),...,h((τB)n,n)
前提よりh(k,k)が最も高いので,
h((τB)x,x) < h((τB)k,k) {x ≠ k} ... ①
ここで,割るのをjとkを入れ替えてみると
(τB)1,(τB)2,(τB)3,...,(τB)k,...,(τB)j,...,(τB)n
その高さは
h((τB)1,1),h((τB)2,2),h((τB)3,3),...,h((τB)k,j),...,h((τB)j,k),...,h((τB)n,n)
hの性質より
h((τB)k,j) < h((τB)k,k) {k< k}//より時間がたてばより高くなる// ... ②
また背理法の仮定より
h((τB)j,k) < h((τB)k,k) ... ③
①②③より、jとk入れ替えた打ち方をすると、どの風船も割られた高さがh((τB)k,k)をこえないため、ペナルティがh((τB)k,k)よりも小さくなってしまう。これはh((τB)k,k)が全ケースのペナルティ最小値ということに矛盾する。よって
j< k => h((τB)j,k) >= h((τB)k,k)
補題2:
補題１と同じ前提で
j > k番目の風船はk-1秒目の時点でk番目に割られた風船より低くなければならない。すなわち
j > k => h((τB)j,k) < h((τB)k,k)
当たり前。τは全ケース最小値となる打ち方の一つである。もし
j > k => h( (τB)j,k) >= h( (τB)k,k)
であるならば、k番目の風船を打った時の位置関係が
〇 h( (τB)j,k)//j番目にうつ予定
----〇--------------------------- h( (τB)k,k)//k番目にうった
となってしまう。前提よりτBのなかではh( (τB)k,k)が最大なのだからありえない。
本題
ペナルティ最小値となる打ち方の中に貪欲法の打ち方が存在するの？
新たな定義
T(τ,(τB)j) 風船の集合Bをτの順番で打つとき、ｊ番目の風船が、打ち方τの時のペナルティとなる高さを超えるまでの時間*3
P(τB) 風船集合Bをτの順番でうった時のペナルティ
Pmin(B) 風船集合Bの全ケースの中の最少のペナルティ
前提(補題と同じ)
風船集合Bの全ケースを考慮したペナルティ最小値を取るような、ある打ち方τを考える。このk番目に割った風船が、他のどの風船よりも高いところで割られてペナルティ = Pmin(B)となったとする。
このとき
(τB)1 から (τB)k-1 までの風船集合とその並びをτ1B1
(τB)k+1 から (τB)n までの風船集合とその並びをτ2B2
とする
k番目に割った風船がペナルティなので
h( (τB)x,x) < h( (τB)k,k) {1 <= x <= k-1}
h( (τB)x,x) < h( (τB)k,k) {k+1 <= x <= n}
よって,τ1B1のなかだけで競技をしたと仮定してペナルティを考えたとき,そのペナルティはh( (τB)k,k) = Pmin(B)を超えない。
すなわち P(τ1B1) < h( (τB)k,k) = Pmin(B)
またPmin,Pの定義より
Pmin(B1) < P(τ1B1)
ゆえにB1の風船集合の全ケースを考えたときの最小ペナルティ = Pmin(B1) < P(τ1B1) < h( (τB)k,k) = Pmin(B) をみたす
同様に Pmin(B2) < P(τ2B2) < h( (τB)k,k) = Pmin(B)
どういうことかというと、
風船の並びを
τB = τ1B1 + (τB)k + τ2B2
って分解したとして、τ1、τ2をそれぞれB1,B2を最少のペナルティで打つ打ち方τ1',τ2'にして
τ'B = τ1'B1 + (τB)k + τ2'B2
っておきかえても、τ'Bもまた全ケース最少のペナルティをとるやり方である
だってそうでしょ？
まずB1を、最もペナルティの少ないやり方で打つ。そのペナルティはh( (τB)k,k)をこえない
つぎに(τB)kをうつ。このペナルティはh( (τB)k,k)
そしてB2を最もペナルティの少ないやり方で打つ。そのペナルティはh( (τB)k,k)をこえない
よってこの打ち方のペナルティの最大値はh( (τB)k,k) = Pmin(B)
時間関係Tもみていく
j < k なら T(τ, (τB)j) < T(τ, (τB)k)
なぜなら補題１より
j< k => h( (τB)j,k) >= h( (τB)k,k) = ペナルティの高さ
j番目に割る風船は、（打たなければ）k番目の風船より先にペナルティの高さを超えるからである。つまりj番目の風船はk番目の風船よりも、ペナルティを超えるまで時間が短い
また
k < j なら T(τ, (τB)k) < T(τ,(τB)j)
なぜなら補題2より
j< k => h( (τB)j,k) <= h( (τB)k,k) = ペナルティの高さ
k-1秒時点でk番目に割る風船(τのペナルティとなる風船)、はj番目の風船より先にペナルティの到達しているはずである。補題２の図をみればわかる
この時間の関係式,jに関する部分をB1とB2に置き換えてやる
1 < j < k-1 => T(τ, (τ1B1)j) < T(τ, (τB)k)
1 < j < n-k => T(τ (τB)k) < T( (τ,(τ2B2)j)
そしてこれで証明は完了してしまったのだ！！！！！！
今までの証明を振り返ろう
たとえば、Bのある打ち方が、全ケース最小のペナルティをとるやり方τだとする。
τBについて考えてみよう、
ｋの前に割った風船の集合をB1,
kの後に割った風船の集合をB2とする
Pmin(B) = P(τB) = h( (τB)k,k)
B1,B2の中だけで最少のペナルティとなるようなうち方τ1',τ2'にいれかえる
(Pmin(B1) = P(τ1'B1),Pmin(B2) = P(τ2'B2))
τ'B = τ1'B1 + (τB)k + τ2'B2
このとき、いつまでに割るかという制限時間は短い順に
B1,(τ'B)k,B2
また、
τ' は依然として全ケース最小のペナルティをとる打ち方です
τ1'B1について考えてみよう
そのτ1'のペナルティとなるk'番目に割った風船について、
k'の前に割った風船の集合をB11,
k'の後に割った風船の集合をB22とする
Pmin(B1) = P(τ1'B1) = h( (τ1'B1)k',k')
B11,B21の中だけで最少のペナルティとなるようなうち方τ1'1',τ2'2'にいれかえる(Pmin(B11) = P(τ1'1'B11),Pmin(B22) = P(τ2'2'B22))
τ1''B1 = τ1'1'B11 + (τ1'B1)k' + τ2'2'B22
このとき、いつまでに割るかという制限時間は短い順に
B11,(τ1''B1)k',B22
いままでのとあわせて
いつまでに割るかという制限時間は短い順に
B11,(τ1''B1)k',B22,(τB)k,B2
またτ'Bの右辺のτ1'B1を置き換えて
τ''B = (τ1'1'B11 + (τ1'B1)k' + τ2'2'B22) + (τB)k + τ2'B2
τ'' は依然として全ケース最小のペナルティをとる打ち方です
τ1'1'B11について考えてみよう
...
千年後
おおっと、B1,k,B2がどんどん分割されて
いつまでに割るかという制限時間は短い順に
b1,b1,b3,...,bn
(bk は風船一個を表す)
みたいにあらわせたぞ
つまりこの並びをτfとすると
τfは制限時間の短い順の貪欲法でとった並び
で、上の再帰をみると、τ',τ'',....,そしてやはりτfも
τf は依然として全ケース最小のペナルティをとる打ち方です
がなりたつ。
よって、
ペナルティ最小値となる打ち方の中に貪欲法の打ち方が存在するの？
します。τfがまさにそれです。
やったぜ。
風船集合Bが空の時とか厳密じゃないけどまあいいでしょ。
