2022年4月3日
元気出せよ 俺はお前の味方だからさ
I★M★S★H★I★M★E
戒め ABC246があまりうまく行かなかった。レートは上がった。悔しい。
自分がわかればいいや。な記事デス。読まないでください。
ABC246-E Bishop 2
[01-BFS, 普通のBFSじゃTLE,斜め移動]
自分はこのTLEが出るところまでできましたが、TLEを取ることができなかった…力不足デス…（CV.チノちゃん) 普通の幅優先探索しようとすると、queueに入れて…って感じでまわしますよね。でもそれだとTLE…どうしてTLEになってしまうかは分かりません(ｴｰｯ！！(cv.はちわれ))
まあ、TLEになる理由はわからないけど、
もしくはこれから行われるので見なくてもいいです。従って、そのようなマスがあった際は探索を打ち切ればいいです。
この辺を理解するかという気持ちで筆を取った。
| # | |||||||||
| 0 | |||||||||
| Goal | |||||||||
| # |
まあ、なんか、適当にこういう感じな表があったとします。0が初期位置で、Goalがゴールです。 幅優先探索で、「左下」「右下」「左上」「右上」の順で見ていくとします。
また、解説の「打ち切る」とは、「左下」を見ているときに「左下」の探索を打ち切り、「右下」の探索を始めることを意味します。
とりあえず、上の状態から、探索を行うとこうなります。 今探索しているところをかぎかっこで囲っておきます。(数字)は、何番目に見つけたかデス。つまり、queueに突っ込まれた順番だと思いましょう。
| 1(7) | |||||||||
|---|---|---|---|---|---|---|---|---|---|
| # | 1(6) | ||||||||
| [0] | |||||||||
| 1(1) | 1(3) | Goal | |||||||
| 1(2) | 1(4) | ||||||||
| # | 1(5) |
こんな感じで、7つが新たにqueueにpushされます。 次は、1(1)がqueueから取り出されて、探索することになります。
まず[1(1)]から左下の探索をします。
| 1(7) | |||||||||
|---|---|---|---|---|---|---|---|---|---|
| # | 1(6) | ||||||||
| 0 | |||||||||
| [1(1)] | 1(3) | Goal | |||||||
| 1(2) <- 2 | 1(4) | ||||||||
| # | 1(5) |
1(2) が 2にコストを更新するか？となりますが、コスト1で 1(2)へ行けることはわかっているので、更新はしません。
ここからがTLEを除くために大事なことです。
1(2)と[1(1)]のコストは同じなので、これ以上左下への探索を行う必要はありません。 なぜなら、壁の位置の探索は、これから1(2)が行ってくれるし、[1(1)]から左下へ行ったときのスコアと1(2)から左下へ行ったときのスコアは同じ2になるはずなので、であれば1(2)へ任せてしまって良いからです。まあ、壁がスコア2ってわけわからないのでここの説明はちょっとわからないと思いますが…すみません良い例が作れなくて。
つぎに、右下と左上を更新します。
| 1(7) | |||||||||
|---|---|---|---|---|---|---|---|---|---|
| 2(11) | # | 1(6) | |||||||
| 2(10) | 0 | ||||||||
| [1(1)] | 1(3) | Goal | |||||||
| 1(2) <- 2 | 2(8) | 1(4) | |||||||
| # | 2(9) | 1(5) |
これはヤルだけデス。
次は右上デス。
[1(1)] から右上に行くと 0ですね
| 1(7) | |||||||||
|---|---|---|---|---|---|---|---|---|---|
| 2(11) | # | 1(6) | |||||||
| 2(10) | 0 <- 2 | ||||||||
| [1(1)] | 1(3) | Goal | |||||||
| 1(2) | 2(8) | 1(4) | |||||||
| # | 2(9) | 1(5) |
コスト0のマス(開始位置)を2に更新するかと聞かれますが、コスト0で行けることがわかっているので、更新しません。
ここからがTLEを除くために大切な作業デス。
[1(1)]と0は、0のほうがコストが低いので、これ以上右上への探索は行わなくていいです。 なぜなら、0よりも右上の1(6)と1(7)の探索は、0の位置からの探索の時点で既に行っており、0の位置からの探索ってことは、コストは1であり、これ以上探索を行っても、コストが低くならないことが分かりきっているからです。
次は[1(2)]からの探索デス。右下と左上はもういいとして・・・
| 1(7) | |||||||||
|---|---|---|---|---|---|---|---|---|---|
| 2(11) | # | 1(6) | |||||||
| 2(10) | 0 | ||||||||
| 2(13) | 1(1) | [1(3)] | Goal | ||||||
| [1(2)] | 2(8) | 1(4) | |||||||
| # | 2(12) | 2(9) | 1(5) |
特に何もないですね。
次は右上ですね。
| 1(7) | |||||||||
|---|---|---|---|---|---|---|---|---|---|
| 2(11) | # | 1(6) | |||||||
| 2(10) | 0 <- 2 | ||||||||
| 2(13) | 1(1) <-2 | [1(3)] | Goal | ||||||
| [1(2)] | 2(8) | 1(4) | |||||||
| # | 2(12) | 2(9) | 1(5) |
1(1))を２に更新するかと聞かれますが。TLEを取り除くために…で行ったように、現在のマスと同じスコアのマスを見つけたらこれ以上右上への探索はしなくていいです。よって1(1)の右上の０には行かなくていい。
次は1(3)からの探索です.
| 1(7) | |||||||||
|---|---|---|---|---|---|---|---|---|---|
| 2(11) | # | 1(6) | |||||||
| 2(10) | 0 <- 2 | ||||||||
| 2(13) | 1(1) | [1(3)] | Goal | ||||||
| [1(2)] | 2(8) <- 2 | 1(4) | |||||||
| # | 2(12) <- 2 | 2(9) | 1(5) |
2(8)を2に更新するかと聞かれますね。 同じ値なので更新しなくていいです。左下への探索は続きます。 2(12)も２に更新するかと聞かれますが、更新しません。 探索の打ち切りが無い理由が分かりますか？
例が悪いのは申し訳ないですが、一行追加されていた場合を考えます。
| 1(7) | |||||||||
|---|---|---|---|---|---|---|---|---|---|
| 2(11) | # | 1(6) | |||||||
| 2(10) | 0 <- 2 | ||||||||
| 2(13) | 1(1) | [1(3)] | Goal | ||||||
| [1(2)] | 2(8) | 1(4) | |||||||
| # | 2(12) | 2(9) | 1(5) | ||||||
| ここ | # |
ここと書かれてますは、まだ探索できていないので、[1(3)]からの探索で見つけて上げる必要があります。だから、2(8)を更新しないからといって、左下への探索をやめてはいけません。
やめていいのは、[1(3)] と同じコスト、もしくはそれより小さいコストのマス。つまりはコスト１のマスか、０のマスを見つけたときだけです。
もし１行多かったら、ここのマスは2(14)に更新されることになりますね。
って感じでやっていくと、TLEが取れます！！！
ちなみに、
| # | |||||||||
| 0 | |||||||||
| Goal | |||||||||
| # |
この場合、Goalへは２手でたどりつけますね。
右下右下右下で１手。右上右上で２手目。って感じです。
若干説明分かりづらいかもしれませんがまとめマス。
探索開始位置 queueから取り出した位置のコスト以下の位置があった場合は、探索をやめる。
ABC246-F typewriter
[動的計画法、桁DP的な？文字列数え上げ、ncm,]
厄介な問題デス…
やり方としては、とりあえずめんどくさいので 'a','b','c'の３文字しかない世界を考えます
文字列の長さはL文字のものを作ります。
やり方としては,001を'a'のみ使ったL文字の文字列。110を'b'と'c'のみを使った文字列、のように対応付けます。
そうすると何が起こるか…考えましょう。とりあえずLは3以上だとしておきましょう。
まず、001('a')のみ、010('b')のみ100('c')のみで表せるL文字の文字列が何通りあるか考えましょう
- 001('a')のみのL文字の文字列は何通りあるか。
- 全部'a'の1通りのみ
- これをdp[001] = 1のように表現します。
- 010('b')のみのL文字…
- 同じ、1通り
- これをdp[010] = 1のように表現します。
- 100('c')のみ…
- 同じ。1通り
- これをdp[100]=1のように表現します。
こうなりますね！！！！
つまり、やり方としては、
dp[001] , dp[010], dp[011], dp[100], dp[101]. dp[110], dp[111]の7個を求めてやれば良いわけです。
dp[xxx]のxの一つだけが1の例は上でやったように簡単に求めることができました。
では、dp[011]のように'b'と'a'だけを使ってL文字の文字列が何通りあるかはどうやって考えれば良いのでしょうか？
今、Lを3としておきます。
- dp[011]が示す意味
- 長さが3の文字列で
- 'a'と'b'を少なくとも1回ずつ使った文字列は何通りあるか
こうなります。 答えは6通りなのですが、なぜだか分かりますか？
それは、"aaa","aab","aba","abb","baa","bab","bba","bbb"のうち、一つの文字しか使っていない不適合なものを除いた、"aab","aba","abb","baa","bab","bba",の6個デス。 では、この2という値はどうやって出したら良いのでしょうか。
まず、長さ2の文字列で、'a','b'を使った文字列を考えます。ここでは'b'が使われていないじゃん！みたいなことは無視します。
- 1文字目は'a'か'b'の二通り、2文字目は'a'か'b'の二通り、3文字目も2通りなので、2 * 2 * 2 = 8通りです。
この中から、一文字しか使っていない場合を取り除きます。 2文字の文字列で、1種類しか文字を使っていないものというのは、1個(dp[001]が示しています)です。で、これが文字の種類分だけあるので、2種類 * 1個で2個
- 8 - 2 = 6と求まりました。バンザイ
まあちょっと解説を書くのがめんどくさくなったので、要点だけ書こう。
- 文字種がx個で長さLの文字列は何通りあるかを求めたい。
- ある文字種を含まない場合も考慮すると x ^ L通りある。
- その中で、1種でも含まない場合を除く
- 1種含まない場合(つまり、x-1種で構成される文字列)
- 2種含まない場合(x-2種で構成される文字列)
- ・・・
- x-1種含まない場合(1種で構成される文字列)
- これらをxLから減算してやればいい。
こんな感じっすね（すっとぼけ）
