アジア太平洋情報オリンピック(APIO)2010 China
概要
アジア太平洋地域の国々でこっそり開催しているマイナーコンテスト。IOIの形式に則る。今年は5時間3問。
その存在感のなさの割に非常に難しいのが特徴。
1. Commando
0から100のn個の整数列が与えられて、これをいくつかの区間に分割する。各区間の和を二次多項式ax^2+bx+c(-5<=a<0)に代入した結果の合計値を最大化せよ。
O(n^2)程度だと50点、O(n)程度だと100点。
自分の解法
0番目からi番目の部分列における上記の値の最大値のDP。
漸化式は、dp[i]=max(dp[j]+a*value_sum(j..i)^2+b*value_sum(j..i)+c for all j)
(境界条件の表記は適当)
愚直に実装するとO(n^2)になる。
ちなみにintだと溢れるので注意
2. Patrol
n頂点のグラフがあり、最初は木である。このグラフの各辺を1回以上通る閉路で、辺を通る回数が最小のものを考える。
初期状態では辺の数の2倍のコストがかかる。
このとき、グラフの任意の相異なるとは限らない2点間を結ぶ近道をK個(K=1,2)つくる。この近道はちょうど1回ずつ通る必要がある。
辺を通る回数の最小値を求めよ。
O(n^2)だと10点、O(n)でK=1の場合だけだと30点、O(n)だと100点。
自分の解法
初期状態では全ての点が偶点であるため、全ての近道でない辺が偶辺である。
近道はその両端だけを考え、最後に近道を通る1回のコストを加算すればよい。
近道の両端点は偶奇が反転する。それにしたがい偶辺が奇辺になる。偶辺は2回、奇辺は1回通るのが必要十分条件であることが確認できる。
奇辺の集合は互いに交差しないような奇点どうしを結ぶ経路の和集合である。奇点は2K個なのでその経路はK個である。
これら奇辺の集合を最大にしたい。
K=1の場合、木の直径であることがすぐにわかる。これを拡張して考えればよい。
木DPを使うが、子ノードをx、親ノードをpとおくと
dp2[p] := max(dp2[p],dp1[p]+dp1[x]+1,dp2[x]) dp1[p] := max(dp1[p],dp1[x]+1)
のようにDPを行うと、dp2[root]が直径を保持する。(dp1[x],dp2[x]の初期値は0)
これを拡張して以下のようにすればよい。
dp4[p] := max(dp4[p],dp3[p]+dp1[x]+1,dp2[p]+dp2[x],dp1[p]+dp3[x]+1,dp4[x]) dp3[p] := max(dp3[p],dp2[p]+dp1[x]+1,dp1[p]+dp2[x],dp3[x]+1) dp2[p] := max(dp2[p],dp1[p]+dp1[x]+1,dp2[x]) dp1[p] := max(dp1[p],dp1[x]+1)
K=1のときdp2[root]、K=2のときdp4[root]を参照すればよい。
3. Signaling
平面上にn個の点(整数座標)がある。どの3点も同一直線上でなく、どの4点も同一円周上ではない。 3つの点の選び方はnC3通りあるが、3つの点を選んだとき、それらの外接円に含まれる点の数(円周上の点も含む)をnC3通り全てについて考えたときの平均値を答えよ。 n≦100(O(n^4)とかO(n^3logn))のとき40点。n≦500のとき70点。n≦1500(O(n^2))のとき100点。
自分の解法
ある2点A,Bを決めたとき、残りについて走査をかけると一括して求められる。
具体的には、有向角AXBのcotangentは内積/外積(ここでは外積≠0よりcotangentを使う)なので、これでソートをする。
ABのどちら側にあるかに応じて1を加算または減算しながら走査。
これで求める。
