ARC069 D Menagerie
所見
Submission #3770946 - AtCoder Regular Contest 069
固定すると見通しが良くなるシリーズ
問題概要
N匹のどうぶつが輪になっている状態を考える。羊は左右のどうぶつが同じ種類の時'o'、違う種類の時'x'と答え、狼はその逆を答える。N文字の'o' or 'x'からなる解答列が与えられたとき、それを満たすどうぶつの列が存在するならその列を、しないなら-1を出力せよ。
取った方針
羊も狼も左右のどうぶつを参照して答えを出すので、最初の2匹を固定するとN匹の動物がすべて確定する。このようにして確定させたとき、1番目とN番目の動物のみ与えられた解答列を満たすことをチェックしていないのでチェックする。この操作を"羊羊" "羊狼" "狼羊" "狼狼" が最初の2匹となるパターンについて全部試せばよい。
正しい方針
同上
得られた知見
- 何かを固定するとうまくいくシリーズ
- 類題として1変数を固定するとほかの変数がすべて決まるのでそれを全探索するものなどがある
解くのに必要な要素
- ある位置のどうぶつの種類はその左もしくは右の2つのどうぶつにより決定されるという気づき(DP っぽい)
周辺調査によって得られた知見
特になし