AtCoder Grand Contest 012 D - Colorful Balls
ボールが一列に並んでいる。異色の場合、重さの合計がY以下なら任意の2個を入れ替えることができる。同色の場合、重さの合計がX以下なら任意の2個を入れ替えることができる。色の並び順として何通りあるか？
自力で解けなかった。考察ではAとBが交換可能かつBとCが交換可能ならAとCが交換可能ということで、互いに任意の2個が交換可能な集合が元のボールの部分集合になるというところまで出来た。ただし、そのような部分集合で元が2個以上あるものはたかだか1個しかない、というところまで考察がいかなった。とりあえず以下ではそのような部分集合をXとおく。
さて、そのような考察ができた場合、同色であればその色の中で重さが最小のボールとの関係だけを考えればよい。異色であれば重さが最小のボール及び、そのボールと色が異なる次に重さが最小のボールの2個との関係だけを考えれば良い(色が2種類あることで、同色の場合は2番めに最低のものと比較してXに含まれるかどうかを判断すればよい)
そのような部分集合が特定できたら、その中での色の並び替えの総数が答えになる。
