PCK2018本選 D-賢者の円卓
問題概要
N人の賢者が円卓に座っている。それぞれの利き手側に座っている人の利き手によりその賢者の不満度が変わる。席順を調整した時の不満度の総和の最小値はいくらか。
解法
まず、問題の条件から右利きの賢者は右利きの賢者の隣に、左利きの賢者は左利きの賢者の隣に座った方が不満度が発生しないので良い。
そのため、全て右利きか全て左利きの場合は答えは0。
右利きと左利きが存在する場合には明らかに右利きと左利きが並ぶ箇所ができる。その際、不満度が発生するのは[右、左]の順番の時左利きの、逆は右利きの賢者である。円卓に並ぶという条件により、どちらも1回は発生することに注意。
そのため、入力される利き手と不満度の情報をpairの配列で持ってsortすることにより、右利きと左利きそれぞれの賢者の集合の中での不満度の最小値が分かるため、この2賢者を違う利き手の賢者と隣り合わせればよい。
これを実装して、AC。
