[JOI合宿]2009-Day1:Sequence [JOI関連]
循環性に気づくまでが勝負です.
まず, 奇数の数だけを知りたいので, 各数の下位ビットのみに注目します.
すると, それらの数を結合して, 2進数とみなすことができます.
鳩の巣原理っぽく考えると, 2^m個以上の相異なる項を作ることが出来ないのが分かり, かつ, ある2進数を作り出す規則は前の項に依存することより, この2進数列は循環することが分かります.
ゆえに, 実際に循環する2進数を列挙して, (1 ~ q項めの奇数の数) - (1 ~ p - 1項目の奇数の数)を求めてやれば良いです.
まず, 奇数の数だけを知りたいので, 各数の下位ビットのみに注目します.
すると, それらの数を結合して, 2進数とみなすことができます.
鳩の巣原理っぽく考えると, 2^m個以上の相異なる項を作ることが出来ないのが分かり, かつ, ある2進数を作り出す規則は前の項に依存することより, この2進数列は循環することが分かります.
ゆえに, 実際に循環する2進数を列挙して, (1 ~ q項めの奇数の数) - (1 ~ p - 1項目の奇数の数)を求めてやれば良いです.
[JOI合宿]2008-Day1:Flu [JOI関連]
愚直に探索するとN^2になりますが, 周辺の点を調べると計算が減る感じの幅優先探索問題です.
O2つけると爆速でいいですね.
ソートが一番重くて, O(NlogN)くらいだと思います.
整数点のユークリッド距離は二乗しておくと誤差が怖くないです.
O2つけると爆速でいいですね.
ソートが一番重くて, O(NlogN)くらいだと思います.
整数点のユークリッド距離は二乗しておくと誤差が怖くないです.
[JOI合宿]2010-Day3:Finals [JOI関連]
呼んだ瞬間最小全域木から幾つか辺を抜く問題だと思ったけど, 頭の中でサンプルの全域木を書いたら間違っていて絶望していました.
実際ちゃんとやったらそのとおりで簡単.
O(MlogN)程度です.
問題文 : http://qnighy.github.com/informatics-olympiad/joi2010-day3-finals-problem.html
実際ちゃんとやったらそのとおりで簡単.
O(MlogN)程度です.
問題文 : http://qnighy.github.com/informatics-olympiad/joi2010-day3-finals-problem.html
[JOI合宿]2009-Day2:Advertisement [JOI関連]
ローカルでAC済み.
強連結成分分解の練習問題として良い問題です.
強連結成分分解をして, 同じ強連結成分を１つのグループと見ます.
このグループで, 辺を逆にしたグラフを構築して, 他のグラフへの辺が存在しないグループに情報を与えると, 全てのグループへ情報を与えられます.
無駄に(?) setを使っているので, O((m+n)log(m+n))くらいで、十分早く動きます.
[訂正] setなんて使わなくても大丈夫でした (O(m+n))
強連結成分分解の練習問題として良い問題です.
強連結成分分解をして, 同じ強連結成分を１つのグループと見ます.
このグループで, 辺を逆にしたグラフを構築して, 他のグラフへの辺が存在しないグループに情報を与えると, 全てのグループへ情報を与えられます.
無駄に(?) setを使っているので, O((m+n)log(m+n))くらいで、十分早く動きます.
[訂正] setなんて使わなくても大丈夫でした (O(m+n))
[JOI合宿]2009-Day2:Abduction [JOI関連]
ローカルでAC確認済み.
明らかに, 東西の移動と南北の移動は独立なので切り離して考える.
ある方向から地点Pに行くには, その方向であって、Pより前の点にいく方法すべての総和となる. ゆえに, 総和を求めて加算すれば良い.
ただし, 最初の地点については, 後ろの場所がないので, たどり着く方法は0となる.
計算量は, O(N * max(W, H))となる. 10^7って大丈夫なんだろうか...
明らかに, 東西の移動と南北の移動は独立なので切り離して考える.
ある方向から地点Pに行くには, その方向であって、Pより前の点にいく方法すべての総和となる. ゆえに, 総和を求めて加算すれば良い.
ただし, 最初の地点については, 後ろの場所がないので, たどり着く方法は0となる.
計算量は, O(N * max(W, H))となる. 10^7って大丈夫なんだろうか...
[JOI合宿]2011-Day1:Banner [JOI関連]
問題文 : こちら
思ったとおりに実装してAC.
実装 15 分 + Debug 1 分 (string.hの宣言を忘れている & 答えのオーバーフロー修正.)
愚直解として, 辺を4つ決めるO((WH)^2)の解が考えられる. これは40 %解法となる.
ここで, 長方形の縦の辺を全て決めると (O(H^2)), 横の辺を全て走査し(O(W)), 横の辺に含まれている色を分類することで, 数学的に旗の組み合わせを求めることができる. (O(1))
故に, O(W^2H)で, 100 % の得点を得ることができる.
思ったとおりに実装してAC.
実装 15 分 + Debug 1 分 (string.hの宣言を忘れている & 答えのオーバーフロー修正.)
愚直解として, 辺を4つ決めるO((WH)^2)の解が考えられる. これは40 %解法となる.
ここで, 長方形の縦の辺を全て決めると (O(H^2)), 横の辺を全て走査し(O(W)), 横の辺に含まれている色を分類することで, 数学的に旗の組み合わせを求めることができる. (O(1))
故に, O(W^2H)で, 100 % の得点を得ることができる.
2006年JOI予選模擬問5 [JOI関連]
昔のJOIは多倍長好きだったんですかね...
問題文を読むと, 求める答えが n H (r - mn) = (n + r - mn - 1) C (r - mn)であることはあきらか.
あとは, nCk = n! / k!(n - k)! を実直に計算します. (バグたくさんで悲しみに包まれました.)
頭の悪い多倍長なのでAOJでは当然間に合いません. ((n, m, r) = (10000, 0, 10000)ケースで20秒くらいかかります)
問題文を読むと, 求める答えが n H (r - mn) = (n + r - mn - 1) C (r - mn)であることはあきらか.
あとは, nCk = n! / k!(n - k)! を実直に計算します. (バグたくさんで悲しみに包まれました.)
頭の悪い多倍長なのでAOJでは当然間に合いません. ((n, m, r) = (10000, 0, 10000)ケースで20秒くらいかかります)
