SRM 555 Div II

Single Round Match 555 Round 1

http://community.topcoder.com/stat?c=round_overview&er=5&rd=15177

255に7分。555に45分。投稿した実装の検証に時間を割いたため955は開かなかった。合計487.93点。レートは1199から1236へ。念願の青コーダー。Room 80。

Problem Status Points
255 XorBoardDivTwo System Test Passed 239.80
555 CuttingBitString System Test Passed 248.13
955 MuddyRoad2 Unopened
  • 250に7分。239.80点
  • 500に45分。248.13点
    • 投稿した実装の検証に時間を割いたため、955は開かなかった
  • 合計487.93点
  • レート1236点
    • ついに青コーダーになれた
  • 次回の目標
    • Div IでEasyを通す

XorBoardDivTwo

http://community.topcoder.com/stat?c=problem_statement&pm=12188&rd=15177

7分。239.80点。

  • 愚直に書いた
    • XORが題材となっている問題には苦手意識があるので、まあいいとした
  • SRM後に見直した
  • 奇数回フリップするはグリッドの内容は反転し、偶数回フリップするグリッドの内容は変わらない
  • 以下のようなボードを考える


  • i行目とj列目をフリップさせることを考える


  • 結果は以下となる


  • 交差しているグリッド以外はi行目とj列目が内容が反転する
  • i行目以外の行のj列目がフリップする様子を考える
  • 0は1に反転する


  • 1は0に反転する


  • i行目の操作は注意が必要だ
    • j列目のグリッドは変わらない
    • j列目以外のグリッドはフリップする
  • i行目j列目のグリッドが0である場合


  • i行目j列目のグリッドが1である場合

ここまでの考察を元に実装をした(システムテストをパス)。

class XorBoardDivTwo {
public:
  int theMax(std::vector<std::string> board) {
    int np = 0;

    for (int i = 0, h = board.size(), w = board[0].size(); i < h; i ++)
      for (int j = 0; j < w; j ++)
	np = std::max(count(board, i, j), np);

    return np;
  };
  
private:
  int count(const std::vector<std::string>& board, int r, int c) const {
    int n = std::count(ALL(board[r]), '0');

    if (board[r][c] == '1') {
      n ++;
    }
    else {
      n --;
    }
    
    for (int i = 0, h = board.size(); i < h; i ++)
      if (i != r) {
	n += std::count(ALL(board[i]), '1');
	
	if (board[i][c] == '0') {
	  n ++;
	}
	else {
	  n --;
	}
      }
    
    return n;
  };
};
  • はまりにはまってしまい、40分ほどかかった
    • 愚直な実装で投稿して正解だったのかもしれない
  • countメソッドは以下のほうが見通しがよさそうだ
  int count(const std::vector<std::string>& board, int r, int c) const {
    int n = 0;

    for (int i = 0, h = board.size(); i < h; i ++)
      if (i != r)
	if (board[i][c] == '0') {
	  n += std::count(ALL(board[i]), '1') + 1;
	}
	else {
	  n += std::count(ALL(board[i]), '1') - 1;
	}

    if (board[r][c] == '0') {
      n += std::count(ALL(board[r]), '0') - 1;
    }
    else {
      n += std::count(ALL(board[r]), '0') + 1;
    }

    return n;
  };

CuttingBitString

http://community.topcoder.com/stat?c=problem_statement&pm=12155&rd=15177

45分。248.13点。

  • SRM 545のStrIIRecに類似した問題であると考えた
    • 文字列の左側から確定していく
      • この問題で文字列は二進数の体をなしている
      • 左側から5の冪乗の二進数を確定していけばよい
  • 以下の例を考えよう


  • この文字列は101、1、101と分割することができ、その分割数は3だ


  • SRM 545のStrIIRecで考察したように、左側から確定させていく
    • 以下のような感じ


  • 二進数の文字列と5の冪乗の数について考えてみた
  • 与えられる文字数は[1, 50]
    • 十進数に変換してもlong longに納まりそうだ
  • long longのstd::setを作って再利用する方針にする
    • getminメソッドで用意しよう
class CuttingBitString {
public:
  int getmin(std::string S) {
    if (! fives_.size())
      for (long long i = 1; i < std::numeric_limits<long long>::max() / 5; i *= 5) {
	std::string s;

	for (long long k = i; ; k /= 2) {
	  s.push_back(k % 2 == 1 ? '1' : '0');
	  
	  if (k < 2)
	    break;
	}

	std::reverse(ALL(s));

	fives_.insert(s);
      }
                                   :
  • 準備はできた
  • では左側から確定させていこう
    • 再帰で実装すればよいだろう
                                   :

    memo_.clear();

    int c = search(S);
    
    return (c != INF) ? c : -1;
  };

private:
  int search(const std::string& S) {
    int size = S.size();

    if (! size)
      return 0;

    if (memo_.count(S))
      return memo_[S];

    int& cp = memo_[S];

    cp = INF;

    for (int i = size - 1; i >= 0; i --) {
      std::string s(S.substr(0, i + 1)), t(S.substr(i + 1, size - 1));

      if (fives_.count(s))
	cp = std::min(search(t) + 1, cp);
    }
    return cp;
  };

private:
  std::map<std::string, int> memo_;
  • メモ化も初めから盛り込んだ
  • よかったよかった
  • 図を作って考えてみよう
    • 例として101101を選んだ
    • この例は101、101と分けられる簡単なものだが、木にするとなかなか見応えがある
  • んー
    • 文字列を左右に分けていることを図に盛り込みたい
    • B木の解説がそんな感じじゃなかったっけか...?
    • 画像検索してみる
  • を


  • をを
    • なかなかカッコいい
  • なるほど、左から確定するという手法はこんな探索木を作っているということだったんだなぁ
  • さて、図を眺めるにこの探索では2つの有効な枝刈りができそうだ
  • 接点が扱う文字列の全体が5の冪乗であれば、処理を終了してしまえばよい


  • 左側の文字列が5の冪乗でなければ、子の接点に訪れる必要もない


  • この問題の場合、かなり有効な枝刈りであるように思える
  • しかし、大きな木になればメモ化が必須だろう
    • 有効な経路が複数ある木であった場合、特に有効だろう
  • ...
  • んー?
    • いや、待てよ?
  • 木を再掲する


  • この問題の接点が取りうる値って意外と少ないのではないか...?
  • 桁が増えると枝刈りをしていない状態の木はとても大きくなるだろう
    • しかし考えてみれば、接点が取りうる値は高々50個なのではないか...?
    • この例の場合も取り得る値は6個だ


  • うーむ
  • 木ではなくてグラフで扱ったほうがよいのではないか?
    • そのグラフは有向グラフとなるはずだ
  • やってみた


  • をを
    • 異様にすっきりしたぞ
  • 状態が遷移する様がここまですっきり把握できるのならば、DPに置き換えるのも簡単そうだ
    • 実装してみた
  • ついでに5の冪乗であるかどうか調べる関数もリファクタリングしてみた
    • 用意しておく手法から、与えられた文字列が5の冪乗であるかどうか判定する手法にしてみた

実装は以下(システムテストをパス)。

#define INF 999999


class CuttingBitString {
public:
  int getmin(std::string S) {
    int size = S.size();

    std::vector<int> dp(size + 1, INF);
    
    dp[size] = 0;

    for (int i = size - 1; i >= 0; i --)
      for (int j = 0; j < size - i; j ++)
	if (fives(S.substr(i, j + 1)))
	  dp[i] = std::min(dp[i+j+1] + 1, dp[i]);

    return dp[0] != INF ? dp[0] : -1;
  };

private:
  bool fives(std::string s) const {
    if (s.empty() || s[0] == '0')
      return false;

    long long n = 0;

    for (long long i = 1; ! s.empty(); i *= 2, s.resize(s.size() - 1))
      if (*s.rbegin() == '1')
	n += i;

    for (long long i = 1; i <= n; i *= 5)
      if (i == n)
	return true;

    return false;
  };
};
  • をを
    • 実装もすっきりした
  • 少しDP力が上がったような気がする