ARC122 B Dif:12 『AtCoder ABC201~225 ARC119~128 灰・茶・緑問題 超詳細解説』サンプル

この記事は 『AtCoder ABC201~225 ARC119~128 灰・茶・緑問題 超詳細解説』 のサンプルです。

【その他のサンプル】
ABC201 A：https://qiita.com/sano192/items/3258c39988187759f756
ABC225 B：https://qiita.com/sano192/items/10133eeb6abc64f1441e
ABC213 C：https://qiita.com/sano192/items/9cd14b2cefd8bafa5615
ABC221 D：https://qiita.com/sano192/items/8679200f0f89e636b354

「ものすごく丁寧でわかりやすいABC解説」シリーズをベースに【キーワード】【どう考える？】【別解】を追加し、【解説】と【実装のコツ】を分けることでよりわかりやすく、具体例や図もより豊富に全ての問題の解説を書き直しました！
さらにQiitaでは公開していないARC119~128の灰・茶・緑問題も解説しています！
緑を目指す灰・茶コーダーの方へおすすめ！

値段：300円(Kindle Unlimited対象)
【kindle】

【booth(pdf)】

ARC119~128の部分のみ抜粋した廉価版 もあります。
値段：200円(Kindle Unlimited対象)
【kindle】

【booth(pdf)】

【キーワード】
三分探索

【どう考える？】
期待値をxの関数E(x)とするとこれは下に凸な関数となっている。三分探索を使ってできるだけ最小に近い場所を探しに行く。

【解説】
x円支払い、シナリオAiで失う金額は
x+Ai−min(Ai,2x)
Aiそれぞれが起こる確率は(1/N)だから、期待値E(x)は
E(x)=(1/N)*Σ(x+Ai−min(Ai,2x))
このE(x)が最小となるようなxを探す。

xは非負実数なので0より大きい。
(Aの最大値)<xの場合、E(Aの最大値)<E(x)となるから(Aの最大値)<xとなるxは答えになりえない。
これはxに大きな数を入れて計算してみればわかる。
A：1 2 3 の場合にE(3)(Aの最大値)とE(100)を計算して計算過程を比較してみよう。
E(3)=(1/3)*((3+1-1)+(3+2-2)+(3+3-3)
E(100)=(1/3)*((100+1-1)+(100+2-2)+(100+3-3)
明らかにE(3)<E(100)になるのがわかる。

よって答えのあり得るxの範囲は
0<x≤(Aの最大値)
となる。

E(x)の形状を確認しよう。
入力例1のA=[1,3,4]の場合、以下のようなグラフになる。

※0.1区切りで計算したものをプロットしただけのグラフなので厳密なものではない。

形としては下に凸になっているのがわかる。
こういったグラフでは三分探索が使える。

「三分探索」
三分探索は山型や谷型のグラフについて、区間を3等分して値を確認しながら区間を狭めていくことにより最大値や最小値を求める方法。
より厳密に説明すると聞き慣れない数学用語がたくさん出てくる。興味があれば調べてもよいが問題を解くにはそこまで必要ない。

最小値を求める手順は以下。

(1)区間の左端、右端を決める
(2)区間を3等分する
(3)3等分の左側、右側の値を確認し、大きい方を新しい区間の端とする
(4)(1)~(3)を十分な回数行う
(5)左端または右端の値を出力する

～例～
N：3
A：3 1 4

求めるのは期待値E(x)の最小値。グラフの一番低いところの値である。

(1)区間の左端、右端を決める
説明したとおり、xの範囲は0<x≤(Aの最大値)となるから
0<x≤4
の範囲で確認すればよい。
左端(L)：0
右端(R)：4
左端の「0」は本来xの範囲に含まれないが、三分探索を行うに当たってはあまり気にしなくて良い。どのみち「0」は一番低いところにならないので左端は更新されていくからだ。

(2)区間を3等分する
中央左(center left)をcl、中央右(center right)をcrとしよう。

cl、crは以下の式で計算できる。
cl=(L*2+R)/3
cr=(L+2*R)/3

L=0,R=4を入れてみよう。
cl=(0*2+4)/3=1.33…
cr=(0+2*4)/3=2.66…
このように区間0~4がいい感じに3等分されているのがわかると思う。

(3)3等分の左側、右側の値を確認し、大きい方を新しい区間の端とする

明らかにE(cl)<E(cr)である。
よってcrのラインを新しいRとする。

区間の長さが2/3となったのがわかるだろう。
「常に区間内に小さい方が残るようにする」と考えるとどちらのラインを残すかわかりやすいと思う。

(4)(1)~(3)を十分な回数行う
(1)~(3)の処理を何度も行っていると区間がどんどん狭くなり、以下のような形になる。

「十分な回数」が具体的にいくらかというのは関数の形と許容される誤差による。そしてそれを厳密に計算するのはかなり難しい。

しかしやればやるほど区間は狭くなり、最小値に近づいていくから、問題を解くときはTLEしない程度に多くの回数を行うようにすれば良い。
本問の場合、E(x)1回の計算で最大O(N)≒10^5回程度の計算が必要になる。pypyなら10^7回程度は余裕で計算できるから、(1)~(3)の操作を100回程度はできる。
1回につき区間の長さが(2/3)になるから100回行うともとの区間LR(長さ4)は
4*(2/3)^100
まで狭まることになる。とてつもなく狭い区間になるのがわかるだろう。

(5)左端または右端の値を出力する
E(R)かE(L)を出力すれば終わり。
LR間は十分に狭くなっているからほとんどL=Rとなっている。どちらを出力してもほぼ同じ値が出る。

【実装のコツ】
＜pypyで提出＞
三分探索はとにかく試行回数を増やすことで精度が上がるため、pythonより実行速度が早いpypyを使うのがよい。
「pypy」はプログラミング言語の一つで、pythonで書いたコードを高速で実行することができる。
(pythonは2sec以内にだいたい10^6回、pypyは2sec以内にだいたい10^8回計算が可能)

＜関数を作ってグラフの形を確認＞
期待値の計算は予め自分で関数を定義しておくと良い。
問題を解く時、最初に関数を作ることでグラフがどのような形をしているか簡単に確認できる。
x=0.1,0.2,...の値で期待値を計算し、エクセルかGoogleスプレッドシートを使ってグラフを作ってみれば形がわかる。
面倒ならそこまでしなくても、値を出力して眺めればどのような形になっているかはわかるだろう。

【提出】

提出

# pypyで提出

# 入力の受け取り
N=int(input())
A=list(map(int,input().split()))

# 期待値計算
# 引数：x　返り値：x円支払い失う金額の期待値
def E(x):
    # 期待値
    result=0
    # i=0~(N-1)まで
    for i in range(N):
        # シナリオA[i]が起きた時失う金額
        result+=(x+A[i]-min(A[i],2*x))
    # 各シナリオの起こる確率=(1/N)を掛ける⇔Nで割る
    result/=N
    # 値を返す
    return result

# 左端
L=0
# 右端
R=max(A)

# 100回
for i in range(100):
    # 中央左側
    cl=(2*L+R)/3
    # 中央右側
    cr=(L+2*R)/3
    # 中央左側が低いまたは同じ
    if E(cl)<=E(cr):
        # 右側を更新
        R=cr
    # 中央右側が低い
    else:
        # 左側を更新
        L=cl

# 答えの出力
print(E(cl))

【別解】
公式解説にある通り、期待値はx=(Aの中央値)/2とした時最小となる。
リストの中央値はソートして真ん中を取るか、statisticsライブラリのmedianを使えば計算できる。

提出

# 入力の受け取り
N=int(input())
A=list(map(int, input().split()))

# 中央値の計算
from statistics import median
x=median(A)

# xを2で割る
x/=2

# 期待値計算
ans=0
for a in A:
    ans+=x+a-min(a,2*x)
ans/=N

# 答えの出力
print(ans)