ABC116 解説 - ARMERIA

AtCoder Beginner Contest 116 - AtCoder

こどふぉと被っていたので参加しませんでした…

A - Right Triangle

解法

三角形の面積は（底辺長）×（高さ）÷２ですね。直角三角形の場合、底辺長と高さは直角を挟む2辺の長さと考えることができます。これを計算しましょう。

ACコード

（Ruby）Submission #4059256 - AtCoder Beginner Contest 116

$\angle ABC = 90^{\circ}$ を見落とすと無駄にソートすることになります。

B - Collatz Problem

解法

この問題の操作は数学においては有名で、どの正の数から始めてもこの操作を続けると有限回で $1\to 4\to 2\to 1\to \cdots$ のループに到達する…ということが予想されています。「コラッツの予想」と呼ばれる未解決問題です。

さて問題文の表現が少し回りくどいですが、「前に出た数と同じものが初めて出現したときのインデックス」を求めればよいです。ということでこれまでに出た数をsetなどで持っておけば「同じものが出た」判定をすることができます。

ACコード

（Ruby）Submission #4059304 - AtCoder Beginner Contest 116

C - Grand Garden

解法

一番左の花から考えていきます。この花の高さが足りない場合、この花を左端とするある範囲に水をあげなければいけません。

ではこの範囲はどのように取るべきでしょうか？できるだけ多くの花に水をあげたほうが効率が良さそうな気がします。実際にこれは「伸ばせるだけ伸ばす」、つまり既に花の高さが足りている花の直前まで範囲を長く取るのが最適となります。これについては以前似たような問題の解説を書いているので、そちらも参考にしてください。

ということで、左から1つずつ見ていって、既に高さが足りている花に当たるまで花の高さを1ずつ足していきます。これを一番左の花の高さが足りるまで繰り返します。

一番左の花の高さが足りたら、次は左から2番目の花を左端として同じように考えます。これを最後の花まで繰り返すと答えが求められます。

計算量的には $O(N \sum h_{i})$ かかる素朴なやり方ですが、制約が小さいのでこれで間に合います。もっと速く解くやり方もありますね。

ACコード

（Ruby）Submission #4059357 - AtCoder Beginner Contest 116

実装は問題の操作とは逆に、「 $h_{i}$ を受け取り、全部0になるまで値を引いていく」と書くと楽です。もちろん、問題の通り「今の花の高さ」を別途配列で用意して値を足していく実装でも解けます。

D - Various Sushi

解法

この問題は解説が難しいですね…

まず、最適な寿司の選び方というものがどのような性質を持っているか考えてみます。例えば入力として

というものを考えてみましょう。このテストケースに対する最適な選び方は以下の図の赤色のものになります。

f:id:betrue12:20190124202804p:plain

満足ポイント $9+8+6+(2\times 2) = 27$ が最適値です。単体の美味しさ優先で $9, 8, 7$ を取ると25ポイント、種類数優先で $9, 6, 2$ を取ると26ポイントで最適になりません。単体の美味しさと種類数、どちらかを無視した貪欲はうまくいかないことが分かります。

このような最適な寿司の選び方が満たす性質があります。それは、「選んだ $K$ 個の寿司は、選ばなかった種類のどの寿司よりも、美味しさが大きいか等しい」という点です。

その理由は、もし選ばなかった種類の寿司の中に選んだ寿司より大きい美味しさを持つものがあれば、寿司を交換することで種類数・美味しさポイントともに有利になり、絶対に満足ポイントが高くなるからです。最適な選び方というからには、より満足ポイントが高い選び方は他に存在しないはずです。

この性質から、もし最適な選び方における寿司の種類数が分かっているならば、次のような方法で最適な選び方を求めることができます。種類数を $k$ とします。

まず全ての種類の寿司から、それぞれの種類で一番美味しい寿司を1つずつ取り出しておき、それらの寿司から美味しい順に $k$ 個選ぶ。
上記で選ばれなかった2番手以降の寿司を集めて、それらの寿司から美味しい順に $K-k$ 個選ぶ。

さきほどの性質を満たすと何故このような選び方で最適になるのかは、以下のように説明できます。

選んだ寿司は選ばなかった種類のどの寿司より大きいという性質、そして $k$ 種類の寿司を選ぶということから、まず各種類のベスト寿司を集めて大きい方から $k$ 個取ることができます。
残りの寿司に関しては、「さっき選んだ $k$ 個と同じ種類から美味しい順に $K-k$ 個選ぶ」という選び方をします。これもまた先ほどの性質のおかげで、単に2番手以降の寿司を集めて上から取れば自然とこのような選び方になります。

こうすることで、「各種類のベスト寿司」と「2番手以降の寿司」を独立に選ぶことができる点が嬉しいです。

肝心の最適な種類数 $k$ はまだ分かっていませんが、 $k$ を全探索すればどこかで最適値が見つかるはずです。このとき上記のやり方で寿司を選んだときの満足ポイントは

（各種類のベスト寿司の、上から $k$ 個の美味しさ和）＋（2番手以降の寿司の、上から $K-k$ 個の美味しさ和）＋ $k*k$