Hatena::Grouptopcoder

cou929のTopCoder日記

2009-12-06

SRM454 div2

04:56

250通過, 500がシステムテストで落ち, 部屋で5位, div2で298位, ratingは1152 -> 1139 (-13). また足踏みです.

Easy - MinimalDifference

digit sum を, 整数の各数字の総和と定義する. 例えば, 1234の場合は 1+2+3+4 = 10 となる. A, B, Cの三つの整数が与えられる. A - B の範囲の整数Xのうち, Xのdigit sumとCのdigit sumの差の絶対値が最小となるXを返す. 複数の候補がある場合は, Xの値の小さいものを返す.

A - B の範囲が高々100000なので, 全探索しました.

class MinimalDifference {
public:
  int getDigitSum(int n) {
    int ret = 0;

    while (n > 0) {
      ret += n%10;
      n /= 10;
    }

    return ret;
  }

  int findNumber(int A, int B, int C) {
    int digit_sum_c = getDigitSum(C);
    int mini = INT_MAX;
    int ret = 0;
    
    for (int i=A; i<=B; i++) {
      int ds = getDigitSum(i);
      if (mini > abs(ds-digit_sum_c)) {
        mini = abs(ds-digit_sum_c);
        ret = i;
      }
      if (mini == 0)
        break;
    }

    return ret;
  }
};


Medium - WordsGame

各要素がアルファベット, 大きさnxnの二次元配列が与えられる. この配列に対して, 行/列のスワップを行うことができる. 長さnの文字列(word)が与えられるので, この文字列が行列の行方向, 列方向いずれかに一直線に並ぶようにするには, 最小で何回スワップする必要があるか.

何度スワップしても, ある行/列の要素そのものが変化することはないので(変化するのは要素の行/列内での位置のみ), wordを作ることができる行/列は, すでにwordと同じ文字を含んでいる行/列のみとなります. よって, まずそのような行/列を探し, それぞれについて何度スワップが必要かを調べ, その最小値を返します. スワップの回数は挿入ソートっぽい方法で求めました. 候補の文字列を前から順に見ていき, その文字がwordと異なっていたら正しい文字とスワップします.

と思っていたらシステムテストで落ちました. 原因は行や列, wordの中に同じアルファベットが複数回出現することを考慮していなかったことでした(なぜか勝手にword内のすべての文字は別々と思い込んでいました). スワップ回数を調べる候補の文字列を探す際に, 単にある行/列のある文字が, wordに含まれているかどうかだけで判定していたので, 同じ文字が複数ある場合は, invalidな文字列も候補に含まれてしまっていました. 対策として, 候補の文字列をソートしたものと, wordソートしたものを比べ, 同じだった場合のみ候補に加えることにしました. 悔いがのこる失敗です.

class WordsGame {
public:
  int minimumSwaps(vector <string> grid, string word) {
    vector <string> candidates;
    int ret = INT_MAX;

    string sorted_word = word;
    sort(sorted_word.begin(), sorted_word.end());
    for (int i=0; i<grid.size(); i++) {
      string s1, s2, sorted_s1, sorted_s2;
      for (int j=0; j<grid.size(); j++) {
        s1 += grid[i][j];
        s2 += grid[j][i];
      }

      sorted_s1 = s1;
      sorted_s2 = s2;
      sort(sorted_s1.begin(), sorted_s1.end());
      sort(sorted_s2.begin(), sorted_s2.end());

      if (sorted_s1 == sorted_word)
        candidates.push_back(s1);
      if (sorted_s2 == sorted_word)
        candidates.push_back(s2);
    }

    for (int i=0; i<candidates.size(); i++) {
      int swap_count = 0;

      for (int j=0; j<word.size(); j++) {
        if (word[j] != candidates[i][j]) {
          int pos = 0;
          for (int k=j+1; k<word.size(); k++)
            if (candidates[i][k] == word[j])
              pos = k;
          char tmp = candidates[i][j];
          candidates[i][j] = word[j];
          candidates[i][pos] = tmp;
          swap_count++;
        }
      }

      if (candidates[i] == word)
        ret = min(ret, swap_count);
    }

    if (ret == INT_MAX)
      ret = -1;

    return ret;
  }
};

Hard - NumbersAndMatches

マッチ棒を並べた数字が与えられる. マッチ棒をk回移動させて, 別の数字をつくる. 出来る数字はなんパターンあるか.

マッチ棒でつくられた数字は最大18個, kが最大127と, データが大きいので, 普通の探索では解けなさそうです. たぶんdpを使うんじゃないかなあと思いつつ, 良い解法が思いつきませんでした.