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

kangaroo

数え上げ,簡単だけど面白い(575)
集合から候補を選んで取っていく形で、集合が単調に出来る場合(この例だと,Cand_i = {j|Aj < Bi})はその集合が小さい順に考えると個数しか持たなくていい、っていう一般的なテク.
今回は、操作ができるまで繰り返す という条件を考えると、「最後にbに何も入れなかった時の残り」が何個今残ってるか というのを持てばいいことがわかる. 区間として考えたほうが良かったかもしれない.

sokoban

chinese

copypaste

invitation