Hatena::Grouptopcoder

TopCoder煮ブログ

本家ブログはこっち → http://d.hatena.ne.jp/nitoyon/

2009-02-08

HexatridecimalSum (SRM434 DIV1 Medium)

| 12:23 | HexatridecimalSum (SRM434 DIV1 Medium) - TopCoder煮ブログ を含むブックマーク はてなブックマーク - HexatridecimalSum (SRM434 DIV1 Medium) - TopCoder煮ブログ

リベンジ

実戦では「桁が上のものから Z に置き換えていくようにすればいい」という方針で時間切れだったので、続きを書いてみた。が、System Test に通らない。しばし考えて間違いだったと気づく。反例は、YZ,Z0,Z0,...,Z0 で k=1 のようなケース。Y を Z に置き換えても高々360増えるだけだが、0 を Z に置き換えたら36×(Z0の個数)増えて、360を超える。

つまり、数字ごとに増分を計算していかなきゃいけない。作戦を変更して書き直し。増分は double に格納していく。増分の比較ならばそこまで精度は細かくなくてよいだろう、と信じる。

やってみたらうまくいった。合計2時間ほど格闘してしまった。

C++1位の人を見てみる

C++1位の人のソースをみてあまりのシンプルさに驚く。

  1. numbers を全部足した文字列を計算する。
  2. 0~Y までのそれぞれを Z に変換したときの増分を文字列で持つ
  3. 増分の大きなもの(文字列の比較でOK)から k 個を 1. の結果に足していく。

ちょっとしたコツ:

  • 桁が違うとややこしいので、000 を各数字の最初に埋めておく。最後に先頭の 0 を取り除いて返す。

自分のソース

以下、自分のソース。

#include <string>
#include <vector>
#include <iostream>
#include <map>
#include <sstream>
#include <algorithm>
#include <set>
#include <numeric>
#include <math.h>
using namespace std;

struct diff{
  int c;
  double exp;
  // 降順にするために逆に比較
  bool operator <(const diff& rhs){
    return exp > rhs.exp;
  }
};

class HexatridecimalSum {
public:
  string maximizeSum(vector <string> numbers, int k) {
    diff E[36];
    for(int i = 0; i < 36; i++){ E[i].c = i; E[i].exp = 0; }

    // 最後に足しやすいように逆順にしておく
    int N = numbers.size();
    for(int i = 0; i < N; i++) reverse(numbers[i].begin(), numbers[i].end());

    // 増分を計算
    for(int i = 0; i < N; i++){
      string s = numbers[i];
      for(int j = 0; j < s.size(); j++){
        char c = numbers[i][j];
        int n = (c <= '9' ? c - '0' : c - 'A' + 10);
        E[n].exp += pow(36.0, j) * (35 - n);
      }
    }
    sort(E, E + 36);

    // 増分が多いものから Z に置き換えていく
    for(int i = 0; i < k; i++){
      if(E[i].exp == 0) break;
      int c = (E[i].c < 10 ? E[i].c + '0' : E[i].c - 10 + 'A');
      for(int j = 0; j < N; j++){
        for(int k = 0; k < numbers[j].size(); k++){
          if(numbers[j][k] == c) numbers[j][k] = 'Z';
        }
      }
    }

    // 36進数の加算
    string ret = "";
    int j = 0;
    int cur = 0;
    int carry = 0;
    while(true){
      cur = carry;
      bool f = false;
      for(int i = 0; i < N; i++){
        int s = numbers[i].size();
        if(j >= s) continue;
        f = true;
        int c = numbers[i][j];
        if(c <= '9') cur += c - '0';
        else cur += c - 'A' + 10;
      }
      if(!f && cur == 0) break;
      carry = cur / 36;
      cur %= 36;
      if(cur < 10) ret += (char)(cur + '0');
      else ret += (char)(cur - 10 + 'A');
      j++;
    }

    // 最後に反転して返す
    reverse(ret.begin(), ret.end());
    return ret;
  }
};

FindingSquareInTable (SRM434 DIV1 Easy)

| 13:53 | FindingSquareInTable (SRM434 DIV1 Easy) - TopCoder煮ブログ を含むブックマーク はてなブックマーク - FindingSquareInTable (SRM434 DIV1 Easy) - TopCoder煮ブログ

本番では混乱したまま書き始めてうまく行かなかった問題。開始座標と増分の4重ループで素直に書けた。なんと…。

上位の人のソースを読んだ感想。

  • for のループを横に連ねてタブの階層を減らしたほうがよさそうだ。
  • perfect square かの判別は (int)sqrt(1.0*n) を2乗して n と比較すればよい。
    • 自分は sqrt して modf したけど一時変数がいるのがかっこ悪いし誤差が怖い。

以下、自分のソース。

class FindingSquareInTable {
public:
  int findMaximalSquare(vector <string> table) {
    int N = table.size();
    int M = table[0].size();

    int ret = -1;
    for(int x0 = 0; x0 < M; x0++){
      for(int y0 = 0; y0 < N; y0++){
        for(int xd = -9; xd <= 9; xd++){
          for(int yd = -9; yd <= 9; yd++){
            int x = x0;
            int y = y0;

            int num = 0;
            while(x >= 0 && y >= 0 && x < M && y < N){
              num *= 10;
              num += table[y][x] - '0';
              double tmp;
              if(modf(sqrt((double)num), &tmp) == 0.0){
                ret = max(ret, num);
              }

              if(xd == 0 && yd == 0) break;
              x += xd; y+= yd;
            }
          }
        }
      }
    }
    return ret;
  }
};

nishiohirokazunishiohirokazu2009/02/08 18:43mod系がダメな理由の一つはnが0になりうるって点かと。