読者です 読者をやめる 読者になる 読者になる

Lilliput Steps

小さな一歩から着実に. 数学やプログラミングのことを書きます.

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);
}