geam1113’s diary

主にAtcoderのコンテストの備忘録を書きます。AtCoder緑と水色を行ったり来たりしています。

ABC211 参加記録

C - chokudai

典型的なDPだと思います。

dp[i][j] := i文字目まで考慮した時に"chokudai"のj文字目までが何通りあるか

とします。

 

例えば、S[i] = 'k'だったとします。i-1文字目までに現れた全ての"cho"となる部分文字列に対して、i文字目を連結させて"chok"を作ることができます。

よって、S[i]が"chokudai"のj文字目であるとき、以下のように計算できます。

dp[i][j] += dp[i-1][j-1]

 

また、i-1文字目までにすでに現れた"chok"の分も足されるので、i文字目が何であっても以下のように計算されます。

dp[i][j] += dp[i-1][j]

 

答えはdp[N][8]です。

 

提出コード:https://atcoder.jp/contests/abc211/submissions/24500667

 

D - Number of Shortest Paths

全ての道路の移動時間が同じなので、単純なBFSをすると最短時間となります。そのままだと、最短経路の総数が出せないので、以下の状態を追加します。

dp[u] := 都市uへの最短経路の総数

 

一般的なBFSでは頂点uから頂点vに移動する時、頂点vが既に訪問済みの場合は処理を飛ばします。今回はそれが都市vへの最短時間と同じであったなら、

dp[v] += dp[u]

と計算します。vが未訪問であった時も同様に計算します。

実装の時は、都市uへの最短時間dist[u]も作っておき、dist[u] + 1 == dist[v]なら、上記計算を行えば良いです。

 

答えはdp[N]です。

 

提出コード:https://atcoder.jp/contests/abc211/submissions/24504591

 

E - Red Polyomino

解けなかったので、解説を見ました。

ポリオミノ自体は知らなくても、テストケース3で最大ケースが何通りあるかはわかるようです。

 

状態数としては少なくても、枝刈り等の余計な探索にかかる計算量の見積もり方がよくわかっていませんでした。恐らく、余計な探索分はおおよそ無視して、[あり得る状態数]×[各状態での探索で必要な計算量]の見積もりでいいような気がしてます。

今回の場合、多分O(ポリオミノの数×N^2)になるでしょうか。

 

実装は64bit整数を使って、冪集合表現でしてみました。

stateのiビット目が1ならマス(i/N, i%N)が赤に塗ってある状態です。

 

提出コード:https://atcoder.jp/contests/abc211/submissions/24582253