yukicoder contest 338

　Dまで四完。Eが間に合わず終了。

コンテストへのリンク

No.1897 Sum of 2nd Max

　自力AC。コンテスト中も正しい方針を考えていたのだけど、詰め切れなかった。

　NとKの制約が両方$2*10^5$以下なので、どちらかしか全探索できないが、要素の総和を求める、ということなので、「あるxが大きい方から2番目になるような数列の個数」を考えた方が良さそう。

　その際、

・xより大きいものが一個、それ以外はx以下

・全てx以下

　の二通りに分け、前者からは「xが含まれない場合」を除く。後者からは「xが一個も含まれない場合」および「xが一個だけ含まれる場合」を除くと考えると計算できる。