こんちゅう

エッセイ・小説・ブログ・楽譜置き場。 不定期更新。

AtCoder ABC 143

解けなかった問題を覚書程度に記す。

ABC143 D

atcoder.jp

解けたけど時間かかった。
a,bを固定してb\le c < a+bなるcの個数を調べればいい。その調べ方について累積和で実装したのだが,二分探索でupper_boundとlower_boundを使えば一瞬だった。実際みんな一瞬で解いてた。

ABC143 E

atcoder.jp

解けたけど(ry
ワーシャルフロイドを2回使えばいい。INFの値をlong longに対応していなくて詰まった。

ABC143 F

atcoder.jp

解けた.....ならよかったんだけどなあ。難しくない?

考え方としてはたぶん典型的なんだと思う。つまり,
・K枚のカードを選ぶときの,操作を行える最大の回数g(K)
と,
・X回の操作を行うときの,選べる最大のカード数f(X)
は問題として等価であることを見抜かないといけない。K,Xの座標軸を用意するとより直感的。この言い換え力がほしい。

さて,X回の操作を行うときの,選べる最大のカード数を調べたい。例えばおかしの詰め合わせをX個作ることを考える。ただしこのお菓子の詰め合わせには,同じおかしを2個以上いれてはいけない。各おかしiC_i個あるとする。このような設定のもと,おかしの詰め合わせには最大何個のおかしを入れることができるか?
各おかしiを,X個まであるだけ徴収する。そのあとお菓子の詰め合わせを作り始める。まずはおかし1をX個の袋にひとつずつ入れていく。おかし1がなくなったら次はおかし2をひとつずつ入れていく。それを繰り返す。各おかしはX個以下なのだから,おかしが同じ袋に入ることはない。よって,
f(X)=\sum_{i=1}^N min(C_i,X) / X
となる。
あとは\sum_{i=1}^N min(C_i,X)を効率的に求められればいい。editionalのように式を変形してもいいし,C_iを昇順にソートしておいて,C_iXの大小の境界をずらしていけば計算できる。

他にもいろんな解法があるみたい。もっと考察すればよかったかも。