Atcoder水色精進記録
ABC222
E - Red and Blue Tree
https://atcoder.jp/contests/abc222/tasks/abc222_e
アルゴリズム・データ構造
BFS,DP
考察
AiからAi+1の最短経路の間に通る辺はBFSによって求めることが出来る。
各iについて上記を実施して、各辺がi=1-M-1までの通る回数をカウントしておく。
辺の通る回数がわかれば、辺を一つずつDPをすればいけそう。
DPとしては現在の辺i、現在までの赤色トータル分の配列で、格納する値は塗り方の個数
現在までの赤色トータル分のmax値は、BFSで求められるトータルの辺の個数なので
(M-1)*N→M*N
DPのトータル計算量は
M*(M*N)=M**2*N
最終的に求めたい値は
R-B=KとなるDP[N-1][R]だが
R+B=S(BFSで求められる辺の個数の総和)
なのでR=(K+S)/2となる、Rが少数/0未満の場合は、組み合わせとしてあり得ない
S＝0となるinputもあるのでdpの配列外参照に注意が必要
提出
感想
DPに配列外アクセスは注意すること。
このレベルの問題をコンテスト中に解けるようになりたい。