Lilliput Steps

小さな一歩から着実に. 数学やプログラミングのことを書きます.

IOI

IOI 2008 Day2 - Linear Garden

問題文 : 直線状の庭園 (pdf 注意)

IOI 2005-day1 Mountains

問題文 : 山の遊園地問題概要 (問題文読みづらいので) : 長さ N の数列が与えられる. 次のクエリに答えよ. 区間 [l, r] の値を v に更新する. [I l r v] [1, x] の値がはじめてv を越えるようなx を求める. [Q v] 解法 :遅延評価をするセグメント木を用いる.…

IOI 2008-day1 Type Printer

問題文 : 活字印刷機解法 : Trie 木上の探索を行う. 最も長い文字を最後にたどれば, その文字の文の型を回収しなくていいため最短ですべての文字を打ち終えることが出来る. (他の文字はどのみち回収しないといけないため). コード : #include <cstdio> #include <cstdlib> #in</cstdlib></cstdio>…

IOI 2010-day1 Quality of Living

問題文 : 住み心地解法 : もし, ランク X がある区画Aの住み心地の中央値になれば, ランクX + 1 が他のどの地点にあったとしても, 区画A での中央値はX となる. そこで, ランクについて二分探索を行い, 中央値になりうるかを確かめる. ランクの地点が影響を…

IOI 2005-day1 Garden

問題文 : 庭園解法 : O(n^3) で長方形列挙を行い, 上下左右から周長の最大値を記録してやれば良い. 長方形列挙は, y 軸の2 点はO(H^2) で決め打ち, x 軸については尺取り法でO(W) で求めれば良い.計算量はO(WH^2) だが, 制限時間ギリギリなので結構大変.コー…

IOI 2005-day1 Mean Sequence

問題文 : 平均数列解法 : 数列の初項を決めると, 残りの数列の値も一意に定まる. 更に, 初項k の平均数列が作れなければ, 初項をk + 1 とする平均数列(またはk - 1 とする平均数列, あるいは両方) が作れないことが分かる. ゆえに, この数列の初項の値は連続…

IOI 2011-day2 Crocodile's Underground City

問題文 : ワニの地下都市(pdf注意)解法 : 出口につけばすぐに出ることが出来るので, 出口のノードのコストは0にしておく.そうでないすべてのノードについて, "出口までたどり着ける最短時間" "出口までたどり着ける2 番目の最短時間"を状態としてdijkstra を…

IOI 2011-day1 Rice Hub

問題文 : 米集積場 (pdf注意)解法 : C(x) : Bバーツ以内でx個の水田から米を届けられるか, とすると, C(A)が成り立つ時, C(A - 1)も成立する. よって, xについて二分探索を行う.このとき, 集める水田が連続していたほうがいいことは明らかなので, R - x個の,…