TopCoder SRM407 Div2 500Pts

このTopCoderの問題はこちらで見ることができる(要TopCoder登録 & 問題文は英語)。問題文について意訳で説明する。

あなたは巨大な会社の人事部で働いている。各労働者は、、直属の上司と直属の部下のどちらかが常にいる(両方いることもある)。もちろん、部下は部下を持つこともあるし、上司はさらに上司を持つ頃もある。XがYのボスであるとは、雇用者A、B、...、Dがおり、XがAの上司、AがBの上司、...、DがYの上司であることをいう。もちろん、XがYの直属の上司である場合もXはYのボスになる。もし、AがBのボスである場合、BはAのボスにはなれないものとする。新しい会社の方針によると、部下のいない労働者の給与は1である。もし、部下を持つ労働者がいれば、その人の給与は直属の部下の給与の合計になる。

relations[]というi番目の文字列のj番目の要素がYであれば、iがjの直属の上司であることを表すというような文字列が与えられたとき、全労働者の給与を返すようなメソッドを作成せよ。なお、Yでない位置の文字列の内容はNになる。自身は自身の上司にならないので、i番目の文字列のi番目の要素は必ずNになる。

私の解答はこちら。再帰を用い、各労働者が何人の部下を持つかを見つけるようにしています。

public class CorporationSalary {

 public long totalSalary(String[] relations) {
  long total = 0;
  long[] salary = new long[relations.length]; // 給与は0で初期化しておく
  for( int i=0 ; i<relations.length ; i++ ){
   total += calc_salary(relations, i, salary);
  }
  return total;
 }
 // i番目の人の給与を計算する関数
 // salary[]は給与を記録するためのテーブルと思ってよい
 private long calc_salary(String[] relations, int i, long[] salary){
  if( relations[i].indexOf("Y") < 0 ){
   return 1; // 部下がいない場合
  }
  long total = 0;
  long ret = 0;
  for( int j=0 ; j<relations[i].length() ; j++ ){
   if( relations[i].charAt(j) == 'Y' ){ // 部下がいた場合
    // 0でないということは給料が分かっている場合、その人の給与は計算済み、既知である
    if( salary[j] > 0 ){
     total += salary[j];
    }else{
     ret = calc_salary(relations, j, salary); // 再帰処理
     total += ret;
     salary[j] = ret; // j番目の人の給料をセット
    }
   }
  }
  return total;
 }
}

得点は150.0/500、何度もトライしました。再帰で時間がかかりすぎるというのが問題の原因だったので、計算結果を途中で入れるようにして解決。これにより2秒で処理が終わらなかったテストケースが、4msecで終わるようになりました。