babcs2035 https://blog.hatena.ne.jp/babcs2035/ きろく https://babcs2035.hateblo.jp/ 競技プログラミング yukicoder レベル 2.5 問題 問題 解法 解答 問題 yukicoder.me 解法 コインの枚数の境目は最大でも 2 * N 個しかできないので，コインの数字を座標圧縮することを考える．そうすると，空間計算量を O(N) に減らせる．各コインの枚数の区間において，その区間に属するもともとのコインの種類は，座標圧縮時に逆配列を作るなどしておけば O(1) で求まるため，愚直に小さいコインから K 個目までを数えればよい．O(NlogN)． 解答 yukicoder.me 190 <iframe src="https://hatenablog-parts.com/embed?url=https%3A%2F%2Fbabcs2035.hateblo.jp%2Fentry%2F2019%2F04%2F20%2F202530" title="yukicoder：No.817 Coin donation - きろく" class="embed-card embed-blogcard" scrolling="no" frameborder="0" style="display: block; width: 100%; height: 190px; max-width: 500px; margin: 10px 0px;"></iframe> https://cdn-ak.f.st-hatena.com/images/fotolife/b/babcs2035/20190420/20190420202516.png Hatena Blog https://hatena.blog 2019-04-20 20:25:30 rich https://babcs2035.hateblo.jp/entry/2019/04/20/202530 1.0 100%