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を目指すとします。その間に通る料金所はとなる全てのの数に等しいです。
逆にマスNを目指すなら、先ほど通らなかった料金所全部のみを通るでしょう。
なので、その二つの料金所の数のうち少ない方がコストの最小値になります。
C - Many Medians
まず、Xをソートした配列としてAを定義します。
そして全ての中央値を求めると、それはとの二つの平均値になります。
ここで、取り除くがならば中央値がになることが、そうでないならになることが分かります。
よって各iについてO(1)で計算することができますね。
D - Binomial Coefficients
変数が複数ある時は1個を除き固定して考えます。
を固定すると、どう考えてもが大きければ大きいほど値が大きくなるので、まず最初の数はであることが分かります。
その時、Combinationの関係上2番目の数はなるべくに近いものを選ぶべきです。
よって、O(n)で解けることが分かります。
結果
ooxx 2完(700点) 15:47(0WA)
267位 パフォーマンス: 1849
レート: 1796 → 1801(+5) highest!
感想
E問題の700点、考察ミスで落としたのは痛かったです。
最初のRE連打も時間を減らし痛手になりました。
強実装する時はもう少し軽量化できないか考えるべきでしたね……少なくとも入れ替え処理はバカげています。
今回、D問題までは考察のし甲斐が無い問題でしたので簡単だったとは思いますが、もし解けなかった場合は解説見たうえでもう一度やり直してみてください。これは簡単な方なので見直せば簡単に解けるはずです。
では、また次回もよろしくお願いします。