第17回日本情報オリンピック　予選６

2017年12月11日
情報オリンピック日本委員会

解説

まず，問題文の処理をそのまま行うことを考える．このとき，長さK以上の連続するカードの列の数は高々N(N-1)/2，長さは高々O(N)なので，それぞれをソートしても計算量はO(N^3logN)である．K番目の数を書きだした列の長さも高々N(N-1)/2なので，これをソートしてL番目を求めることはO(N^2logN)で済む．この解法により，6点を獲得することができる．

次に，O(N^2)で解くことを考えよう．左端を固定し，長さをKから1ずつ増やしつつ，K番目の数を保持してみよう．K番目の数は，長さを増やすに伴い単調に減少するため，1からnの整数が列に何回含まれているかという配列を保持し，x以下の数がK以上含まれるような最小のxを更新することで，合計O(N^2)で書きだされる数を求めることができる．実際に書き出された列を作るのではなく，1からnの整数が何回書かれたかという配列を作ることで，L番目の数をソートすることなく求めることができる．この解法により，さらに33点を獲得することができる．

最後に，O(NlogN)で解くことを考えよう．L番目に小さい数とは，x以下の数がL以上あるような最小の数xである．「x以下の数」はxが増加すると単調に増加するので，書きだされた数の中でx以下の数がいくつあるか求めることができれば，xについて二分探索を用い，x以下の数がL以上となる最小のxを求めることができる．

それでは，xが与えられたとき書きだされた数の中でx以下の数がいくつあるかを求めてみよう．33点の解法で述べたとおり，左端lから右端rの中でのK番目の数がx以下のとき，右端を伸ばしてもK番目の数はx以下のままである．すなわち，ある左端lについてK番目の数がx以下になる最小のrを求めることで，ある左端lについてはx以下が(N+1-r)回書かれることが分かる．

さらに，lに対するK番目の数がx以下になる最小のrは，lの増加について単調に増加する．これより，左端lと右端rについてしゃくとり法の要領で動かすことで，合計O(N)でx以下の数が何回書かれるか求めることができる．