Facebook Hacker Cup 2016 Qualification Round 40:Text Editor

問題

https://www.facebook.com/hackercup/problem/1525154397757404/

問題概要

全部でT個のテストケースがある。
各テストケースではN個の単語のうちK個を印刷したい。
今与えられているテキストエディタでは以下の操作を行うことができる。
・一文字打つ
・(右端の)一文字を消す。バックスペースに相当
・印刷する
K単語印刷したら必ず今画面に表示されている文字をすべて消すことも考慮した時、最小何回の操作を行えばよいか

ただし、各テストケースの総文字数は高々である。

解法

まず、与えられた単語から以下の様なtrie木を作成する。(赤ノードが単語の終了位置を示している。)

そうすると、文字を一文字打つという操作は根から葉に向かって移動し、文字を一文字消すという操作は根に向かって移動することになる。また、tire木は木なので、根からある単語の末尾に行くまでの道筋は一通りしかなく、行きと帰りで2回ノード間を移動しなければならないので、移動したエッジの数×2+Kを出力すればよい。(最後にK回足しているのは印刷するという操作がK回発生するから)
あとはエッジの向きをすべて反転させ、トポロジカル順序に従って動的計画法を行っていけば答えを出すことができる。
dpテーブルは具体的に、dp[pos][k] := ノードposにいる時、採用した単語の数がk個になるようにした時のエッジの合計値の最小値となるようにすればよい。
今見ているノードの親ノードの子ノードの数が2以上の場合、
dp[nextPos][l]とdp[pos][k]を考慮しなければならず、lとkがそれぞれ最大でKであるのでO()かかってしまいますが、そのようなposは高々N個しかない(trie木に単語を生やすたびにそのようなノードが高々1つしか発生しない)ので、全体の計算量としてはO()となります。
また、実装に依ると思いますが、dp[pos][*]から更新できる更新先の更新は最後にまとめて行わないと更新した値を使ってさらに更新する、といったおかしなことが起こります。

ソース

#include <iostream>
#include <map>
#include <cmath>
#include <queue>

using namespace std;

#define INF 100000000

typedef long long int LL;

void printAns(int testcase, LL ans){
  printf("Case #%d: %lld\n", testcase, ans);
}

#define MAX_T 105
#define MAX_K 305
#define MAX_N 305
#define MAX_ALL_N 100005

int T, K, N;

string inputStr[MAX_N];

class nodeClass{

public:

  int nextPos['z' - 'a' + 1];
  int prePos;
  int reafNodeCnt;
  bool reafNode;
  char posChar;
  int pos;
  int nextPosCnt;
  int mirrorNextPosCnt;
  
  nodeClass(){
    init();
  }

  void init(){
    reafNodeCnt = 0;
    memset(nextPos, -1, sizeof(nextPos));
    prePos = -1;
    posChar = 'Z'; pos = 0;
    nextPosCnt = mirrorNextPosCnt = 0;
    reafNode = true;
  }

  void printDebug(){
    cerr << pos << " " << posChar << " " << prePos << " reafNodeCnt:" << reafNodeCnt << endl;
  }
  
};

class nodeManagerClass{

public:
  
  static int mNewNodeNum;
  nodeClass node[MAX_ALL_N];
  int topologyIndex[MAX_ALL_N];
  int topologyIndexSize;
  
  nodeManagerClass(){
    init();
  }

  void init(){
    mNewNodeNum = 1;
    for(int i = 0; i < MAX_ALL_N; i++){
      node[i].init();
    }
  }

  int newNode(){
    mNewNodeNum++;
    return mNewNodeNum - 1;
  }

  void updateNode(string str){
    
    int pos = 0;
    
    for(int strPos = 0; strPos < (int)str.length(); strPos++){
      if(node[pos].nextPos[str[strPos] - 'a'] != -1){
	pos = node[pos].nextPos[str[strPos] - 'a'];
      }
      else{
	int newNodeNum = newNode();
	node[pos].nextPos[str[strPos] - 'a'] = newNodeNum;
	node[pos].reafNode = false;
	node[pos].nextPosCnt++;
	node[pos].mirrorNextPosCnt++;
	node[newNodeNum].prePos = pos;
	node[newNodeNum].posChar = str[strPos];
	node[newNodeNum].pos = newNodeNum;
	pos = newNodeNum;
      }

      if(strPos == (int)str.length() - 1){
	node[pos].reafNodeCnt++;
      }
      
    }

  }

  void calcTopology(){

    topologyIndexSize = 0;

    for(int i = 0; i < mNewNodeNum; i++){
      if(node[i].nextPosCnt == 0){
	
	int pos = i;
	while(node[pos].nextPosCnt == 0){
	  topologyIndex[topologyIndexSize++] = pos;
	  pos = node[pos].prePos;
	  node[pos].nextPosCnt--;
	}

      }
    }

  }

  void allPrint(int len = 10){

    for(int i = 0; i < len; i++){
      node[i].printDebug();
    }

  }

  void topoPrint(){
    for(int i = 0; i < topologyIndexSize; i++){
      cerr << topologyIndex[i];
      if(i < topologyIndexSize - 1)
	cerr << "->";
    }
    cerr << endl;
  }

}nodeManager;

int nodeManagerClass::mNewNodeNum = 0;
int dpK[MAX_ALL_N];
int dp[MAX_ALL_N][MAX_K];

void init(){
  nodeManager.init();
  for(int i = 0; i < MAX_ALL_N; i++){
    for(int j = 0; j < MAX_K; j++){
      dp[i][j] = INF;
      if(j == 0)
	dp[i][j] = 0;
    }
  }
}

typedef pair<int, int> II;

int main(){

  cin >> T;

  for(int testcase = 1; testcase <= T; testcase++){
    
    init();
    cin >> N >> K;
    for(int i = 0; i < N; i++){
      cin >> inputStr[i];
      nodeManager.updateNode(inputStr[i]);
    }

    nodeManager.calcTopology();

    memset(dpK, 0, sizeof(dpK));
    for(int i = 0; i < nodeManager.topologyIndexSize - 1; i++){
      int pos = nodeManager.topologyIndex[i];
      if(nodeManager.node[pos].reafNodeCnt > 0){
	dpK[pos]++;
      }
      dpK[nodeManager.node[pos].prePos] += dpK[pos];
    }

    for(int i = 0; i < nodeManager.topologyIndexSize - 1; i++){
      
      int pos = nodeManager.topologyIndex[i];
      int nextPos = nodeManager.node[pos].prePos;
      
      queue<II> que;

      //posのノードまでの採用単語数がk
      for(int k = dpK[pos]; k >= 0; k--){

	if(nodeManager.node[pos].reafNodeCnt > 0 &&
	   k > 0){
	  dp[pos][k] = min(dp[pos][k], dp[pos][k-1]);
	}
	
	if(dp[pos][k] == INF)
	  continue;

	//今見ているノードの親ノードの子ノードの数が1個の時
	if(nodeManager.node[nextPos].mirrorNextPosCnt < 2){
	  //そのまま
	  que.push(II(min(dp[nextPos][k], dp[pos][k] + 1),k));
	}
	//移動先が2以上の入次数を持っている場合は
	//計算する
	else{
	  for(int l = dpK[nextPos] - dpK[pos]; l >= 0; l--){
	    if(dp[nextPos][l] == INF)
	      continue;
	    if(k > 0){
	      //更新は最後にまとめて行わないとバグる
	      que.push(II(min(dp[nextPos][l+k], dp[nextPos][l] + dp[pos][k] + 1),l+k));
	    }
	    
	  }
	}

      }

      while(que.size()){
	II q = que.front();
	que.pop();
	dp[nextPos][q.second] = min(dp[nextPos][q.second], q.first);
      }

    }

    printAns(testcase, dp[0][K]*2 + K);
    
  }
  

  return 0;

}