AtCoder Beginner Contest 144 E,F問題メモ

AtCoder Beginner Contest 144

E - Gluttony

• $N$ 人チームで大食い大会に出る
  • 大会では、$N$ 個の食べ物を1人が1個ずつ担当し、完食する
  • 各人の消化コストは $A_1,A_2,...,A_N$
  • 各食べ物の大きさは $F_1,F_2,...,F_N$
  • 消化コスト $A_i$ の人が大きさ $F_j$ の食べ物を完食する時間は $A_iF_j$
  • 大会でのスコアは、最も完食が遅かった人の時間
• 大会までに、各人の消化コストを整数単位で合計 $K$ まで下げられる。0未満にはできない
• このチームが大会で達成できるベストタイムを求めよ
• $1 \le N \le 2 \times 10^5$
• $0 \le K \le 10^{18}$
• $1 \le A_i,F_i \le 10^6$

問題タイトルのグラトニーとは貪食という意味で、七つの大罪にも含まれる。グラットンソードはみんなの憧れ。

ABC143に続き、答えを決め打って二分探索で解ける問題。復習大事。

かかる時間の最小値は消化コストを全て0にしたときの0、最大値は $\max(A) \times \max(F) \le 10^{12}$。 この間で、タイム $t$ が達成可能を判定する。1回あたり $O(N)$ で判定できれば、全体で $O(N \log(\max(A) \max(F)))$ でできる。

誰がどれを担当すればよいかというと、$A_i$ を昇順に、$F_i$ を降順にソートして、先頭から順番に組にしていけばよい。

以下、$A_1,A_2,...$ は昇順ソート済み、$F_1,F_2,...$ は降順ソート済みの順番とする。

特訓して消化コストを下げた状態を $B_1,B_2,...$ とする。

最大値を低くするのだから、小さいのと大きいのを組み合わせればいいというのはなんとなく思うので、それが正しいことを証明する。

 i  1  2  3
B   3  5  8
F  10  7  2

ここで $B$昇順・$F$降順に並んだ状態から、$B_2$ と $B_3$ を入れ替えて、変化した部分のみのスコアを比較すると

• 今の状態のスコア: $\max(B_2F_2, B_3F_3)$
• 入れ替えたスコア: $\max(B_2F_3, B_3F_2)$

ここで、$B_3F_2$ は、$B_2F_2, B_3F_3$ のいずれよりも必ず大きい（か等しい）ので、入れ替えてスコアが悪くなることはあっても、改善されることは無い。

よって、この状態が最適で、降順の $F$ に対して、$B$ は昇順で組にしてよい。

（ここから、特訓後 $B_i$ に対応するのは $A_i$ でいいのかの証明も必要だが、略）

食べ物の大きさ $F_i$ と目標タイム $t$ が決まっていたら、それを担当する人の消化コスト $B_i$ の制約は決まり、$B_i \le \frac{t}{F_i}$（切り捨て）である。

$A_i$ が $\frac{t}{F_i}$ より大きいなら、その差分だけ特訓が必要。逆に低いなら不要。

必要な特訓量を計算し、その合計が $K$ 以下なら目標タイム $t$ は達成可能と判定できる。

素のPythonで組むとちょっと時間が厳しめだが、こういう「配列の全ての数を $x$ で割る」「2つの配列の同じindexを組にして同じ演算を行っていく」処理はNumPyが使いどころ。

F - Fork in the Road

• $N$ 個の部屋と $M$ 本の通路からなる洞窟があり、各部屋には $1,2,...,N$ の番号が付いている
• 通路を通って部屋1から $N$ まで移動する
• $i$ 番目の通路は $s_i$ → $t_i$ を一方通行に結ぶ
  • 全て $s_i \lt t_i$
• $N$ 以外の全ての部屋は、最低1つの出路があることが保証される
• 各部屋から次の部屋への移動は、その部屋の出路を等確率で1つ選んでおこなう
• 出発前に1本だけ、好きな通路を消すことができる（消さなくてもよい）
  • ただし、消すことでその部屋からの出路が無くなるような通路は消せない
• 1から $N$ までに通ることになる通路の期待値を考えたとき、最小値はいくらか
• $2 \le N \le 600$
• $N-1 \le M \le \frac{N(N-1)}{2}$

「この部屋から伸びる通路を消す」と決め打って、その時の期待値を求めて最小値を探す。全体で $O(M)$ となる。

通路を消すという奇妙な操作はできるものの、まずはそもそもの消さない場合の期待値の計算が出来ないことには答えが出ないので、その方法を考える。

通路の条件を見ると、$s_i \lt t_i$ より有向非巡回グラフであることがわかるので、部屋番号の若い方から順に処理していけそう。

しかし先頭から順に決めていこうとすると、いまいちうまくできない。 各部屋につき「通った通路数」と「その通路数でその部屋に到達する確率」を分けて持てば計算できなくは無いが…… 遷移の計算量が $N$ 倍になって面倒なので、他の方法を考える。

                        ,---------------,
              1 ------ 2 ------ 3 ------ 4
               `---------------'        |
               `------------------------'
(通路,確率) (0,1)   (1,1/3)  (1,1/3)  (1,1/3)
                             (2,1/6)  (2,1/2)
                                      (3,1/6)

後ろから求めるとうまくいく。「部屋 $i$ を出発して」$N$ までに通る通路数の期待値 $e_i$ を求めていく。

部屋 $i$ から $j,k,l$ に出路があったとすると、$e_j,e_k,e_l$ は既に求まっているので $\displaystyle e_i=\frac{e_j+e_k+e_l}{3} + 1$ で求められる。

                ,---------------,
      1 ------ 2 ------ 3 ------ 4
       `---------------'        |
       `------------------------'
ei  11/6      3/2       1        0

$e_1$ が通路を消さない場合の期待値となる。計算量は辺数に依存し、$O(M)$ となる。

部屋 $i$ から出る通路を消すと決め、消さない場合からの削減量を考える。

まず、出路が1本しか無い部屋の通路は消せないので、飛ばしてそれ以外を考える。

通路を消して期待値を下げるということは、 残り通路数期待値（$e$）の多い部屋へ繋がる通路を消し、 少ない部屋へ向かう確率を上げるということである。

なので最も効率的なのは、$i$ から出る通路の内、次の部屋の $e$ が最大の部屋への通路を消すことである。

                ,---------------,
      1 ------ 2 ------ 3 ------ 4
       `---------------'        |
       `------------------------'
ei            3/2       1        0

この場合、1からは2,3,4へ行けるが、2へ繋がる通路を消すのが効果的

通路を消した場合の $e_i$ に相当する期待値を $e'_i$ とし、次の部屋を $j,k,l$ とすると、以下のようになる。

$\displaystyle e'_i = \frac{e_j+e_k+e_l - \max(e_j,e_k,e_l)}{3 - 1} + 1$

これと $e_i$ との差分 $d_i = e_i - e'_i$ が、「$i$ を出発し $N$ までに通る通路数の期待値を、 通路を1つ消すことによって削減できる量」ということになる。

では、これが全体（1を出発した場合）に対してどれだけ効いてくるかというと、 1を出発して $i$ を経由する確率を $p_i$ とすると、$p_i \times d_i$ で求められる。

よって、各部屋に至る確率 $p_i$ を求める。こちらは先頭からのdpで求められる。

$p_id_i$ の最大値が、最も効果の高い通路を消した際の削減量であり、 これを通路を消さない場合の期待値 $e_1$ より引いた結果が答えとなる。