解けなかった問題を覚書程度に記す。
ABC143 D
解けたけど時間かかった。
を固定してなるの個数を調べればいい。その調べ方について累積和で実装したのだが,二分探索でupper_boundとlower_boundを使えば一瞬だった。実際みんな一瞬で解いてた。
ABC143 F
解けた.....ならよかったんだけどなあ。難しくない?
考え方としてはたぶん典型的なんだと思う。つまり,
・K枚のカードを選ぶときの,操作を行える最大の回数
と,
・X回の操作を行うときの,選べる最大のカード数
は問題として等価であることを見抜かないといけない。K,Xの座標軸を用意するとより直感的。この言い換え力がほしい。
さて,X回の操作を行うときの,選べる最大のカード数を調べたい。例えばおかしの詰め合わせを個作ることを考える。ただしこのお菓子の詰め合わせには,同じおかしを2個以上いれてはいけない。各おかしは個あるとする。このような設定のもと,おかしの詰め合わせには最大何個のおかしを入れることができるか?
各おかしを,個まであるだけ徴収する。そのあとお菓子の詰め合わせを作り始める。まずはおかし1を個の袋にひとつずつ入れていく。おかし1がなくなったら次はおかし2をひとつずつ入れていく。それを繰り返す。各おかしは個以下なのだから,おかしが同じ袋に入ることはない。よって,
となる。
あとはを効率的に求められればいい。editionalのように式を変形してもいいし,を昇順にソートしておいて,との大小の境界をずらしていけば計算できる。
他にもいろんな解法があるみたい。もっと考察すればよかったかも。