問題概要
英小文字からなる文字列 が与えられる。この文字列に対し、異なる二つの文字を選んで取り除く操作を繰り返し適用し、それ以上操作を適用できなくなった時点で終了する。一連の操作の完了後、 に残っている文字が 1 種類だけならば、その文字を winning letter と呼ぶ。ある に対し、どのような順序で操作を適用しても winning letter が 1 通りに定まるとき、その winning letter を happy letter と呼ぶ。
与えられた文字列 に於ける happy letter を求めよ。存在しない場合は '.' で示せ。
解法
文字列長を と書きます。
ある文字 を仮定したときに が happy letter か否かを求めることができれば、 を全通り試すことで答えを得られます。文字 が happy letter か否かを判定するために、文字列中に文字が出現する回数に着目します。 の出現回数が、その他の文字の出現回数の総和以下のとき、 を全て消し去ることができるので は happy letter ではありません。そうでないとき、どのような順序で操作しても が 1 つ以上残るので、 は happy letter であると言えます。従って、 の出現回数を とすれば、 が happy letter である必要十分条件は と書けます。なお、複数の文字が同時にこの条件を満たすことはありません。従って、 と置く文字を全通り試して、条件を満たすものを発見したらそのときの を return することで happy letter を調べられます。そのような文字が存在しない場合は '.' を return します。
コード
#define ALL( c ) (c).begin(), (c).end() class HappyLetterDiv2 { public: char getHappyLetter( string letters ) { const int L = letters.size(); for ( char c = 'a'; c <= 'z'; c++ ) { if ( L / 2 < count( ALL( letters ), c ) ) { return c; } } return '.'; } };