SRM291 に挑戦．

2006 TopCoder Open - Algorithm Competition が来週の 2 月 28 日から始まります．今日は，それに向けて最後の SRM になります．

250 点問題． 折り紙で雪の結晶をつくりましょう．

このように 8 等分に折った折り紙に対して，

穴をあけてから，もとの大きさに広げると，あら不思議．雪の結晶のように，対称な，きれいな形ができますねー．あ，そう．って感じですが，，，

問題は，以下のような，8 等分に折った折り紙の穴のパターンが与えられたとき，

{"*",
 "..",
 ".*.",
 ".**.",
 ".*.**"}

広げた形のパターンを求めてください．という問題です. 例の場合は，答えはこのようになります．

{"**.*..*.**",
 "*.**..**.*",
 ".*.*..*.*.",
 "***....***",
 "....**....",
 "....**....",
 "***....***",
 ".*.*..*.*.",
 "*.**..**.*",
 "**.*..*.**" }

悩むところは特にないですが，いかに時間をかけないでサクサクすませられるか勝負です．私は，14 分もかかってしまいましたが，早い人は，3 分かからずにすませています．．

500 点問題． 素直に BFS でいけました．

1000 点問題． Level1，Level2 問題を終えた時点で，30 分ほど時間がありましたので，1000 点問題にチャレンジ．

単語(Word)がいくつか与えられます．

{"salad", "sandwich", "hamburger", "rings"}

これらの単語の最初の文字と最後の文字をつなげて，文字列をつくっていきます．

"hamburgeringsandwichamburger..."

「しりとり」ですね．こうしてできる文字列のうち，長さが (len) 以上のもので，辞書的に一番最初にくる文字列を返しなさい．という問題です．たとえば，入力が

{"abd", "dgga", "abdg", "gga", "gg", "gaader"}
len: 22

ならば，

"abdggabdggabdggabdgaader"

が答えになります．

ちょっと考え，「DP でいける！」と思い，コーディング開始. 1000 点問題をはじめて解けるか？！ と思ったのですが，時間が足りませんでした．． SRM 後，悔しいので完成させました．

public class StickedWords {

  public String constructLine(String[] dict, int len) {

      String[][] dp = new String[len+51][26];
      for (int i = 1; i < dp.length; i++) {
          for (int j = 0; j < 26; j++) {
              for (String word : dict) {
                  if (word.charAt(word.length()-1) - 'a' != j) continue;
                  if (i == word.length()) {
                      if (dp[i][j] == null || word.compareTo(dp[i][j]) < 0) {
                          dp[i][j] = word;
                      }
                      continue;
                  }
                  int pre = i - (word.length() - 1);
                  if (pre <= 0) continue;
                  int first = word.charAt(0) - 'a';
                  if (dp[pre][first] == null) continue;
                  String next = dp[pre][first] + word.substring(1);
                  if (dp[i][j] == null || next.compareTo(dp[i][j]) < 0) {
                      dp[i][j] = next;
                  }
              }
          }
      }
      String res = null;
      for (int i = len; i < len+51; i++) {
          for (int j = 0; j < 26; j++) {
              if (dp[i][j] == null) continue;
              if (res == null || dp[i][j].compareTo(res) < 0) {
                  res = dp[i][j];
              }
          }
      }
      return (res == null) ? "" : res;
  }
}

もうちょっとだったのになーと思っていたけど，実は，ぜんぜんもうちょっとではありませんでした．落とし穴がまっていました．． 最悪のケース (len=2500)では,

java.lang.OutOfMemoryError...

を引き起こしてしまいます． TopCoder では時間（2 秒以内）という制限だけではなく，使用メモリの制限 (64Mbyte)もありました． 最悪のケース (len=2500)では，最終的にはメモリ使用量は，

2500 x (2500 / 2) x 26 = 81250000

ですから，80MByte を超えますね.．．これはトリッキーだ．．普通，気づかないよな．． 1000 点問題にしてはとっかかりやすいと思ったけど，こういう側面があったとは．．こういうのは，問題作成者が意図的にやってるんですね．

ひとつあたりの単語の長さは最大 50 なので，DP をしつつ，最近の 50 ステップ分だけ，覚えるようにして，いらなくなったものには，null をいれると．

}
if (i - 51 >= 0) {
    dp[i-51] = null;
}

これで，なんとか System Test に通るようになります．

結果

System Test の結果です． ( Room Statistics )

レーティングは 1626 -> 1730 と 100 ほど上昇しました．いよいよ来週は，2006 TopCoder Open の予選です．

今日の教訓

• メモリ使用量に注意．