3匹の猫

みみねこの競プロ精進メモ

M-SOLUTIONS プロコンオープン 2020の感想

競プロ解説 参加記

100-200-300-400-0-0 で4完1000点。早解きで良いパフォが付いてもあまりうれしくない。

A

A - Kyu in AtCoder
if文で条件分岐を書いてもいいが、8通りもの分岐を手打ちするのは面倒だし時間がかかる。ここで、レーティングが200変わるごとに級が1減るという法則を見つけることが出来れば、10-X\div 200が答えになることがわかる。こういうのを等差数列と言ったりする。
どちらの方法でも、計算量はO(1)。

B

B - Magic 2
色々な解法がありそうな問題。
最低何回操作すれば条件を満たせるかを求められれば、それをKと比較した結果を返せばよいことになる。ここで、A,B,Cの制約が極端に小さいので、どんな組み合わせの入力が来ても高々10回程度操作すれば条件を満たせそうだということがわかる。（補足：操作するごとに数値は2倍になっていくので、操作回数に対して数値の増加速度がとても速そう、という予想を立てている。）
なので、実際に操作を行って操作回数をカウントするシュミレーションを行う。まずA\lt Bの条件を満たすようにBの数値を増加させて、その後B\lt Cの条件を満たすようにCの数値を増加させる。
計算量はO(\log (\max (A, B, C)))。

C

C - Marks
i学期の評点はA_i \times A_{i-1} \times \dots \times A_{i-K+2} \times A_{i-K+1}で求められる。同様に、(i-1)学期の評定はA_{i-1} \times A_{i-2} \times \dots \times A_{i-K+1} \times A_{i-K}である。純粋にこの値を計算しようとすると、A_i\le 10^9という制約よりオーバーフローしてしまう可能性がある。ここで二つの式を見比べるとA_{i-1} \times \dots \times A_{i-K+1}という部分は重複しているので、大小関係を比べるだけならA_iとA_{i-K}を見るだけで良い。（補足：各学期で行われる期末テストの点数A_iは全て正である。）これをN-K回繰り返せばよい。
計算量はO(N)。

D

D - Road to Millionaire
問題文を理解するのにしばらく時間がかかった。
M君が所持しているのは「金」「株」の2つのパラメータであるが、このうちの「金」の最終的な値をできるだけ多くしたいということ。i日目において、金→株の変換と株→金の変換は同じコストで行えるので、A_iが小さい時に金→株の変換を行い、A_iが大きい時に株→金の変換を行うと所持金が多くなりそうという予想が立つ。この考えをもとに、i日目から見てi\lt jかつA_i\lt A_jなるjがあるなら金→株の変換をできるだけ行い、i\lt jかつA_i\gt A_jなるjがあるなら株→金の変換をできるだけ行うというような貪欲法を思いつく。実際この貪欲法は正しい（詳しい証明は解説PDFがわかりやすい）。
計算量はO(N)。
ちなみにO(N^2)のdpでも解けるが貪欲法の方が直感的でわかりやすいかもしれない。dpに慣れている人なら形式的に落とし込むだけなのでdpの方が楽か。

E

E - M's Solution
解けなかった。
集落の数を表すNが小さいので、全探索解を考える。鉄道を建設するならどれかの集落を通るようなものの方が良いので、「どの集落」を通る「縦・横どちら向きの鉄道」を建設するかを考える。N個の集落それぞれについて、その集落を通る鉄道を建設する・しないをbit列で割り振り、その中でさらに縦・横を選ぶ。そして実際に各集落からの歩行距離を算出してその解を現時点での最小解と比較し、更新する。この解法でO(N2^{2N})の計算量だが、これはおよそ1.6\times 10^{10}となるため間に合わない。困った

F

F - Air Safety
こちらの方が解いた人の数は多いらしい。座標を45度回転させるっていう概念がよくわからない

感想

E問題を解きたかった…。解説PDFにもあるように問題を小さくして考えると上手くいきそう？