Hatena::Grouptopcoder

cou929のTopCoder日記

2009-12-22

SRM380 div2 (過去問)

02:37

Easy - LuckyTicketSubstring

数列の前半と後半の数字の和が等しいものをlucky ticketと呼ぶ. ある数列が与えられるので, そのサブ数列のうちlucky ticketとなるものの最大長を求める.

ふつうに全探索です. lucky ticketの中心を左から右へスライドさせて行き, nをひとつずつ増やして調べています.

class LuckyTicketSubstring {
public:
  int maxLength(string s) {
    int ret = 0;

    for (int i=1; i<s.size(); i++) {
      int left_sum = 0, right_sum = 0;
      for (int j=1; i-j >= 0 && i+j-1 < s.size(); j++) {
        left_sum += s[i-j] - '0';
        right_sum += s[i+j-1] - '0';
        if (left_sum == right_sum)
          ret = max(ret, j*2);
      }
    }

    return ret;
  }
};

Medium - LameKnight

右にしか進めないナイトが, 盤上の左下に置かれている. 盤の縦横の大きさが与えられるので, このナイトは最大何セル訪れることが出来るか. ただし最初の4手以上の場合は4種類の動き(上2右1, 下2右1,上1右2, 下1右2)のそれぞれを少なくとも一回は行わないといけない.

すごく汚らしいコードになっちゃうんですが, すべての場合をifで分岐して求めています. 縦が3マス以上, 横が7マス以上あれば, 最初に横へ2つ動く動きをして, あとはすべて横に1つ動く動きをするのが最適解になるので, そのように計算しています. それ以外の場合は, パターン数が少ないので, すべて列挙しました. こういう解法は考慮漏れをしがちなので慎重に行うべきです. 今回もシステムテストにおちちゃいました.

class LameKnight {
public:
  int maxCells(int height, int width) {
    int ret = 1;

    if (height >= 3 && width >= 7) {
      ret += 4 + width - 7;
    } else {
      if (height > 1 && width > 1 && height * width != 4) {
        if (height == 2) {
          if (width < 5)
            ret += 1;
          else if (width < 7)
            ret += 2;
          else
            ret += 3;
        } else {
          if (width == 2)
            ret += 1;
          else if (width == 3)
            ret += 2;
          else if (width < 7)
            ret += 3;
        }
      }
    }

    return ret;
  }
};