Hatena::Grouptopcoder

cou929のTopCoder日記

2010-04-11

SRM 466 div2 (過去問)

12:19

寝坊してしまったので参加してません. とりあえずdiv2からやりました.

Easy - LotteryTicket

4つの整数とpriceが与えられる. 4つのうち任意個を足しあわせてちょうどpriceにすることが可能かを調べる.

全組み合わせを調べるだけです.

class LotteryTicket {
public:
  string buy(int price, int b1, int b2, int b3, int b4) {
    int i, j;
    int n = 16, bitShift = 4;
    int backnotes[4] = {b1, b2, b3, b4};

    for (i=0; i<n; i++) {
      int sum = 0;
      for (j=0; j<bitShift; j++)
        if ((1 << j) & i)
          sum += backnotes[j];
      if (sum == price)
        return "POSSIBLE";
    }

    return "IMPOSSIBLE";
  }
};

Medium - LotteryCheating

最大10桁の数字(ID)が与えられる. IDの各数字は自由に書き換えられる. 約数の数が奇数となるようなIDを作るには最小で何回の書き換えが必要か.

約数の個数が奇数になるのは平方数のみです. 自分は気づくことができませんでしたが, この法則に気がつくことができれば簡単な問題です.

約数 - Wikipedia

caferilierさんの日記で, どのようにしてこの法則にたどり着いたかが書かれていて非常に参考になります.

class LotteryCheating {
public:
  string toStr(long long n) {ostringstream ss; ss << n; return ss.str();}

  string fillZero(string s, int len) {
    string ret(len, '0');
    int i, n = s.size();

    for (i=0; i<n; i++)
      ret[ret.size() - 1 - i] = s[n - 1 - i];

    return ret;
  }

  int minimalChange(string ID) {
    int ret = 10;
    long long i, j;
    int place = ID.size();
    long long n = (long long)pow(10.0, place);
    
    for (i=0; i*i<n; i++) {
      string candidate = toStr(i*i);
      int distance = 0;

      candidate = fillZero(candidate, place);

      for (j=0; j<place; j++)
        if (candidate[j] != ID[j])
          distance++;

      ret = min(ret, distance);
    }

    return ret;
  }
};

Hard - MatrixGame

要素が1, 0の2種類のみからなる行列が与えられる. この行列に対して行のスワップ・列のスワップを任意の回数どんな順番でもすることができる. 辞書順でもっとも若いものを求める.

8x8が最大のサイズ. 最大ケースでの場合の数は 8! * 8! = 1625702400 と結構大きいのでそのままでは無理です. 列のスワップのみ全パターン行って, それぞれについて行列をソートしてベストを探せば 8! 回の試行だけで済むので間に合うようになります.

途中でギブアップしtopsubmissionを見てしまったのですが, これはなんとか自力で解きたかったです.

class MatrixGame {
public:
  vector <string> getMinimal(vector <string> matrix) {
    vector <string> ret = matrix;
    vector <int> p;
    int i, j;

    for (i=0; i<matrix[0].size(); i++) p.push_back(i);

    do {
      vector <string> cur = matrix;
      for (i=0; i<p.size(); i++)
        for (j=0; j<matrix.size(); j++)
          cur[j][p[i]] = matrix[j][i];
      sort(cur.begin(), cur.end());
      if (cur < ret)
        ret = cur;
    } while (next_permutation(p.begin(), p.end()));

    return ret;
  }
};