TopCoder SRM434 Div1 - 西尾泰和のはてなダイアリー

むー、ついに二軍に落ちてしまった。

250-points FindingSquareInTable

0〜9の数字が書かれた升目がある。x座標とy座標が等差数列になるような升目の数字をつなげて作られる数のうち、もっとも大きな平方数を返せ。ないなら-1を返せ。という問題。

  bool is_square(size_t n){
    size_t m = sqrt(n);
    if(m * m == n || (m + 1) * (m + 1) == n){
      return true;
    }
    return false;
  }

  int findMaximalSquare(vector <string> table) {
    const size_t HEIGHT = table.size();
    const size_t WIDTH = table[0].size();
    int result = -1;
    for(size_t sy=0; sy < HEIGHT; sy++){
      for(size_t sx=0; sx < WIDTH; sx++){
        for(int dx= -int(WIDTH) + 1; dx < int(WIDTH); dx++){
	  for(int dy= -int(HEIGHT) + 1; dy < int(HEIGHT); dy++){
	    if(dx == 0 && dy == 0) continue;
	    int x = sx, y = sy;
	    int seq = table[y][x] - '0';
	    if(is_square(seq) && seq > result){
	      result = seq;
	    }
	    while(true){
	      x += dx;
	      y += dy;
	      if(!(x < int(WIDTH) && x >= 0 && y < int(HEIGHT) && y >= 0)) break;
	      seq *= 10;
	      seq += table[y][x] - '0';
	      if(is_square(seq) && seq > result){
		result = seq;
	      }
	    } 
	  }
	}
      }
    }
    return result;
  }

さて、チャレンジ開始後即座に撃墜されたのでよっぽどわかりやすいポカミスがあるに違いない。Practice Roomに入ってテストしてみる。

Args:
{{"0"}}

Expected:
0

Received:
-1

ぶは。これがいけないのか。動く余地のない1x1の升目の場合はdxやdyのfor文の中に入らないから移動せずに1個だけですでに平方数になっている場合のチェックを取りこぼしているのか。修正したら通った。

500-points HexatridecimalSum

36進数で表現された数のリストが渡されるので、36種類の数字のうちk個をZに置き換えて合計を最大化し、その最大の合計を36進数で返しなさい、という問題。最初問題文を勘違いしてk=1だと思っていて、慌ててk=2以上に対応させて終了90秒前にかろうじてサブミット。

まずはk=1版

  unsigned long long from36(string s){
    char** endptr;
    return strtoull(s.c_str(), endptr, 36);
  }
  string to36(unsigned long long x){
    string ret = "";
    while(x){
      if(x % 36 < 10){
	ret = ret.insert(0, 1, char('0' + x % 36));
      }else{
	ret = ret.insert(0, 1, char('A' + (x % 36 - 10)));
      }
      x /= 36;
    }
    return ret;
  }
  string maximizeSum(vector <string> numbers, int k) {
    unsigned long long max_sum = 0;
    for(size_t i=0; i<35; i++){
      unsigned long long sum = 0;
      char query = to36(i)[0];
      for(size_t j=0; j<numbers.size(); j++){
        string tmp = numbers[j]; // copy
	for(size_t k=0; k<tmp.size(); k++){
	  if(tmp[k] == query) tmp[k] = 'Z';
	}
	DP(tmp);
	sum += from36(tmp);
      }
      if(sum > max_sum) max_sum = sum;
    }
    return to36(max_sum);
  }

いや、250より簡単だからオカシイとは思ったんだよ！
k = 2以上版に関しては、それぞれの数字の置換は独立なので、35!回の探索なんか全然必要なくて35回調べて効果の大きい順に選べばいいだけなので簡単。でもなぜかdouble freeとかそういう嫌らしいエラーが出てきたのでstrtoullの使い方が間違ってるんだろうなぁと思って自分で書き直した。

  unsigned long long from36(string s){
    //char** endptr;
    //return strtoull(s.c_str(), endptr, 36);
    unsigned long long ret = 0;
    for(size_t i=0; i<s.size(); i++){
      ret *= 36;
      if('0' <= s[i] && s[i] <= '9'){
	ret += s[i] - '0';
      }else{
	ret += s[i] - 'A' + 10;
      }
    }
    return ret;
  }

  string to36(unsigned long long x){
    if(x == 0) return "0";
    string ret = "";
    while(x){
      if(x % 36 < 10){
	ret = ret.insert(0, 1, char('0' + x % 36));
      }else{
	ret = ret.insert(0, 1, char('A' + (x % 36 - 10)));
      }
      x /= 36;
    }
    return ret;
  }

  string maximizeSum(vector <string> numbers, int k) {
    unsigned long long max_sum = 0;
    vector<pair<unsigned long long, char> > candidates;
    unsigned long long base = 0;
    for(size_t j=0; j<numbers.size(); j++){
      base += from36(numbers[j]);
    }
    
    for(size_t i=0; i<35; i++){
      unsigned long long sum = 0;
      char query = to36(i)[0];
      for(size_t j=0; j<numbers.size(); j++){
        string tmp = numbers[j]; // copy
	for(size_t k=0; k<tmp.size(); k++){
	  if(tmp[k] == query) tmp[k] = 'Z';
	}
	sum += from36(tmp);
      }
      candidates.push_back(make_pair(sum - base, query));
    }
    sort(candidates.begin(), candidates.end());
    max_sum = base;
    if(k == 36) k = 35;
    for(size_t i = 35 - k; i < 35; i++){
      max_sum += candidates[i].first;
    }
    return to36(max_sum);
  }

で、なにがまずかったのかテスト。

Args:
{{"93K7XFUCPTGJWUDCPQY9TW0Y9B7Q2PWXQUUTFEZEHIFRIB03HW", "NX73A16PXA5LUE6QUQGN7N6BU67EUBZ0OICX1KBI9FA2CL12DW", 
(中略)
"1JBNQ0CTVE9LF2V10FPIRMQC3R9IWDVD3NW6R4EOT6C3DPD57G", "SBSW40X7KMPVFRWG0NHYVZXO3NRK4RC9J9VNF1W9I1B70XBBZO"}, 18}

Expected:
"1B9KG009JCTTFOMNN3QI86HEHJENK39KL7NM34FCP3JZ7AYXF6H1"

Received:
"3ONMBDMI72QM0"

あー、はい。36進数50桁がunsigned long longに収まるはずがないですね。。おおまかなサイズの感覚を鍛えてないからこんなことになるんだ。

>>> 2 ** 64 
18446744073709551616
>>> 10 ** 19
10000000000000000000
>>> 36 ** 12
4738381338321616896
>>> 36 ** 13
170581728179578208256

ぜんぜん収まらないじゃん！みんなこれどうやってといたんだろ。36進数の加算を実装したんだろうか。JavaはBigIntegerあるからいいなぁ。

http://www.topcoder.com/stat?c=problem_solution&rm=300143&rd=13696&pm=10266&cr=22664055

うはー。本体の3倍の長さがあるstruct bignumなんか作ってある。これやっぱり事前に作っておいて必要に応じてコピペしているのかな。