AtCoder Beginner Contest 116
Updated:
6 位でした。
Source codes
Solutions
A - Right Triangle
コンテスト中に思いついた解法
直角三角形であることから、その面積は $3$ 辺のうち短い方から $2$ つの辺の積の半分である。
恐らく模範解答
$\angle ABC = 90^\circ$ が保証されているので、 sort は必要ない。
x = gets.chomp.split(" ").map{|i| i.to_i}
puts x[0] * x[1] / 2
ポイント
問題文の誤読に近いが、安全策を取ったと考えれば許せる。
B - Collatz Problem
素直に $f$ を実装する。 set<ll> S; を用意する。 $a _1 = s$ とし、以降 $a _{i + 1} = f(a _i)$ を計算する。 $S$ に問い合わせて存在すればその添字が答え。そうでなければ $S$ に $a _{i+1}$ を突っ込む。これを繰り返す。 $1000000$ 回以内に終わることが保証されているのでこれで間に合う。
ポイント
$a _{i} \leq 1000000$ が保証されているので int でよかった。
C - Grand Garden
解法
$0$-indexed とする。貪欲法をやる。水やりをして花の高さを伸ばすのではなく、時を戻す魔法を使って花の高さを小さくしていくことにする。魔法を使って全部 $0$ にする最小回数を求める。
$i = 0, \dots, N - 1$ に対し、 $h[i] > 0$ ならば、以下の動作を行う： $j = i, \dots, N - 1$ に対し、 $h[i] > 0$ ならば $h[i]$ を 1 減らし、そうでなければ break; する。ループを抜ける度に ans++; する。これで答えが求まる。
貪欲法で良いことの証明
まず $i$ 番目に対し $h[i]$ を $0$ にするためには、 $i$ 番目の花に $h[i]$ 回の魔法を適用する必要がある。そして $0$ になったものに魔法を適用してはいけない(ルールの読み変える前だと $h[i] + 1$ に成長してしまう)ので、ちょうど $h[i]$ 回適用する必要がある。
魔法の適用する方法は有限なので、必ず回数の最小値が存在する。その最小値を実現する魔法の適用の仕方を $1$ つ固定する。この魔法の適用の仕方で、 $i = 0$ の花に対して適用した魔法の区間を順に $[0, x _0], [0, x _1], \dots, [0, x _{h[i] - 1}]$ とする。ここで、貪欲な方法でない区間 $[0, x _k]$ が存在すると仮定する。つまり、この魔法を適用した直後に $h[x _k + 1] > 0$ であると仮定する。するとこの魔法を適用した後に、必ず区間 $[l, r]$ に適用する魔法が存在して、 $x _k + 1 \in [l, r]$ を充たす。したがって $j \in [l, r]$ に対して $h[j] > 0$ である。
しかしこのとき、 $[0, x _k]$ の代わりに $[0, r]$ を適用し、 $[l, r]$ の代わりに $[l, x _k]$ を適用しても、回数は変わらないし、魔法も適用できることがわかる。したがって最小値を達成しつつ、より「貪欲」な魔法の適用方法が見つかる。これを有限回繰り返すことで、結局 $i = 0$ に関しては上記の貪欲法で最小回数が達成可能であることがわかる。
すると残りの問題は $i = 1$ から先だけになるので、問題は小さくなっている。以降も貪欲法を適用し続ければ良い。したがって上記の解法で解答が求まる。
ポイント
証明は思いつく前に、直感で「これは貪欲法だ」で実装した。うまく実装できた。
D - Various Sushi
$0$-indexed とする。
まず「おいしさ基礎ポイント」を貪欲に取ることを考える。つまり typedef tuple<ll, int> sushi; とし、 $\{ (d[i], t[i]) \}$ を vector<sushi> V; に突っ込んで標準順序で sort, reverse しておく。 $i = 0, \dots, K - 1$ に対し、 $d[i]$ の和をとる($X$ とする)。このとき、
$cnt[i] = $ 今までに取ったネタ $i$ の寿司の数
と定めておき、同時に計算しておく。 $v = \sharp \{ i \in N \mid cnt[i] > 0 \}$ とし、まずひとまず $A = X + v^2$ とする。これが答えの候補である。つまり 「種類ボーナスポイント」は「ひとまず貰えるもんはもらっておこう」 の姿勢である。
これ以上の得点を取るためにはどうすれば良いか？ おいしさ基礎ポイント自体はすでに最大値 なので、 「おいしさ基礎ポイント $X$ は減るけれども、種類ボーナスポイントは増えて、結果得点が増える」 以外に可能性はない。ここで「 $X$ をできるだけ減らさない」けれども「 $v$ は $1$ 増えている」という状態は、以下のように貪欲に求めることができる。
取った寿司を priority_queue<sushi, vector<sushi>, greater<sushi>> Q; に突っ込んでおく。 $i = K, \dots, N - 1$ に対し、以下の動作を実行する。まず $cnt[t[i]] > 0$ ならば、これは $v$ の増加に寄与しないので無意味であるから無視する。 $cnt[t[i]] = 0$ の場合、検討する価値がある。 $Q$ から寿司を取り出していくと、前段階で取った寿司をおいしさが小さい順に取り出すことができる。ここで $(x, y)$ が取り出されたとする。 $cnt[y] > 0$ は保証されている。
- $cnt[y] \geq 2$ の場合：寿司 $(x, y)$ の代わりに寿司 $(d[i], t[i])$ を取ることで、「 $X$ をできるだけ減らさない」けれども「 $v$ は $1$ 増えている」という状態が達成される。 $v, X, cnt$ は適切に動かし $A \gets \max(A, X + v^2)$ とする。そして $i$ を進ませる。
- $cnt[y] = 1$ の場合：寿司 $(x, y)$ の代わりに寿司 $(d[i], t[i])$ を取っても損をするだけである($v$ は変わらず $x \geq d[i]$ であるから)。ゆえに操作の対象ではない。
また $Q = \emptyset$ になったらその時点で打ち切りである。以上により答えが求まる。計算量は $O(N + K \log K)$ である。実装に priority queue を使う必要はもちろんなく、尺取り方の逆方向みたいにすることで $O(N + K) = O(N)$ になる。
ポイント
ほぼほぼ、貪欲法だった。最初は種類数を固定すると思っていたけれども、うまくいかないようだった。 「ひとまず貰えるもんはもらっておこう」 に気付いてからは、 $X$ と $v$ のトレードオフができた。
Others
A - sample: 3, tle: 2.000, time: 01:13, from_submit: 23:10
B - sample: 3, tle: 2.000, time: 03:35, from_submit: 19:34
C - sample: 3, tle: 2.000, time: 02:16, from_submit: 17:19
D - sample: 3, tle: 2.000, time: 17:19, from_submit: 00:00