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]
最近、問題解くのに時間かけすぎな気もしますが...
あんまりバシバシ解けるタイプでも無いので, そうなれるようにちょっとずつ変わって行きたい所存です.
ちなみにこれ解けてません. 三角関数まわりの誤差でしょうか.
強連結成分分解は間違ってないはずです.
あんまりバシバシ解けるタイプでも無いので, そうなれるようにちょっとずつ変わって行きたい所存です.
ちなみにこれ解けてません. 三角関数まわりの誤差でしょうか.
強連結成分分解は間違ってないはずです.
AOJ 1082:11224111122411 [AOJ]
さかにゃんさんの問題です.
問題文はこちら.
まず, 問題の答えの組み合わせは, 同じ文字が連続している部分の変換方法の積であることが容易に分かります.
各々の連続している部分の変換方法は, 前の(5つ or 3つ)の値を足していく数列を動的計画法で前計算をしておくと, 容易に求めることができます.
計算量は, 各ケースに対してO(|S|)位なので, テストケースの数をTとして, O(T|S|)となります.
問題文はこちら.
まず, 問題の答えの組み合わせは, 同じ文字が連続している部分の変換方法の積であることが容易に分かります.
各々の連続している部分の変換方法は, 前の(5つ or 3つ)の値を足していく数列を動的計画法で前計算をしておくと, 容易に求めることができます.
計算量は, 各ケースに対してO(|S|)位なので, テストケースの数をTとして, O(T|S|)となります.
[未]AOJ 0553: Dungeon [AOJ]
JOIボリューム, この問題が終わればチェックメイトなのですが, 中々オーダーが改善できません...
30点解法です. 満点解法ではないので詳しい解法は述べませんが, 泉の最小使用回数をminAとすると, O(N + minA* (NlogN))くらいです.
minAが10^4くらいになると死にます. (最大ケースでは, minA >= 10^9なのでこの解法自体ダメなのかもしれない.)
もう少し頑張ると O(N + minA * (log^2N))にできる可能性が存在しますが, 現時点では厳しそうです (そもそも満点は得れ無さそうなオーダーでかなしい).
想定解はO(NlogN)くらいなのでしょうか...
30点解法です. 満点解法ではないので詳しい解法は述べませんが, 泉の最小使用回数をminAとすると, O(N + minA* (NlogN))くらいです.
minAが10^4くらいになると死にます. (最大ケースでは, minA >= 10^9なのでこの解法自体ダメなのかもしれない.)
もう少し頑張ると O(N + minA * (log^2N))にできる可能性が存在しますが, 現時点では厳しそうです (そもそも満点は得れ無さそうなオーダーでかなしい).
想定解はO(NlogN)くらいなのでしょうか...
AOJ 0575: Festivals in JOI Kingdom [AOJ]
Dijkstra(O(M log N)して、Maximum Spanning Treeを作ってO(M log N), Q個のクエリにLCAを使って応答をします(O(QlogN)).
全体のオーダーはO((M+Q)logN)くらいです. 詳しい解説はiwi先生のスライドなどを参考にしてください (多分想定解法そのままなので).
全体のオーダーはO((M+Q)logN)くらいです. 詳しい解説はiwi先生のスライドなどを参考にしてください (多分想定解法そのままなので).
AOJ 0552: Exposition [AOJ]
難しすぎる... かなり時間かけました.
前回の記事の通り, 点対を実際にグループ分けします.
素朴な方法では, グループ分けがO(N^2)になってしまいますが, このグループ分けをO (N)に横着しています.
具体的には, 今日書いた
|x1 - x2| + |y1 - y2| = max(|x1 + y1 - (x2 + y2)|, |x1 - y1 - (x1 - y2)|) という式を使って計算をしています.
グループ分けの基準とする距離をKと仮定します.
グループ分けが前者で出来たと仮定してグループ分けしたものと, グループ分けが後者で出来たと仮定してグループ分けしたものについて、矛盾がなければ距離Kでグループ分けが出来ます.
Kでグループ分けできれば, K + 1でもグループ分けができるので、二分探索を行えます.
前回の記事の通り, 点対を実際にグループ分けします.
素朴な方法では, グループ分けがO(N^2)になってしまいますが, このグループ分けをO (N)に横着しています.
具体的には, 今日書いた
|x1 - x2| + |y1 - y2| = max(|x1 + y1 - (x2 + y2)|, |x1 - y1 - (x1 - y2)|) という式を使って計算をしています.
グループ分けの基準とする距離をKと仮定します.
グループ分けが前者で出来たと仮定してグループ分けしたものと, グループ分けが後者で出来たと仮定してグループ分けしたものについて、矛盾がなければ距離Kでグループ分けが出来ます.
Kでグループ分けできれば, K + 1でもグループ分けができるので、二分探索を行えます.
AOJ 0564: Bug Party [AOJ]
AOJ で解いた問題の中で 300 問目にあたる問題です.
セグメント木と二分探索を用いました.
N匹の微生物たちについて, foo許容量が多い微生物をシャーレに入れていき, それらの微生物のfoo放出量の総和が, もっとも(foo許容量が小さい微生物) * N より小さければ, すべての微生物が死なずにシャーレの中に入ることになります.
このNを求めるために二分探索をし, 具体的な操作はセグメント木を用います. 2つを併せて, オーダーはO(N log^2 N)くらいです.
セグメント木は、数値の更新が更新が頻繁に行われるデータ列の中の最大値を求めるものを構築しました.
更新をO(log N), 取り出しをO(1)で出来るような構造にしました. (これだけなら別のデータ構造でもいいかもしれないですが...)
自由自在にセグメント木を扱えるようにしていきたいです.
セグメント木と二分探索を用いました.
N匹の微生物たちについて, foo許容量が多い微生物をシャーレに入れていき, それらの微生物のfoo放出量の総和が, もっとも(foo許容量が小さい微生物) * N より小さければ, すべての微生物が死なずにシャーレの中に入ることになります.
このNを求めるために二分探索をし, 具体的な操作はセグメント木を用います. 2つを併せて, オーダーはO(N log^2 N)くらいです.
セグメント木は、数値の更新が更新が頻繁に行われるデータ列の中の最大値を求めるものを構築しました.
更新をO(log N), 取り出しをO(1)で出来るような構造にしました. (これだけなら別のデータ構造でもいいかもしれないですが...)
自由自在にセグメント木を扱えるようにしていきたいです.
