Hatena::Grouptopcoder

cou929のTopCoder日記

2009-12-10

SRM445 div2 (過去問)

15:42

Easy - TheEncryptionDivTwo

文字列を暗号化する. 方法はアルファベットごとに, 別のアルファベットにマップする. 暗号化後の文字列のうち, 辞書順でもっとも早いものを返す.

引数を頭からみていき, 新しいアルファベットが出たら新しい暗号化後のアルファベットを割り振ります.

class TheEncryptionDivTwo {
public:
  string encrypt(string message) {
    string ret;
    map <char, char> m;
    int counter = 0;

    for (int i=0; i<message.size(); i++)
      if (m.find(message[i]) != m.end()) {
        ret += m[message[i]];
      } else {
        m[message[i]] = 'a' + counter++;
        ret += m[message[i]];
      }

    return ret;
  }
};

Medium - TheNewHouseDivTwo

2次元座標形上の点がいくつか与えられる. 上下左右に最低一つの点が存在するような位置はいくつあるか.

これもそのままやるだけです. 途中うっかりインデックスを間違えて10分位つまってしまいました.

class TheNewHouseDivTwo {
public:
  int count(vector <int> x, vector <int> y) {
    int ret = 0;

    for (int i=-100; i<=100; i++)
      for (int j=-100; j<=100; j++) {
        bool flg[4] = {false, false, false, false}; 
        for (int k=0; k<x.size(); k++) {
          if (x[k] == i && y[k] > j)
            flg[0] = true;
          if (x[k] == i && y[k] < j)
            flg[1] = true;
          if (x[k] > i && y[k] == j)   // ここを if (x[k] > j && y[k] == j) としてしまっていた
            flg[2] = true;
          if (x[k] < i && y[k] == j)
            flg[3] = true;
        }
        if (flg[0] && flg[1] && flg[2] && flg[3])
          ret++;
      }

    return ret;
  }
};

Hard - TheLockDivTwo

次のビット列の変換ルールが与えられる. 変換できるのは任意個の0または1のどちらかのみで, 辞書順にはやいほうから並ぶ. 例えば4桁のビット列の場合は, "0000", "0001", "0011", "0010", "0110", "0100" となる. このルールでn桁のビット列を生成したとき, k番目の値を返す.

nが高々10なので, うまくやれば0-kまで順に調べ, k番目の値を返すだけで良さそうです. ビット列の生成は使用済みの値を保存しておいて, あとは 0 - (1 << n)までループし, それがルールにのっとっているかを調べるようにしました. 値のチェックは, はじめビットの値の変化は必ず1つずつという勘違いをしてしまっていたので, XORをとってたっているビット数が1ならばokとしていたのですが, 変化するビット数は1とは限らないためダメです. ほかのひとのコードを見てみると, "(a & b) == a || (a & b) == b" というふうにチェックしていました. たしかにこれだと, 片方の値のみを変化させるという条件をチェックできますが, 思いつきませんでした.

class TheLockDivTwo {
public:
  int N;

  string toStr(int n) {
    string ret;
    for (int i=0; i<N; i++)
      if (n & (1 << i))
        ret += '1';
      else
        ret += '0';
    reverse(ret.begin(), ret.end());
    return ret;
  }

  bool ok(int a, int b) {
    if ((a & b) == a || (a & b) == b) // はじめは if (__builtin_popcount(a ^ b) == 1) としていた
      return true;
    return false;
  }

  string password(int n, int k) {
    bool used[(1 << n)];
    int pre = 0;
    N = n;
    memset(used, false, sizeof(used));
    used[0] = true;

    for (int i=1; i<k; i++)
      for (int j=0; j<(1 << n); j++)
        if (!used[j] && ok(pre, j)) {
          pre = j;
          used[j] = true;
          break;
        }

    return toStr(pre);
  }
};