IOI 2008-day1 Type Printer

問題文 : 活字印刷機

解法 :
Trie 木上の探索を行う. 最も長い文字を最後にたどれば, その文字の文の型を回収しなくていいため最短ですべての文字を打ち終えることが出来る. (他の文字はどのみち回収しないといけないため).

コード :

#include <cstdio>
#include <cstdlib>
#include <vector>
#include <algorithm>
     
using namespace std;
     
struct Trie {
    vector<pair<char, Trie *> > next;
    char len;
    bool end;
    Trie(){
		len = 1; end = false;
    }
};
     
Trie *root;
     
void insert(Trie *p, char *q)
{
    for (int i = 0; q[i]; i++){
		bool f = false;
		for (int j = 0; j < p->next.size(); j++){
			if (p->next[j].first == q[i]){
				//printf("next node %c\n", q[i]);
				p = p->next[j].second;
				f = true;
				break;
			}
		}
		if (!f){
			//printf("added %c\n", q[i]);
			p->next.push_back(make_pair(q[i], new Trie));
			p = p->next[p->next.size() - 1].second;
		}
	}
    p->end = true;
}
     
vector<char> res;
     
char getLen(Trie *p)
{
    p->len = 1;
    for (int i = 0; i < p->next.size(); i++){
		p->len = max(p->len, (char)(getLen(p->next[i].second) + 1));
    }
		return (p->len);
}
     
int N;
int done;
     
void getAns(Trie *p, char c)
{
	if (c != '$'){
		res.push_back(c);
    }
    if (p->end){
		res.push_back('P');
		done++;
    }
    for (int i = 0; i < p->next.size(); i++){
		if (p->next[i].second->len + 1 != p->len) getAns(p->next[i].second, p->next[i].first);
    }
    for (int i = 0; i < p->next.size(); i++){
		if (p->next[i].second->len + 1 == p->len) getAns(p->next[i].second, p->next[i].first);
    }
    if (c != '$' && done != N) res.push_back('-');
}
     
int main()
{
    scanf("%d", &N);
    root = new Trie;

    for (int i = 0; i < N; i++){
		char s[32];
		scanf("%s", s);
		insert(root, s);
    }
	
    getLen(root);
    getAns(root, '$');
    printf("%d\n", res.size());
    
	for (int i = 0; i < res.size(); i++) printf("%c\n", res[i]);
    
	return (0);
}