ARC 101-200/ARC198C - Error Swap - 競技プログラミング用 知識集積所

---

問題

ARC198C

必要知識

簡単な内容は省略

考え方

個数が小さいものから考えてみる。

まず、nが2の場合。
入れ替え方法は1つしかない。
そして、それを繰り返すと、

回数	vector
0回	10	20
1回	19	11
2回	10	20

となり、2回で元に戻ってしまう。
つまり、元々一致している場合と、1回で一致する場合は可能で、それ以外は不可能。

次に、nが3の場合。

回数	vector
0回	10	20	30
1回	19	11	30
2回	29	11	20
3回	29	19	12
4回	11	19	30

この手順で、a.at(0)を1減らして、a.at(1)を1増やすことができる。
逆に、

回数	vector
0回	10	20	30
1回	29	20	11
2回	29	10	21
3回	20	10	30
4回	9	21	30

この手順で、a.at(0)を1増やして、a.at(1)を1減らすことができる。
ということで、あとは何らかの方法でa.at(2)をあわせる方法があれば解決する。

ある場所の値を一気にm個前に戻してから1つずつ後ろに戻すと、元の位置に戻ったときに値がm-1増える。
ある場所の値を1つずつ前にm回動かしてから一気に元の位置に戻すと、値がm-1減る。
これを利用すれば、a.at(2)を合わせることができる。
というか、nが4以上の場合にも後ろから順に合わせていけば、先頭の2個だけの問題にできる。
そこからa.at(1)を前述の方法であわせ、残ったa.at(0)の値がそろっているかでYes/Noを判断すればいい。

残る心配は31000回の制限を超えないかどうか。
m-1加算減算するときに可能な限り遠くを利用して値の変化を平均していけば、vector内のどこかの値が飛びぬけて大きくなったりはしない。
よって、1つあたり310回以内の制限には余裕で間に合う。

解答例

解答例

注意点

別解

他の構成方法

多分、構成方法はいくらでもある。