[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
とある置換積分 [数学]
関数√(x^2+1)を積分するときに, 多くの参考書では
"t-x=√(x^2+1)と置換する"だとか, "最初に1/√(x^2+1)を積分する"と書かれています.
後者はともかく, 前者なんて積分結果を知らないと絶対に思いつきません. (思いついた人はゴメンナサイ)
そこで, 積分結果を知らなくても一発で積分できちゃう方法を記します. (長いですが, 頑張れば必ずできるのです)
"t-x=√(x^2+1)と置換する"だとか, "最初に1/√(x^2+1)を積分する"と書かれています.
後者はともかく, 前者なんて積分結果を知らないと絶対に思いつきません. (思いついた人はゴメンナサイ)
そこで, 積分結果を知らなくても一発で積分できちゃう方法を記します. (長いですが, 頑張れば必ずできるのです)
AOJ 0243: Filling Game [AOJ]
去年の夏に解いた問題でしたが, 入力周りにエラーがあったのと, そもそもそのままではTLE解法だったようです.
なので, すこしだけ工夫をしました.
入力部分は, 間に空白や\nや\rが含まれるので, getcharで頑張って1文字ずつとって来ています.
基本アルゴリズムは幅優先探索です. 塗りつぶしの処理で深さ優先探索を行なっており, その過程で,現在のR, G, Bの数を記憶しておきます.
キューからとりだしたときに, RまたはGまたはBの数がx * y (=フィールドのサイズ)であれば, 探索を打ち切っています.
なので, すこしだけ工夫をしました.
入力部分は, 間に空白や\nや\rが含まれるので, getcharで頑張って1文字ずつとって来ています.
基本アルゴリズムは幅優先探索です. 塗りつぶしの処理で深さ優先探索を行なっており, その過程で,現在のR, G, Bの数を記憶しておきます.
キューからとりだしたときに, RまたはGまたはBの数がx * y (=フィールドのサイズ)であれば, 探索を打ち切っています.
AOJ 0237: Last Door [AOJ]
最近、問題解くのに時間かけすぎな気もしますが...
あんまりバシバシ解けるタイプでも無いので, そうなれるようにちょっとずつ変わって行きたい所存です.
ちなみにこれ解けてません. 三角関数まわりの誤差でしょうか.
強連結成分分解は間違ってないはずです.
あんまりバシバシ解けるタイプでも無いので, そうなれるようにちょっとずつ変わって行きたい所存です.
ちなみにこれ解けてません. 三角関数まわりの誤差でしょうか.
強連結成分分解は間違ってないはずです.
[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って大丈夫なんだろうか...
AOJ 1082:11224111122411 [AOJ]
さかにゃんさんの問題です.
問題文はこちら.
まず, 問題の答えの組み合わせは, 同じ文字が連続している部分の変換方法の積であることが容易に分かります.
各々の連続している部分の変換方法は, 前の(5つ or 3つ)の値を足していく数列を動的計画法で前計算をしておくと, 容易に求めることができます.
計算量は, 各ケースに対してO(|S|)位なので, テストケースの数をTとして, O(T|S|)となります.
問題文はこちら.
まず, 問題の答えの組み合わせは, 同じ文字が連続している部分の変換方法の積であることが容易に分かります.
各々の連続している部分の変換方法は, 前の(5つ or 3つ)の値を足していく数列を動的計画法で前計算をしておくと, 容易に求めることができます.
計算量は, 各ケースに対してO(|S|)位なので, テストケースの数をTとして, O(T|S|)となります.
