Google Code Jam - tattyu's blog

クオリファイをすっぽかしたので、参加できずorz

それでもLuaでテストだけしてみた。
Smallな入力なら普通に終わるんだけど、Largeだとまずテスト時間内に計算が終わらないので工夫する。
が、テーブルのインデクスを間違えてて微妙に結果が違うのではまる。

さらに自身満々でLargeに挑むもLuaの計算精度のせいで(Luaはラージナンバー扱えない）もちろんIncorrect。

あたまにきたのでRubyで書いたらあっさり通った。ちょっと嬉しい。
が、クリアしても次のラウンドに行ける訳でもないので自己満足。終わり。

問題文の先頭の方にディスカバリーチャンネルとか余計な説明文があるせいで混乱するけど、
入力された値で頂点を生成し、頂点の組み合わせだけ三角形を生成。で重心が整数になってる三角形はいくつかって問題。
英文だと読み解くだけで時間かかるからやーね。

力任せに解けば、

頂点生成

for v1=0,頂点数-2 
 for v2=v1-1,頂点数-1 
  for v3=v2-1,頂点数 
    三角形の重心が整数か調べる
  end
 end
end

でおｋだけど、Largeは入力が100000とかあるので計算時間がとんでもないことになる。

考えた方法は、
3x3のmod空間に頂点を配置しなおしてそれぞれ個数をカウント。
重心が整数になる組み合わせで2重ループして組み合わせ数を求めた総和で出すようにしたら上手くいった。
下らないバグのせいで3時間以上かかったorz。

こんな問題郡を2時間以内に満点出してる奴は本当の天才かチーターマンのどっちかだな。