狠狠撸

狠狠撸Share a Scribd company logo

各种问题の解説

?
?
tozan gezan
tozan gezan

JOI夏季セミナー 2014

1 of 16
Download to read offline
各种问题の解説 @dp_zirk, tozangezan, wolf_sothe
なぜこんなスライドを作ったか ● 生徒だけがスライドを作って大変な思いをしている のに、チューターだけ楽してたらアレですよねぇ… ● TopCoderのDiv1Hardの問題を簡潔に解説してい きます。 ● これらはすべて夏季セミナー中に解いたものです。
Ambigram (SRM183 Hard) ● 問題概要: 自分で調べてください。空文字列が Ambigramでないのがめんどい要素。 ● 解法: 区間DP。 ● 長さ1，2のときは別に処理したほうが良い。 ● あと、1文字以上つかったかどうかも持っておく。
Scheduling (SRM165 Hard) ● 問題概要: 自分で調べてください。 ● 解法: ● 実は状態量がかなりすくない。(4096*100くらい) ● priority_queueで全探索すれば大丈夫。 ● DFSしたらTLEした。
Roxor (SRM216 Hard) ● 問題概要: 自分で調べてください。ゲーム系。 ● 解法: ● 実はそれぞれの山の偶奇だけを考えればよい(相 手と同じことをすれば2個減るだけ) ● また、奇数個ある山から取るだけでよい(偶数個の ところを取っても自分の番に2つ減るだけで変化が ない) ● あとはbitDP
SwapSorter (SRM 279 Hard) ● 問題概要: 自分で調べてください。 ● 解法: Ad-hoc ● そろってないところに書いてある数字とそれの正し い位置でUnion-Findして(頂点は位置ではなく数 字)連結成分ごとに考える。 ● 連結成分の大きさが2のときはsize/2回、 ● そうでないときはsize-1回swapすることができる。
PolyominoCut (SRM 242 Hard) ● 問題概要: 自分で調べてください。 ● 解法: やるだけ ● まず穴のないk-ominoを全列挙する。 ● それぞれについてそのk-ominoが内部にある、辺 に接する、角に接するものを考えて掛け算や足し 算で上手く計算する。 ● 穴判定、辺に接することが可能かの判定はBFSす ればよい。角判定は2辺で可能で(k-ominoを含む 最小長方形の最も上,最も左)にブロックがあれば よい。
MergingGraph (SRM 321 Hard) ● 問題概要: 自分で調べてください。 ● 解法: ● まず、マージできなくなるまで、Union-Findを使って i->k, j->kの辺があるときに(i,j)をマージ、を繰り返 す。しっかりUnion-Findを活用しないと元は違う頂 点だが今マージされて同じ頂点が行き先のとき間 違える。あと、k->i, k->jも同じようにやる。 ● こうしてできたものは孤立点と直線グラフとルー プ。ループの大きさは今ループがあるならそれらの 大きさのgcd、ないなら直線グラフを全部つなげる。
BeautifulHexagonalTilings (SRM 355 Hard) ● 問題概要: 自分で調べてください。 ● 解法: 答えの数がかなり少ない。 ● 全探索 or bitDP ● 全探索した。 ● TLEした。 ● ループ減らして3倍くらい定数倍改善した。 ● 通った。 ● あのさぁ……。
PresentationComp (SRM 221 Hard) ● 問題概要: 自分で調べてください。 ● 解法: ● 次のような不変量がある。 ● (xの個数 mod 8)*6+((偶数個目のxの右にあるyの 個数)-(奇数個目の右にあるyの個数) mod 6) ● 答えの長さは短いので全探索してこの不変量を比 べる。
ColorfulBoard (SRM 517 Hard) ● 問題概要: 自分で調べてください。rng_58さん作。 ● 解法: ● 塗られない行または列が存在する(全部塗ると仮 定すると一番最初に塗られた行or列が意味をなさ なくて無駄) ● それを全部についてためし、その行と違う色のとこ ろが分かれば列に塗ったいろが分かる。あと塗る 順序(i行とj列どっちが早いか)がわかる。これでグ ラフをつくって閉路を探す。あれば矛盾。 ● 矛盾がなければ使う個数は簡単にわかる。
CountryWar (SRM 288 Hard) ● 問題概要: 自分で調べてください。 ● 解法: bitDP。 ● 結構計算量が重くなってしまって削るのが大変。 ● しかも結局定数倍改善した。 ● 答えが10-65くらいになることがあるので、最初に明 らかに答えが10-9よりも小さくてどうでもいいケース は0を返した。
RandomApple (SRM 478 Hard) ● 問題概要: 自分で調べてください。rng_58さん作。 ● 解法: ● i個目の箱を選んだときにりんごの数の合計がk個 となるほかの箱の選び方が何通りあるかDPで求 める(long longに収まる)。これは1回O(NK)。 ● しかし↑はまとめて計算できる。iごとに引き算して あわせてO(NK)ですませられる。 ● そこからkそれぞれについて箱iの重みが分かり、そ の箱の中からりんごjを引く確率にその値をかけれ ば全体で箱iの中のりんごjを引く確率が分かる。
CurvyonRails (SRM 570 Hard) ● 問題概要: 自分で調べてください。snuke作。 ● 解法: snukeに聞いてください。 ● ループを複数作る系は最小費用流が有効。 ● これに流す。
TheXGame (SRM 304 Hard) ● 問題概要: 自分で調べてください。ゲーム系。 ● 解法: 数　学　オ　リ　ン　ピ　ッ　ク ● 帰納法で普通のNimと同様であることが証明でき る。 ● 普通に数学オリンピックで強い人じゃないと気がつ かないと思う。 ● 証明の仕方が妙に数学オリンピックにありそう。 ● 証明できたらあとはやるだけ。
TransformMatrix (SRM 407 Hard) ● 問題概要: 自分で調べてください。 ● 解法: どうせ最小費用流。 ● 今回のグラフでは、可能かどうか判定するための 容量制限のところと、コストを求めるためのコスト部 分は違う辺にあるというのが気づきにくい。 ● 各頂点について使える回数/2+(スタートの数字)+ (ゴールの数字)が頂点容量。 ● あとは移動先にコスト1容量∞の辺を張る。 ● 88方向に移動可能であることに注意!!!!

More Related Content

各种问题の解説

  • 2. なぜこんなスライドを作ったか ● 生徒だけがスライドを作って大変な思いをしている のに、チューターだけ楽してたらアレですよねぇ… ● TopCoderのDiv1Hardの問題を簡潔に解説してい きます。 ● これらはすべて夏季セミナー中に解いたものです。
  • 3. Ambigram (SRM183 Hard) ● 問題概要: 自分で調べてください。空文字列が Ambigramでないのがめんどい要素。 ● 解法: 区間DP。 ● 長さ1，2のときは別に処理したほうが良い。 ● あと、1文字以上つかったかどうかも持っておく。
  • 4. Scheduling (SRM165 Hard) ● 問題概要: 自分で調べてください。 ● 解法: ● 実は状態量がかなりすくない。(4096*100くらい) ● priority_queueで全探索すれば大丈夫。 ● DFSしたらTLEした。
  • 5. Roxor (SRM216 Hard) ● 問題概要: 自分で調べてください。ゲーム系。 ● 解法: ● 実はそれぞれの山の偶奇だけを考えればよい(相 手と同じことをすれば2個減るだけ) ● また、奇数個ある山から取るだけでよい(偶数個の ところを取っても自分の番に2つ減るだけで変化が ない) ● あとはbitDP
  • 6. SwapSorter (SRM 279 Hard) ● 問題概要: 自分で調べてください。 ● 解法: Ad-hoc ● そろってないところに書いてある数字とそれの正し い位置でUnion-Findして(頂点は位置ではなく数 字)連結成分ごとに考える。 ● 連結成分の大きさが2のときはsize/2回、 ● そうでないときはsize-1回swapすることができる。
  • 7. PolyominoCut (SRM 242 Hard) ● 問題概要: 自分で調べてください。 ● 解法: やるだけ ● まず穴のないk-ominoを全列挙する。 ● それぞれについてそのk-ominoが内部にある、辺 に接する、角に接するものを考えて掛け算や足し 算で上手く計算する。 ● 穴判定、辺に接することが可能かの判定はBFSす ればよい。角判定は2辺で可能で(k-ominoを含む 最小長方形の最も上,最も左)にブロックがあれば よい。
  • 8. MergingGraph (SRM 321 Hard) ● 問題概要: 自分で調べてください。 ● 解法: ● まず、マージできなくなるまで、Union-Findを使って i->k, j->kの辺があるときに(i,j)をマージ、を繰り返 す。しっかりUnion-Findを活用しないと元は違う頂 点だが今マージされて同じ頂点が行き先のとき間 違える。あと、k->i, k->jも同じようにやる。 ● こうしてできたものは孤立点と直線グラフとルー プ。ループの大きさは今ループがあるならそれらの 大きさのgcd、ないなら直線グラフを全部つなげる。
  • 9. BeautifulHexagonalTilings (SRM 355 Hard) ● 問題概要: 自分で調べてください。 ● 解法: 答えの数がかなり少ない。 ● 全探索 or bitDP ● 全探索した。 ● TLEした。 ● ループ減らして3倍くらい定数倍改善した。 ● 通った。 ● あのさぁ……。
  • 10. PresentationComp (SRM 221 Hard) ● 問題概要: 自分で調べてください。 ● 解法: ● 次のような不変量がある。 ● (xの個数 mod 8)*6+((偶数個目のxの右にあるyの 個数)-(奇数個目の右にあるyの個数) mod 6) ● 答えの長さは短いので全探索してこの不変量を比 べる。
  • 11. ColorfulBoard (SRM 517 Hard) ● 問題概要: 自分で調べてください。rng_58さん作。 ● 解法: ● 塗られない行または列が存在する(全部塗ると仮 定すると一番最初に塗られた行or列が意味をなさ なくて無駄) ● それを全部についてためし、その行と違う色のとこ ろが分かれば列に塗ったいろが分かる。あと塗る 順序(i行とj列どっちが早いか)がわかる。これでグ ラフをつくって閉路を探す。あれば矛盾。 ● 矛盾がなければ使う個数は簡単にわかる。
  • 12. CountryWar (SRM 288 Hard) ● 問題概要: 自分で調べてください。 ● 解法: bitDP。 ● 結構計算量が重くなってしまって削るのが大変。 ● しかも結局定数倍改善した。 ● 答えが10-65くらいになることがあるので、最初に明 らかに答えが10-9よりも小さくてどうでもいいケース は0を返した。
  • 13. RandomApple (SRM 478 Hard) ● 問題概要: 自分で調べてください。rng_58さん作。 ● 解法: ● i個目の箱を選んだときにりんごの数の合計がk個 となるほかの箱の選び方が何通りあるかDPで求 める(long longに収まる)。これは1回O(NK)。 ● しかし↑はまとめて計算できる。iごとに引き算して あわせてO(NK)ですませられる。 ● そこからkそれぞれについて箱iの重みが分かり、そ の箱の中からりんごjを引く確率にその値をかけれ ば全体で箱iの中のりんごjを引く確率が分かる。
  • 14. CurvyonRails (SRM 570 Hard) ● 問題概要: 自分で調べてください。snuke作。 ● 解法: snukeに聞いてください。 ● ループを複数作る系は最小費用流が有効。 ● これに流す。
  • 15. TheXGame (SRM 304 Hard) ● 問題概要: 自分で調べてください。ゲーム系。 ● 解法: 数　学　オ　リ　ン　ピ　ッ　ク ● 帰納法で普通のNimと同様であることが証明でき る。 ● 普通に数学オリンピックで強い人じゃないと気がつ かないと思う。 ● 証明の仕方が妙に数学オリンピックにありそう。 ● 証明できたらあとはやるだけ。
  • 16. TransformMatrix (SRM 407 Hard) ● 問題概要: 自分で調べてください。 ● 解法: どうせ最小費用流。 ● 今回のグラフでは、可能かどうか判定するための 容量制限のところと、コストを求めるためのコスト部 分は違う辺にあるというのが気づきにくい。 ● 各頂点について使える回数/2+(スタートの数字)+ (ゴールの数字)が頂点容量。 ● あとは移動先にコスト1容量∞の辺を張る。 ● 88方向に移動可能であることに注意!!!!