情報オリンピック2010本選 感想と解説
し ん だ＼(^o^)／
概要
常連がみんな死んだなどと言っている。むごい。
いくら凄い人々ばかりだったとはいえ、去年満点を3人だしてしまったので、今回は満点阻止レベルの問題構成になると予想したら、やっぱりそうなった。
ちなみに自分は3完。いろいろとヤバい。
自分はDPの発見は得意になったけど、数理的な特徴の発見とかができなくて死ぬ。
あと部分点がとれないのが厄介。
1旅人
旅人が右往左往東奔西走するので、その合計距離を求める問題。
宿場町1から宿場町Xまでの距離を先に計算しておけばO(n)でできるので完答。さもなければO(n^2)で50%。
自分は何を血迷ったかBITを作ってしまったのでO(nlogn)だけどn=100000なのでおそらく完答。
2おかし
几帳面な二人がお菓子を半分こするお話。
「iミリ地点でjミリをAさんが取っていて、かつkさんが右端を取っている場合」についてDPすればよくてO(n^2)で完答。
上記DPより遅いDPを組むとO(n^3)以上になって50%。
切断箇所の組合せを列挙するとO(n^n)であるが、3箇所に限定してO(n^3)を効率化できると10%。2箇所に限定してO(n^2)を書けると5%。
自分はおそらく完答。
追記:DPについて
二次元配列を用意する。
二次元配列のi番目のj番目には、「左端からiミリまでのお菓子だけ手元にあったとして、そのうちjミリ分をAさんに、i-jミリ分をBさんに配分するのにかかる最小の時間」をいれる。
ただし、右端1ミリをAさんに分配する場合とBさんに分配する場合は区別する。(僕のソースではfirstとsecondに格納している。)
区別することで「左端からiミリまでのお菓子だけ手元にある場合」から「左端からi+1ミリまでのお菓子だけ手元にある場合」を計算できるからである。
左端からiミリまでが既に分配されていたとする。
次の1ミリを、直前の1ミリと同じ人に分配する場合、「くっつける」ことができる。というより、元々そのお菓子はくっついていたのだ。
ところが、次の1ミリを、直前の1ミリと逆の人に分配する場合、その間は切断しなければならないので、さらに時間がかかる。
だから、次の1ミリをBさんに分配するには、「直前の1ミリがAさんに分配されていて、次を切る」場合と「直前の1ミリはBさんに分配されているので、ここは切らなくていい」場合のうち、短くすむほうを選べばよい。
これを行っているのは僕のソースでは以下の部分である。
dp1[j].first = MY_MAX; dp1[j].second = min(dp0[j].first+cut_cost[i], dp0[j].second); if(j>0) { dp1[j].first = min(dp0[j-1].first, dp0[j-1].second+cut_cost[i]); }
これは左端処理があるので、簡略化すると次のようになる。
dp1[j].first = min(dp0[j-1].first, dp0[j-1].second+cut_cost[i]); dp1[j].second = min(dp0[j].first+cut_cost[i], dp0[j].second);
これが前述のDPを実現している。
最後に、実際に二次元配列で確保してはいけない。(メモリが足りない)
実際は直前だけが必要(i+1の計算にはiだけが必要)なので、中身を入れ替えながら処理していけばよい。
3つらら
両端より長いつららだけ成長するが、ある程度の長さでポッキリ逝く。
単純な方法だとO(nl)っぽなので30%。
極大なつらら→極小なつららが折れる、までの時間のうち最小をとればよい。(追記:これでO(n))
自分はpriority_queueを使ってシミュレートしO(nlogn)。またはsortを使う手もある。O(nlogn)でも通る。
4博覧会
平面上の点集合を2つに分類し、同じ点集合内での2点間のマンハッタン距離の最大値を最小化する。
Kruskalの要領で、UnionFindに色を付けてオンライン2部グラフ判定を構成して、最も長い辺から処理をすれば答えが得られるが、辺の列挙のメモリコストがO(n^2logn)で30%。僕はさらにこれをpriority_queueなどを駆使して低速に列挙するアルゴリズムを発明してしまい死んだ。
以下のように考える。
マンハッタン距離|x2-x1|+|y2-y1|を場合わけして考えると、|x2-x1|+|y2-y1|=max(|(x1+y1)-(x2+y2)|,|(x1-y1)-(x2-y2)|)
ここで、|(x1+y1)-(x2+y2)|を正のマンハッタン距離、|(x1-y1)-(x2-y2)|を負のマンハッタン距離とおくと
全点間のマンハッタン距離がd以下⇔全点間の正のマンハッタン距離がd以下で全点間の負のマンハッタン距離もd以下
⇔(x+y)の最大値と最小値の差と(x-y)の最大値と最小値の差がどちらもd以下
ここで、(x+y)の最大値と(x-y)の最大値を同じ集合にいれるか、または、(x+y)の最小値と(x-y)の最大値を同じ集合にいれるかのどちらかを選択することになる。
どちらの場合も、全ての点について、近いほうの集合に入れればよい(点について集合Aと集合Bのどちらが近いかminをとり、さらに点全体について単にmaxをとればよい)
で、2つの場合を考えたのでこのうち小さいほうをとればよい。
5ダンジョン
風来するお話。財宝がエクスカリバーだったら本気だしてたのにと言っていた人がいた。
DPによる解法はO(nh)で10%、単純な貪欲法だとO(n^2)で30%。dequeを使って改善すると10^6で50%。さらに除算を導入すると完答。
あとで説明かく。
自分は解かなかった。これを解けたのはおそらくsemiexpだけなので、優勝おめでとうございます。
反省(後悔でない)
ファイト
