ABC301 参加記

5完45:27 125位

Cで詰まった&Fが3分間に合わなかったのにこの順位なのびっくり

落ちたからやめた人多そう

A Overall Winner

素直にやります

A,Tの数を数えて片方が大きいならそれを出力、等しいなら後ろにないほうでOK

(AC 2:17)

B Fill the Gaps

これも素直にやる

とりあえず最初の数だけ入れておいて、あとは間の数を定義通りループで入れていく

(AC 5:07)

C AtCoder Cards

貪欲の自信がなかった...

とりあえず、"@atcoder" に含まれないもので数が異なるものがあるとどうしようもないのでNoです

あとはこれらをうまくそろえていけばよくて、足りてないものを@で補填していくのが最善になります

 

が、なぜか本番で最善かわからなかったのでフローで殴りました

スタート、ゴール、S,Tのa~z,@にあたるものを頂点とします

スタート -> Sの各文字:容量=Sにある文字の個数

Sの各文字->Tの各文字:容量=INF

 "atcoder"でない小文字は同じ文字にだけ

 "atcoder"にある小文字は同じ文字+@に

 @は@,atcoderのすべてに

Tの各文字->ゴール:容量=Tにある文字の個数

として流量がNであればよいです

 

(AC 26:51)

D Bitmask

こっちのほうが簡単では?

まず1のところはどうしようもないので、加算しておきます

あとは?のところを変えていくのですが、1にできるなら変えるのが最善です

難易度C>>>Dと思ったけどそんなことなかった

(AC 29:47)

 

E Pac-Takahashi

やることわかるけど実装重め

まず問題文に「18個以下」と強調して書いてある&最短距離的なので、bitDP使うんだろうな~と思います

お菓子を取る順番を決めてしまえば、それぞれの最短距離を求めればいいだけですがこれを愚直にやるとO(K!) [K=お菓子の個数]になります

こういう順列全探索の高速化はbitDPが相性がいいことが知られています

つまり、順番はそこまで大事でなくて「どこを通ったか/通っていないか」が重要なので、その情報をbitで持つことで計算量をO(2^K)に改善できます

 

それぞれの最短距離を求めればいいだけ、と書いたのですがここをちゃんと考えておきます

もう少しサイズが小さければワーシャルフロイドを使って全ペアの最短距離をO((HW)^3)で計算できますが、今回の制約では厳しいです

重要なのはお菓子のあるマス(+スタート・ゴール)への距離なので、このK+2マスについてわかればよいです

ということで、それぞれのマスを始点として最短経路を計算します(BFS, Dijkstraなど)

それぞれの最短距離がわかれば、あとはbitDP(巡回セールスマン問題と同じ)で解くことができます

 

(AC 45:27)

 

F Anti-DDoS

いかにも設定から作られてそうですが、適度な難易度でおもしろかった

 

「(連続でない)部分列としてTが存在するSの個数」の典型として、

dp[i][j] := Sのi文字目まで見てTのj文字目まで存在する通り数

と定義して計算するというものがあります

例:?を含むSを書き換えて、"atcoder"が含まれるのは何通りか?

 

今回も考え方としては同じです

dp[i][j] := Sのi文字目まで見て"DDoS"のj文字目まで存在する通り数、とします

3,4文字目のo,Sは小文字・大文字という条件しかないので簡単です

ただし、1,2文字目のDDは「1文字目と2文字目が等しい」という条件がついているので少し難しいです

 

DDの部分を解決することを考えましょう

愚直に考えるとアルファベットのi文字目があるか?という情報をもってbitDPができそうですが、これは2^26必要で計算量が厳しそうです

そのため具体的に「どの文字があるか?」と持つことは諦めて「文字が何種類あるか?」を持つことを考えます

 

dp[i][j][k] :=  Sのi文字目まで見て"DDoS"のj文字目まで存在して、今までに出現した大文字の種類数がkである通り数

と定義して計算していきます

 

もしS[i]=?であれば、今まで出現した文字とかぶるorかぶらないの2パターンを考えます

かぶるときは、どの文字とかぶるかがk通りあるので、

dp[i][2][k] += dp[i][1][k] * k と遷移します

かぶらないときは、同様に考えて

dp[i][1][k+1] += dp[i][1][k] * (26 - k) と遷移します

 

もしS[i]=大文字であれば、今まで出現した文字とかぶるorかぶらないの2パターンを考えます

少しここが厄介なので状況を整理します

i-1文字目までで、すでに決まっている(=?でない)大文字がA種類

i-1文字目までで、?から大文字に変えた箇所がB個(これはどの大文字ともかぶらない)

とします

S[i]が今までに登場した大文字とかぶる確率を考えます

もし、すでに決まっているA種類のものと同じであれば確率は1です

そうでなければ、B / (26 - A)になります

この確率をかけてdpの遷移をしてあげればよいです

また、かぶらない確率は上の結果から容易に計算できます

 

最終的にはdp[N][0][k] + dp[N][1][k] + dp[N][2][k] + dp[N][3][k]を出力すればACとなります

(AC 108:37)

 

総括

Fちゃんと通したかった