競プロ小説

「競技プログラミングやろう！」
「なに？」
「競技プログラミング」
「プログラミングの勉強をしたいってこと？」
「それもあるけど、競技プログラミングはゲームだから」
「そうなんだ」
「そうだよ。……テンション低いな？」
「いや、何ヶ月か前にお前が似たようなことを言って俺にスプラ3を買わせた時のことを思い出しただけだよ。俺はでんせつになったけど、お前の最終ログインいつ？とか思ってないから安心してくれ」
「その節はどうも。今回はなんと初期投資0円で始められるから頼む」
「いいけどさ。それで、プログラミングするの？」
「そう。毎週土曜の21時にコンテストが開かれて、100分間の制限時間で解いた問題に応じてレーティングが増減する。目指せ、トップランカー！　……というゲーム」
「対人ゲームではないってことか」
「PvPではないね。全員に共通の問題が出されて、多く解いた人が上位」
「要するに学校でやってるテストで競う感じ？」
「そうそう。お前そういうの好きだろ、いつも上の方にいるじゃん」
「別に好きというわけでもないが……。それで、どんな問題が出るわけ？　兵庫県警を呼べるプログラムを作るとか？」
「兵庫県警？」
「いや、知らないならいい。話を進めてくれ」
「おーけー。出る問題は、簡単にいったら数学だな。具体的には……、っと、お前ってプログラミングできるんだっけ？」
「できるよ」
「マジ？」
「マジマジ。見てろよ」

>>> def plus(a, b): return a + b
>>> plus(1, 2)
3

「ほんとにできるんだ。知らなかった……」
「電卓の代わりに使ってるくらいだけどな。それで、話の続きは？」
「あーはいはい。いや、話が早くて助かるね。一番初心者向けの問題が『整数A,Bが与えられるのでA+Bを出力してください』なんだよね」
「いま作ったな。言語は何でもいいのか？」
「うん。ほんとは入出力もしないといけないんだけど、お前が実はすでにプログラミングをできることがわかったからその辺の話は省略する。知らなかったらあとでググってくれ」
「わかった。で、これを大量に解いたら勝ち？　タイピング大会じゃん」
「まあこれは一番簡単な問題だからね。もうちょっと難しい問題だとこういうのがある。『何個かの正整数が与えられます。ここから和が偶数になるように2つ選ぶとき、和の最大値は？』」
「偶数が作れないときは？」
「じゃあとりあえずそういうケースはないものとして解いてくれ」
「わかった。別にそんなに難しいとは思わないけどな」

def f(array):
  n = len(array)
  ans = 0
  for i in range(n):
    for j in range(i+1, n):
      if (array[i] + array[j]) % 2 == 0:
        ans = max(ans, array[i] + array[j])
  return ans

「うーん、この言語は知らないけど、雰囲気的に合ってそう。いやー、やっぱお前賢いから話がスムーズに進むな」
「もっと褒めてくれていいぞ」
「うんうん、想定した通りの誤解法を書いてくれてありがとう」
「は？」
「いやいや、これは俺が説明してない要素だからお前は悪くない」
「わざわざこのコードを書いた俺の労力を返せ」
「まあまあ。実は、提出するプログラムには実行時間に制限がある。大抵の問題は2秒だ」
「こんなシンプルな処理で2秒も掛かることなくない？」
「じゃあ試してみよう。実行時間ってどうやって測れるか知ってる？」
「知らないけど、2秒以上かどうか判定するだけなら見てれば十分だろ」
「たしかに。それじゃあ、適当に作った長さ1万の配列を渡してみて」
「全部1でもいいか？」
「いいよ」

>>> f([1] * 10000)
2

「5秒くらいかかってるな」
「そう。これをどうにか2秒以内におさめてください」
「うーん……。ソートして枝刈りすれば良さそう」
「なに？？」

def f(array):
  n = len(array)
  array.sort()
  array.reverse()
  ans = 0
  for i in range(n):
    for j in range(i+1, n):
      if array[i] + array[j] <= ans:
        break
      if (array[i] + array[j]) % 2 == 0:
        ans = max(ans, array[i] + array[j])
  return ans

>>> f([1]*10000)
2

「一瞬になったな。これで正解か？」
「えっ、どうなんだろう？」
「なんで出題者がわからないんだよ」
「用意してる答えと違うことされたから……」
「実際にはどうやって正誤判定してるんだ？」
「出題者が何十個か入力のバリエーションを先に用意しておいて、それに全部正解したら正解」
「じゃあ今からお前が作れ」
「えー」

問題：作中で提示されたコードが十分高速に動作するか判定せよ。