問題：C - 錬金術士
解答：Submission #11032114 - CODE FESTIVAL 2014 予選B
解法：まず、各文字種('A' - 'Z')について、S1内の個数とS2内の個数の和がS3内の個数より小さいものがあれば、NOを出力。全ての場合でそうでないなら、「S1から何個、S2から何個」という個数を気にしなければS1とS2からS3を作れることになる。
次に、S1とS2からそれぞれちょうどN/2個ずつ文字を取り出すという条件を考える。例えば文字AがS1に2個、S2に4個、S3に5個ある場合に、S1とS2から最低何個ずつ取り出す必要があるかを考える。これは対になる文字から最大限の取り出しがあった場合を考えると、文字S1からは5-4=1で最低1個、S2からは5-2=3で最低3個のAを取り出す必要があることになる。よって、S1とS2についてこの最低限取り出す必要のある文字数をチェックし、その数がどちらかでもN/2を超えていれば、NOを出力する。そうでないなら、必ずS3を生成できる。これを次で示す。
S1から最低限取り出す文字数をm1、S2のそれをm2とする。このときm1 + m2 < N / 2 + N / 2 = Nであるが、残りのN - m1 - m2個の文字はS1からもS2からも取り出すことができる文字である。よってそのうちN / 2 - m1個をS1から取り出し、N / 2 - m2個をS2から取り出せばよい。
