SRM 545

Single Round Match 545 Round 1

http://community.topcoder.com/stat?c=round_overview&er=5&rd=14737

所用で参加できず。練習。

250に13分。550は2日間ほど考えた。

Problem Status Points
250 ANDEquation Opened 213.55
550 StrIIRec Opened N/A
1000 SpacetskE Unopened

ANDEquation

http://community.topcoder.com/stat?c=problem_statement&pm=12029&rd=14737

13分。213.55点。

  • AND演算を繰り返すとビットがどんどん寝ていくのをイメージした
    • ならば、ビット数が一番少ない数値が答えの候補だ
    • まずビットをカウントするメソッドを書こう
    • bitcountを書いた
      • 初め、反復の終了条件をi < nとして動かなかった
  • 数値とビット数をstd::pairとし、ビット数で整列する
    • 初めの数値とそれ以降の数値のANDを取ったものが等しければ、それが正解だ

実装は以下(システムテスト済)。

class ANDEquation {
public:
  int restoreY(std::vector<int> A) {
    int size = A.size();

    std::vector<std::pair<int, int> > pairs;

    EACH(it, A)
      pairs.push_back(std::make_pair<int, int>(bitcount(*it), *it));

    std::sort(ALL(pairs));

    int r = pairs[1].second;

    for (int i = 2; i < size; i ++)
      r &= pairs[i].second;

    if (r == pairs[0].second) {
      return pairs[0].second;
    }
    else {
      return -1;
    }
  };

private:
  int bitcount(int n) const {
    int c = 0;

    for (int i = 1; i <= n; i <<= 1)
      if (n & i)
	c ++;

    return c;
  };
};
  • あ
    • ビット数が同じ候補がある場合を考えていなかった
    • 011と101等
    • んー
      • ああ、この場合解はないのか
      • 助かった
  • 今考えるに、bitcountの実装は以下でもよいか
    • こちらのほうが反復の終了条件を間違えないように思う
  int bitcount(int n) const {
    int c = 0;

    for ( ; n; n >>= 1)
      if (n & 1)
	c ++;

    return c;
  };

StrIIRec

http://community.topcoder.com/stat?c=problem_statement&pm=12025&rd=14737

  • 2日間ほど考えていた
    • 文字列の探索は苦手な分野なので、克服したかった
    • それぞれの文字が1回しか出てこないことを読みこぼしていた
  • まず、必要とされる文字数を満たすようにした
    • 使われていない文字を末尾に、辞書順に足せばよい


  • この後が難しかった
    • 文字列を2つに分け、
      • 左の文字列の逆転数と
      • 左と右の文字列間の逆転数を足し、
      • さらに右の文字列の逆転数の最大値を足して、
    • 条件にマッチするかどうか判定すれば効率的であるように考えた
  • 例えば、cdとeabで分けた場合


  • cdは逆転なしなので0
    • 左側と右側では4(cはa、bより大きく、dもまたa、bより大きい)
    • eabは3文字なので、最大で3回逆転する
    • 全体では最大で7回逆転する
    • つまり、右側だけ全ての組み合わせを試す戦略である
  • これはうまくいかなかった
    • 以下のテストケースの逆転数が55以上であること求めている


  • 辞書順で処理した場合、求める並びに到達するのは最後
    • 最大で20!回。つまり2432902008176640000回
    • std::next_permutation等で追っていくと余裕でTLEする


  • 左側を1文字とすることで、左側の文字列の逆転数を考える必要がなくなってしまった
    • この場合、
      • 左側の1文字と右側の逆転数の2と
      • 右側の逆転数の最大値、6を足せば、
    • 左側の1文字が条件を満たしているか否か判断できる
  • 条件を満たしているのであれば、右側の文字列でまた判定をする
  • 条件を満たしていないのであれば、
    • 左側の一文字の次の文字を探索し、
    • 残りの文字を整列した文字列を右側とし
  • 同じ判定を繰り返せばよい

以下はシステムテストを通った実装。

class StrIIRec {
public:
  std::string recovstr(int n, int minInv, std::string minStr) {
    std::string s(minStr);

    for (char c = 'a'; s.size() < n; c ++)
      if (s.find(c) == std::string::npos)
	s.push_back(c);

    return search(s, minInv);
  };
  
private:
  std::string search(std::string s, int t) const {
    int size = s.size();

    if (size == 1)
      return s;

    while (1) {
      int c = 0;

      for (int i = 1; i < size; i ++)
	if (s[0] > s[i])
	  c ++;

      if (c + (size - 1) * (size - 2) / 2 >= t)
	return s[0] + search(s.substr(1), t - c);

      char t = s[0];

      std::sort(ALL(s));

      std::swap(s[0], s[s.find(t) + 1]);
    }
  };
};
  • std::stringにpush_backがあるのを知った
    • 大人になった気分だ
  • ある文字の次に大きい文字を文字列から探すのって意外に難しい
    • この問題では整列してしまってよかったので、助かっている
  • んー
    • この問題は要素群をただただ二つに分けただけではうまく行かなかった
    • 1要素と残りの要素群に分けることで問題を単純化した
    • 今後これを意識してみよう
  • あ
    • よく見ると思った通り動いていない
      • 「左側の一文字の次の文字を探索し、残りの文字を整列した文字列を右側とし」の整列ができていなかった
      • 交換しただけで終わっていた


  char t = s[0];

  std::sort(ALL(s));

  std::swap(s[0], s[s.find(t) + 1]);

  std::sort(s.begin() + 1, s.end());
  • すごく冗長な気がする
    • アセンブラでいうrotateをやりたいのだよな
    • abcdeの左側、abcdをrotate(dabcを得る)
    • その結果、dabceを得る、みたいな...
  • この問題の解法がすごく好きだ
    • 上界を計算してはまるかはまらないかを見るのが乱択アルゴリズムっぽいからかもしれない