AtCoder Beginner Contest 209 に参加しました

結果C問題以降が解けず、ランクが下がりました。悲しい。後日、解説を見て勉強しました。

C - Not Equal

全探索しようものなら日が暮れても終わらなさそうなので、組み合わせを計算してO(N)でやればよいなぁ、というところまでは気づいたものの、照準でソートしてやればいいよね。というところは気付きませんでした。
そのままの並びでやるにはどうしたもんか、というのを考えていたので解けず。解説を見て理解しました。ありがとうございました。

とはいえTLE（実行時間制限超過）になるぜ

例えば入力例4の場合に、組み合わせを全部掛け算して最後の答えを 1000000007 で割る、というように素直に計算すると、ものすごく大きい数値になってしまう。これが最大の 200000 の数列になった場合だとそうとう大きな数値になって掛け算だけで相当な時間がかかることが予想されます。

irb(main):001:0> 999999907 * 999999907 * 999999912 * 999999911 * 999999913 * 999999918 * 999999945 * 999999958 * 999999971 * 999999976
=> 999999318000205830963866884077102238770504150918905125322736356669038801918563070769445120

どうしたものか、ということで調べる。どうも問題文にある「答えは非常に大きくなる可能性があるので、1000000007で割った余りを出力してください。」 がポイントのようです。これまで問題になることがなかったですが、ちゃんと調べると意外と奥が深い。こちらの記事が詳しく、参考になりました。

qiita.com

結論から言うと「余りをとるのは最後にやるのではなく、計算の途中でとっても良い」というのがわかりました。かんたんなサンプルコードで動きを確認すると以下のようになる（素数は 1009 にしている）。

mod_result = 1
prime      = 1009 # 1000より大きい最初の素数
arr        = Array.new(10) { (rand * 1000).to_i }
p arr

arr.each do |e|
  puts format "result    : %d", result = result * e
  puts format "mod_result: %d", mod_result = mod_result * e % prime
end

puts format "answer       : %d", result % prime
puts format "answer_result: %d", mod_resul

[822, 451, 961, 994, 291, 159, 387, 641, 929, 636]
result    : 822
mod_result: 822
result    : 370722
mod_result: 419
result    : 356263842
mod_result: 68
result    : 354126258948
mod_result: 998
result    : 103050741353868
mod_result: 835
result    : 16385067875265012
mod_result: 586
result    : 6341021267727559644
mod_result: 766
result    : 4064594632613365731804
mod_result: 632
result    : 3776008413697816764845916
mod_result: 899
result    : 2401541351111811462442002576
mod_result: 670
answer       : 670
answer_result: 670

最終的な結果がおなじになっている。仕組みを理解するかどうかはさておき、プロコンというコンテキストの中では、計算の都度余りを取っていくのが良さそうだ。