2019-04-20 yukicoder：No.817 Coin donation 競技プログラミング yukicoder レベル 2.5 問題 問題 解法 解答 問題 yukicoder.me 解法 コインの枚数の境目は最大でも 2 * N 個しかできないので，コインの数字を座標圧縮することを考える．そうすると，空間計算量を O(N) に減らせる．各コインの枚数の区間において，その区間に属するもともとのコインの種類は，座標圧縮時に逆配列を作るなどしておけば O(1) で求まるため，愚直に小さいコインから K 個目までを数えればよい．O(NlogN)． 解答 yukicoder.me
