JOI春
問題一覧 - 情報オリンピック 問題と解説
2012年 日本情報オリンピック春合宿OJ - 2012年 日本情報オリンピック春合宿OJ | AtCoder
2013年 日本情報オリンピック春合宿 1日目 - 2013年 日本情報オリンピック春合宿 1日目 | AtCoder
2014年 日本情報オリンピック春合宿 オンラインジャッジ - 2014年 日本情報オリンピック春合宿 オンラインジャッジ | AtCoder
(2013だけURLが違う)
やります
2012
building2
データ構造をマージする一般的なテク.今となっては典型.マージテクで参照してる場所 をちゃんと持たないとバグります.
fish
まず2倍がどうこう、というのを見てmaximalな区間たちに落とす、次に高次元なので時間軸として一次元処理する、のこりの二次元の面積を求められればいいので、これは階段状の点を持って処理する. P(inf,0)とP(0,inf)を始めに入れとくと楽.
joi_flag
動的segtreeみたいに、非自明な計算が必要なとこだけ計算する.
broadcasting
output only 知らない. こういうのは各outputをvisualizeしてから考えるといいらしい.Kruskalとか,中心集合を適当に取る→貪欲→それらの中心を取る を繰り返すとかかなあ.
constellation
まず適当な例を考えると、どう考えてもDPの状態として持ちようがないつなぎ方をするしかないような例が作れて、まあだから実は簡単な条件で書けるんだろうという察しがつく. 凸包上でoxoxみたいになってたらアウトだなあ→それ以外ならできそう
rotate
とりあえず一次元でreverseだと面倒なクエリごとにlogNの平衡二分木があるけど、そんな感じのが想定解だったらΩ＼ζ°)ﾁｰﾝなので,各クエリでO(N^2)よりましなものを考える.縦横がどれにつながってるかだけなら境界のO(N)だけ変えればいいので出来そうという気持ちになる.実際どこにいるかを取得するのが難しい気がしたのでまずはじめに考えたのがクエリ平方分割で、各クエリブロックごとに、「いまXにいるのは誰ですか?をクエリの逆演算をして求める」というのをやった、これをするとO(NQsqrt(N))とかになるんですけど定数倍がかなり重いのでTLEした. 冷静に考えると、つながり方はcyclicな向きを保って持てるので、端っこから調べるとO(N)で境界を見つけられる.全体でO(NQ).
TLEだったけどクエリ平方分割をあまり実装したことがないので練習になった(結局「答えを求める」をB回やって、各ブロックではクエリiにクエリj(<i)が影響を及ぼす というのを全ペアに対して考慮してもO(sqrt(Q)^2)で大丈夫、というのが重要.いやそれはそう.
プログラミングコンテストでのデータ構造 2 ～平衡二分探索木編～に書いてあるように、もとからreverseしたものを複製しておいてswap(つなぎかえる) というのが便利.
fortune_telling
典型遅延評価segtree
kangaroo
数え上げ,簡単だけど面白い(575)
集合から候補を選んで取っていく形で、集合が単調に出来る場合(この例だと,Cand_i = {j|Aj < Bi})はその集合が小さい順に考えると個数しか持たなくていい、っていう一般的なテク.
今回は、操作ができるまで繰り返す という条件を考えると、「最後にbに何も入れなかった時の残り」が何個今残ってるか というのを持てばいいことがわかる. 区間として考えたほうが良かったかもしれない.
sokoban
面倒 of 面倒 二重辺連結成分だとわかりやすく木に分解できるが、二重頂点でも同様のことが出来る.
chinese
自明 実はsetだけでいける
