解けそうなやつ解いてみました。
2017 5番
N+1要素以上の単調増加列を使って構成する方法をまず考えましたが、うまく行かず。
そのときに数の区間で考える発想が浮かんだので、1-N+1,N+2-2(N+1),...,(N-1)(N+1)+1-N(N-1)のN個に分割してみました。
そうすると数の大小を考えずに区間が同じやつが隣同士になれば良いという条件になるので考えやすくなりました。
ここまでくれば後は楽勝です。先頭からN+1個見れば鳩の巣原理から区間が同じペアが存在します。その区間の全ての数、ペアよりも前に存在した数を全部消すと、残りの数列の長さLはL>=N(N+1)-2N=N(N-1)となります。N-1の場合に帰着できたので帰納法で解けました。
やっぱり対称性の高くしてあげるとうまくいく場合が多いですね。こういう感覚身につけたい。
2015 6番
k+ak≠l+alが意味不明なので言い換えます。すると、
1 <= bk <= 2015を満たす長さmの数列があって、次の操作を繰り返すことと同じになります。
1.bkのうち１つ選んでこれを数列aに追加する。
2.他の要素について全て-1する。
3.bに2015を追加する。
です。m <= 2015であり、mは単調増加なので、あるmで固定して考えます。
(bの長さ)=mとなったところからaに追加された要素の合計をS,Σbk=S'とします。
すると(S+S')next=(S+S')current+(2016-m)となることがわかります。なので問題文のbを2016-mとしてあげて、
Σbk-b=S''とすれば(S+S'')=constとなります。最初はS=0なのでconstはS''に依存します。
あとbは上の操作から作られることを考えると、(m-1)(3m-4030)/2<=S''<=(m-1)m/2が成立するので、
constも同じ条件が成立します。S=S''-constなので|S| <= (m-1)m/2-(3m-4030)(m-1)/2=(m-1)(2015-m)となります。
(m-1)(2015-m)はm=1008で最大で1007^2となるので示せました。
これもmが本質になることを感じ取って、mを中心に議論を展開すれば解ける問題でした。
