Hatena::Grouptopcoder

cou929のTopCoder日記

2009-12-03

SRM429 div2 (過去問)

15:24

Easy - LinearPolyominoCovering

"..XXXX..XX...XXXXXX.."このような文字列が与えられるので,"X"の部分を,"AAAA"か"BB"で置き換えて返す.その際,辞書順で早いものを返す.不可能なら"impossible"を返す.先の例だと答えは"..AAAA..BB...AAAABB.."となる.

つながっているXの数が奇数なら"impossible"そうでないなら,できるだけ"AAAA"を優先して挿入する.という方法で書いたのですが,非常に時間がかかってしまいました.スコアも180点台です.

class LinearPolyominoCovering {
public:
  string findCovering(string region) {
    string ret;
    
    for (int i=0; i<region.size(); i++) {
      if (region[i] == 'X') {
        int counter = 0;

        for (int j=i; j<region.size(); j++) 
          if (region[j] == 'X')
            counter++;
          else
            break;

        if (counter % 2 != 0)
          return "impossible";

        int anum = counter / 4;
        int bnum = counter % 4;

        for (int j=0; j<anum; j++)
          ret += "AAAA";
        for (int j=0; j<bnum; j++)
          ret += "B";

        i += counter-1;
      } else if (region[i] == '.') {
        ret += ".";
      }
  
    }
    return ret;
  }
};

Medium - SubrectanglesOfTable

問題文は省略.非常に時間がかかりました.たぶん一時間以上.

"全ての矩形をカウントした場合,tableの各位置は何回出現するか"を考えます.例えば,2x2のtableを考えます.文字は仮に以下のようになっているとします.(問題の条件からはありえません)

AB
CD

この場合,全ての矩形は,

AB AB .. A. .B A. .B .. ..
CD .. CD C. .D .. .. C. .D

ここで,各数字の出現頻度は,以下のようにすべて4回です.

4 4
4 4

この値には,次のような法則があります.

MxNの大きさのtalbeのi, j要素の値は,(大きさMx1のtableのi番目の要素の値) * (大きさNx1のtalbeのj番目の要素の値)

図で表すとこんな感じです.

f:id:cou929:20091203151620j:image

この法則に従って,各位置のアルファベットの出現回数をカウントすれば,答えが出ます.

次にNx1のtableの値の求め方です.次のような法則があります.例えばN=5の場合,

1番目: 5 = 1 + 1 + 1 + 1 + 1
2番目: 8 = 1 + 2 + 2 + 2 + 1
3番目: 9 = 1 + 2 + 3 + 2 + 1
4番目: 8 = 1 + 2 + 2 + 2 + 1
5番目: 5 = 1 + 1 + 1 + 1 + 1

以上を実装したのが以下のコードです.デバッグに非常に時間がかかりました.他の人のコードはもっと全然短かったので,もっとスマートな方法があるはずです.

class SubrectanglesOfTable {
public:
  vector<long long> getQuantity(vector <string> t) {
    vector <long long> ret(26, 0);
    vector <int> row;
    vector <int> col;

    // talbeを作る
    vector <string> table;
    for (int i=0; i<t.size()*2; i++)
      if (i < t.size()) {
        string line = t[i];
        line += t[i];
        table.push_back(line);
      } else {
        table.push_back(table[i - t.size()]);
      }

    // 縦方向(talbe.size() x 1 の大きさ)のtableの数列を作る
    int center = table.size() / 2;
    if (table.size() % 2 == 1)
      center++;
    for (int i=0; i<table.size(); i++) {
      if (i < center) {
        vector <int> nums;
        for (int j=0; j<table.size(); j++)
          if (j < center)
            nums.push_back(min(i, j) + 1);
          else
            nums.push_back(nums[table.size() - 1 - j]);

        int num = 0;
        for (int j=0; j<nums.size(); j++)
          num += nums[j];
        col.push_back(num);
      } else {
        col.push_back(col[table.size() -1 - i]);
      }
    }

    // 横方向(talbe[0].size() x 1 の大きさ)のtableの数列を作る
    center = table[0].size() / 2;
    if (table[0].size() % 2 == 1)
      center++;
    for (int i=0; i<table[0].size(); i++) {
      if (i < center) {
        vector <int> nums;
        for (int j=0; j<table[0].size(); j++) {
          if (j < center)
            nums.push_back(min(i, j) + 1);
          else
            nums.push_back(nums[table[0].size() - 1 - j]);
        }

        int num = 0;
        for (int j=0; j<nums.size(); j++)
          num += nums[j];
        row.push_back(num);
      } else {
        row.push_back(row[table[0].size() -1 - i]);
      }
    }

    // 頻度のカウント
    for (int i=0; i<table.size(); i++)
      for (int j=0; j<table[0].size(); j++) {
        ret[table[i][j] - 'A'] += (long long)col[i] * (long long)row[j];
      }

    return ret;
  }
};