SRM 655 Div 2

結果

x--

あれ、目にゴミが…

なぜかEasyに時間がかかってしまった。その上System Testに落ちた。無力。

解答

Easy - BichromeBoard

盤面のパターンは2種類しかない。どちらかのパターンにマッチするならPossible, そうじゃないならImpossible

class BichromeBoard {
public:
  vector<string> board;
  int w,l;
  char types[2][2] = {{'B', 'W'}, {'W', 'B'}};

  bool ableToDrawType(int offset) {
    bool res = true;
    REP(i,w)REP(j,l) {
      res = res && (board[i][j] != types[(i+offset)%2][j%2]);
    }
    return res;
  }

  string ableToDraw(vector<string> _board) {
    board = _board;
    w = board.size();
    l = board[0].size();
    return (ableToDrawType(0) || ableToDrawType(1)) ? "Possible" : "Impossible";
  }
};

復習で間違えたパターン

Medium - FoldingPaper2

一方向に折りたたむ時、一番頑張っても幅が半分まで。目標値の2倍以上の間は半分に折り、二倍未満のときはあと一回で目標値にできる。

class FoldingPaper2 {
public:
  int W;
  int H;
  int A;
  int INF = 100001;

  int foldPart(int i, int L) {
    int ans = 0;
    while(i * 2 < L){
      ans++;
      L = (L+1) / 2;
    }
    if(i != L)ans++;
    return ans;
  }

  int fold(int i, int j, int _W, int _H) {
    if(i > _W || j > _H) return INF;
    return foldPart(i, _W) + foldPart(j, _H);
  }

  int solve(int _W, int _H, int _A) {
    W = _W, H = _H, A = _A;
    int res = INF;
    int m = sqrt(A);
    for(int i = 1; i <= m; i++) {
      for(int j = i; j <= A; j++) {
        if(i*j == A) {
          res = min(res, fold(i,j,W,H));
          res = min(res, fold(i,j,H,W));
        }
      }
    }
    return res == INF ? -1 : res;
  }
};

復習で間違えたパターン

Hard - NineEasy

そもそも問題文を理解するのにものすごい時間がかかったし、問題文を理解してからも大分長い間ウンウン唸った。

前提知識

9の倍数の判定法=各桁の和が9の倍数

解法

メモ化することでO(M*10*9^N)

class NineEasy {
public:
  int N, M;
  vector<int> d;
  int memo[20][9][9][9][9][9];

  int solve(int digit, int *r) {
    if(digit == M){
      REP(i,5)if(r[i] != 0) return 0;
      return 1;
    }
    int *m = &memo[digit][r[0]][r[1]][r[2]][r[3]][r[4]];
    if(*m != -1) return *m;

    int res = 0;
    int nr[5];
    REP(i,10) {
      REP(j,5) {
        nr[j] = r[j];
        if(d[digit] & (1 << j)) nr[j] = (nr[j] + i) % 9;
      }
      res += solve(digit + 1, nr);
      res %= 1000000007;
    }
    return *m = res;
  }

  int count(int _N, vector<int> _d) {
    N = _N, d = _d, M = _d.size();
    memset(memo, -1, sizeof(memo));
    int ini[] = {0, 0, 0, 0, 0};
    return solve(0, ini);
  }
};

絶対もうちょっとましな書き方ある。Div1 MediumではMが大きくてもう一工夫必要みたい。

所感