ABC-D 69-71
今日は3問だけ。
ABC69
縦に並べていって、なくなったら横にずれてまた縦に逆方向。
1 2 3 5 5
1 2 4 4 6
2 2 4 4 6
塗る順で1Dに書くと 1 1 2 2 2 2 3 4 4 4 4 5 5 6 7
ai個のiを順に1Dに書いて、2Dになるように読み出せばいい。
rep(i,h*w){
if(i/h %2==0){
ans[i%h][i/h] = color[i];
}else{
ans[h-1- i%h][i/h] = color[i];
}
}
ABC70
K始点でダイクストラしてdist[a]+dist[b]するだけ。
ABC71
左から i 列目がどうなっているか。
i-1が横向きドミノの二列目で
a
b
のとき、右側にあり得るのは
ac
bc
abb
baa
acc
baa
abb
の4通りで、後ろ３つは色の入れ替えで同値。
a
a
の時
ab
ab
ac
ac
abb
acc
acc
abb
の4通りで、前２つ、後ろ２つはそれぞれ同値。
横ドミノ1列目だったらそのまま。
結局i+1列目の塗り方は、
i 列目が横1ならi列目までと同じ。
i 列目が横2でi+1列目が縦ならi列目までと同じ。
i 列目が横2でi+1列目が横ならi列目まで*3
i 列目が縦でi+1が横なら *2
i 列目が縦でi+1が縦なら *2
0列目については、横なら6通りで縦なら3通り。
