[JOI合宿]2010-Day1:JOI Poster

オフラインでAC確認済み.
書かれているとおりにポスターを構築していきます.

続きを読む

[JOI合宿]2008-Day4:Typhoon

とりあえず、ローカルで全てのテストケースに対して正解を確認したので載せます.

セグメント木の問題. 他にも色々知識を使えたので、スキルアップになりました！

まず、問題中に出てくる全ての地点を用いて座標圧縮をします.
次に, すべての台風を2回ずつ襲撃させます. １回目では、クエリ(p, q, r)に対して, 1 ~ q - 1番目までの台風の数を, セグメント木を用いて引いておき, 2回目では, クエリ(p, q, r)に対して1 ~ r番目までの台風の数を加算します.

これをすることで、１つのクエリの処理にO(logN), その他クエリの並び変えなどにO(NlogN)くらいかかるので, 全体で O((Q + N)logN)くらいで問題に答えることが出来ます.

続きを読む

[JOI合宿]2007-Day1:Factorial

此方は、エラトステネスが遅すぎて話しにならない感じになっています... 0.5s間に合うかなあ...

nを素因数分解して、max((nの素因数p_i)*(p_iの指数))が答えになります.
[簡易な証明]
nの素因数p_iがp_iの指数個あるということは、最低でもp_iの指数個のp_iが必要になり、それは、p_i置きにでてくるので、max((nの素因数p_i)*(p_iの指数))の数があればmの階乗でnを作ることができます(それ以下の数は全て階乗に内包されています.)

続きを読む

[JOI合宿]2007-Day1:Score

#これからのオーダーの話しをしよう

一番最初のとしからゆっくりと.
点数の最大値をPとするとき、O(max(P, N))で、後半のデータセットではO(N)です.
エセDPしてます.
今年の予選問2もO(max(P,N))でこの解法で解けます が、空間計算量が心配なところです.(問題忘れたけど)

続きを読む