情報妖精の競プロ日記

AtCoderの問題に対する方針を主に書きます

AtCoder Regular Contest 095

AtCoder Regular Contest 095に参加しました!
ABC094 旧版:
abc094.contest.atcoder.jp
ABC094 beta:
https://beta.atcoder.jp/contests/abc094/beta.atcoder.jp
ARC095 旧版:
arc095.contest.atcoder.jp
ARC095 beta:
https://beta.atcoder.jp/contests/arc095/beta.atcoder.jp

解けた問題だけ解説をしていきますー

要項

AtCoder Beginner Contest 094 / Regular Contest 095
rated 1200 / 2800
4/14(土) 21:10 ~ 22:50 (100分)
100-200-300-400-700-900 (6問)
ペナルティ: 5分

方針

C,D問題を解き、なるべくE問題も解いていきたい。
前回が700解けたし大丈夫なはず……

A - Cats and Dogs

要するに、猫の数はA匹以上A+B匹以下なので、この範囲の間にXが入るかを判定すれば大丈夫ですね。
A≦XかつX≦A+Bならば大丈夫です。

B - Toll Gates

まず、マス0を目指すとします。その間に通る料金所は A_i < Xとなる全ての A_iの数に等しいです。
逆にマスNを目指すなら、先ほど通らなかった料金所全部のみを通るでしょう。
なので、その二つの料金所の数のうち少ない方がコストの最小値になります。

C - Many Medians

まず、Xをソートした配列としてAを定義します。
そして全ての中央値を求めると、それは A_{N/2} A_{N/2+1}の二つの平均値になります。
ここで、取り除く X_i X_i <= A_{N/2}ならば中央値が A_{N/2+1}になることが、そうでないなら A_{N/2}になることが分かります。
よって各iについてO(1)で計算することができますね。

D - Binomial Coefficients

変数が複数ある時は1個を除き固定して考えます。
 a_jを固定すると、どう考えても a_iが大きければ大きいほど値が大きくなるので、まず最初の数は max(a_i)であることが分かります。
その時、Combinationの関係上2番目の数はなるべく max(a_i) / 2に近いものを選ぶべきです。
よって、O(n)で解けることが分かります。

結果

ooxx 2完(700点) 15:47(0WA)
267位 パフォーマンス: 1849
レート: 1796 → 1801(+5) highest!

感想

E問題の700点、考察ミスで落としたのは痛かったです。
最初のRE連打も時間を減らし痛手になりました。
強実装する時はもう少し軽量化できないか考えるべきでしたね……少なくとも入れ替え処理はバカげています。
今回、D問題までは考察のし甲斐が無い問題でしたので簡単だったとは思いますが、もし解けなかった場合は解説見たうえでもう一度やり直してみてください。これは簡単な方なので見直せば簡単に解けるはずです。
では、また次回もよろしくお願いします。