APIO2010
2010年5月8日(土)にAPIO(アジア太平洋情報オリンピック)という大会がありました。
3問/5時間。
問題とか結果とかは http://www.apio2010.org/apioweb/index.jsp から。
結果：死 ん だ ＼ ( ^ o ^ ) ／
Q1 Commando
sum(i,j) = x_i + x_{i+1} + ... + x_{j}
f(x) = a*x*x + b*x + c
とすると、
dp[i] = max(f(sum(0,i)), dp[0]+f(sum(1,i)), dp[1]+f(sum(2,i)), ..., dp[i-1]+f(sum(i,i))))
でO(n^2)で求まる。
intでは足りない事にも注意した。
…はずだった。
配点の50%がn≦10000なので取れると思ったが、なぜか20%しか取れなかった。謎。
Q2 Patrol
k=1の時は木の直径になることは気づいたが、何故かノード1を通る直径を求めるプログラムを書いてしまっていた。
k=2の時は混乱した。
落ち着けば30点貰えたのに16点だった。かなしい。
Q3 Signaling
- 1点を決める
- その点を原点とした偏角を他の各点について計算し、その順にソート
- 他の各点について、最初に決めた1点とそれを通る直線の上側と下側に来る点の数(それぞれn_0, n_1とする)を二分探索で求める
- sumにn_0*(n_0+1)/2+2*n_0+n_1*(n_1+1)/2+2*n_1を足す
- 最初に決める1点をすべてについて行い、最後にsumをn(n-1)(n-2)で割って終わり
という見事に違うアルゴリズムを開発し0点でした。
n≦100のケースが40点だったから普通に全探索書けば良かった。
Result
20/16/0 合計:36
【参考】
- メダリストボーダー：83点
- 日本代表(6名)ボーダー：117点
最初から部分点狙っていれば50+30+40=120でメダル圏内だったから非常に口惜しいけど、
この程度の実力だと言うことを身をもって知ることが出来たので良い経験になったと思います。
// commandoが50でないのは諦めがつかないけど……。
あぁ、そうそう、メダルを手に入れたid:semiexp、id:qnighy、id:JAPLJ、huziwara、utatakiyoshi、灘の人はおめでとう御座いました。
内4名は日本代表ですね。IOI頑張ってきて下さい。
夏のJOIセミナーはSuperconと被るらしいので参加できそうにないから、自分が情オリと関わるのはこれで最後になりそう。
今までありがとうございました。
