POJ Founder Monthly Contest 2008.12.28.

はじめてのPOJMonthlyでした。

A

たぶん連立方程式を解くだけ。なので解けない
[opened]

B

D進法表記したとき各桁が周期的に変わっていくので、あとはがんばる
[accepted at 02:57:59 / 7 wrong tries]

C

点を動かしてk点以上重なるようにするために移動する最短距離を求める問題
たぶん今回の最難問題。AC少ないのでちゃんと考えてない
[opened]

D

木におまけがついたものをばさばさ切ってくゲーム
Grundy数をがんばって求める問題？
[opened]

E

三角形ABCに対して、d(Q,BC)^2 + d(Q,CA)^2 + d(Q,AB)^2 が最小になる点Qを見つける
最初内心だと思ったが嘘すぎ。その次に山登りしたら通らなくて焦った
x = d(Q,BC), y = d(Q,CA), z = d(Q,AB) とおくと xBC + yCA + zAB = 2S で、これを平面とみて原点との距離(の2乗)を求める感じ
x,y,z求めたあとは適当に。ABCが負の向きで与えられる場合に注意
[accepted at 01:11:35 / 9 wrong tries]

F

頂点数nのグラフでk-マッチングが存在しないようなものの最大辺数を求める問題

• n<2kのときは完全グラフ
• n>=2kのときは(2k-1)点だけ完全グラフにするか、(k-1)点と(n-k+1)点の2部完全グラフ

とやってみたら通った。証明は謎
[accepted at 03:26:17]

G

任意の2頂点間に3本以上の点素パスがあるかどうか調べる問題
頂点数2倍にしてフローを流せばO(N^4M)が得られるがもちろんTLE
よくわからない
[3 wrong tries]

H

N点の集合が2つあって、それらの間での最短距離を求める問題
普通にLineSweepするだけ。N<=100000だがstd::set使っても間に合った
xとyを書き間違えていたとかでWAを出してて悲しい
[accepted at 04:11:48 / 3 wrong tries]

Result

4完最下位(18:07:39)の10位。
4完はまあよかったとして、もう少し落ち着いてcodingするべきだと実感。