199.1

250

一辺の長さがNの正三角形の中に長さ1の正三角形グリッドを描くとき、正三角形は全部でいくつできるかという問題。

単純にカウントするだけの問題。1からNまでの和を求める式を使うとすっきり書けるけれど、世間の人は全部カウントする読めないソース。

500

チップをN人に高々1枚ずつ分けるとき、各人がもらえる確率を答えよという問題。各人がもらえる確率は他の人全員の優先度の合計で自分の優先度を割った値。

もらった人が抜けていくので、誰がどういう順番で抜けた時にどうなるか、というのを計算する。高々10人なので、10!通りのパターンを試して、それぞれにおける確率を合計するのでいいと思う。

あるいは既にもらった人について、その人達の確率を計算しておいて、それが発生した後に抜ける人の確率を計算するというのをやれば良い。これだと2^10通りのパターンを計算すれば良い。前の人の順番については考える必要がないということ。

1000

150000点の3次元の点について、一番距離の近い二点間の距離の二乗と、そうなるペアの総数を答えよという問題。

分割統治するといいらしい。取り敢えず真ん中付近で二つに分けて、それぞれの中を計算する。それぞれの中での距離のうち、一番小さいものより近い可能性があるのは、境界からの距離がそれよりも離れていないものなので、その範囲にあるものすべてについて距離を計算する。