リンゴ列をもっと短く！

三分木を使ってハフマン符号を構成すればよかった。
初めは出現頻度の低い方から3つをmergeしていけばよい、とか考えていたけど、
少し考えると初めにmergeするときに2つをmergeしないと最小にならない、という
ことに気づいた。

#include <iostream>
#include <cmath>
#include <algorithm>
#include <vector>
#include <map>
#include <string>

using namespace std;

map<char,string> symbols;
char rgb[] = {'r','g','b'};

class Leaf{
public:
    int cnt;
    vector<char> chars;

    Leaf(int _cnt, vector<char> _chars):cnt(_cnt),chars(_chars){}

    Leaf(){}

    bool operator <(const Leaf arg) const{
        return cnt < arg.cnt;
    }
};

int main(){
    string str;
    cin >> str;
    vector<int> times(26);
    vector<Leaf> leaves;    
    Leaf newLeaf, tmp;
    for(int i=0;i < (int)str.size();i++){
        times[str[i] - 'A']++;
    }

    for(int i=0;i<26;i++){
        leaves.push_back(Leaf(times[i], vector<char>(1, i+'A')));
    }

    while((int)leaves.size() > 1){
        sort(leaves.rbegin(), leaves.rend());
        newLeaf = Leaf(0, vector<char>());
        int loopCount = leaves.size() % 2 ? 3 : 2;
        cerr << "merge: {";
        for(int i=0;i<loopCount;i++){
            tmp = leaves.back();
            leaves.pop_back();
            newLeaf.cnt += tmp.cnt;
            for(int j=0;j<(int)tmp.chars.size();j++){
                cerr << " " << tmp.chars[j] << " ";
                symbols[tmp.chars[j]] += i+'0';
                newLeaf.chars.push_back(tmp.chars[j]);
            }
            if(i != loopCount - 1) cerr << "} and {";
        }
        cerr << "}" <<endl;
        leaves.push_back(newLeaf);
    }
    map<char,string>::iterator it = symbols.begin();

    while(it != symbols.end()){
        string str = (*it).second;
        cout << (*it).first << ":";
        for(int i=str.size();i>=0;i--){
            cout << rgb[str[i]-'0'];
        }
        cout << endl;
        ++it;
    }
}