IOI 2008 Egypt過去問 TYPE PRINTER

問題概要

スタックが1個あって、次の3つの操作が許されている。

• 文字を1つpush
• 文字を1つpop
• スタックの底から頂点までをなぞって文字列を印字する

さて、N個の文字列が与えられるので、上の3つの操作をできるだけ少ない回数だけ使ってこれらの文字列を全て印字したい(順番は問わないし、最後の文字列を印字した後にスタックに文字が残ってても構わない)。最適な操作列を求めよ。

• 1 <= N <= 25000
• 1 <= 各文字列の長さ <= 20

解法

Trieを作って辿る。一番深い部分木を最後に辿れば操作回数が最小になる。

ソース

DFSがなかなか汚い。

#include<cstdio>
#include<vector>
#include<algorithm>

using namespace std;

struct trie {
  struct node {
    int cnt;
    bool leaf;
    char chr;
    node* next[26];
    node() {
      leaf = false;
      chr = '\0';
      cnt = 0;
      for(int i=0; i<26; ++i)
        next[i] = NULL;
    }
  };
  int printed, N;
  node* root;
  trie(int words) : root(new node()), N(words), printed(0) { }
  void insert(char* s) {
    node* p = root;
    while(*s) {
      if(p->next[*s-'a'] == NULL)
        p->next[*s-'a'] = new node();
      p = p->next[*s-'a'];
      p->chr = *s;
      s++;
    }
    p->leaf = true;
  }
  void dfs1(node* p) {
    p->cnt = 1;
    for(int i=0; i<26; ++i) {
      if(p->next[i] != NULL) {
        dfs1(p->next[i]);
        p->cnt = max(p->cnt, p->next[i]->cnt+1);
      }
    }
  }
  void dfs2(node* p, vector<char>& x) {
    if(p->chr != '\0')
      x.push_back(p->chr);
    if(p->leaf) {
      x.push_back('P');
      printed++;
    }
    for(int i=0; i<26; ++i)
      if(p->next[i] != NULL && p->cnt-1 != p->next[i]->cnt)
        dfs2(p->next[i], x);
    for(int i=0; i<26; ++i)
      if(p->next[i] != NULL && p->cnt-1 == p->next[i]->cnt)
        dfs2(p->next[i], x);
    if(p->chr != '\0' && printed < N)
      x.push_back('-');
  }
  void dfs1() {
    dfs1(root);
  }
  void dfs2(vector<char>& x) {
    dfs2(root, x);
  }
};

int main()
{
  int N;
  scanf("%d", &N);
  trie T(N);
  for(int i=0; i<N; ++i) {
    char str[32];
    scanf("%s", str);
    T.insert(str);
  }
  vector<char> res;
  T.dfs1();
  T.dfs2(res);
  printf("%d\n", res.size());
  for(int i=0; i<res.size(); ++i)
    printf("%c\n", res[i]);
  return 0;
}