Hatena::Grouptopcoder

cou929のTopCoder日記

2010-06-13

TCO10 Qual 3 div1 (過去問)

11:37

アルゴリズム練習はなんだかひさびさ.

Easy - SumRectangle

2次元の表が与えられていて, すべてのセルに数字が入る. あるセルの値はそのセルの右, 下, 右下のセルの値の合計となる. 表の1行目, 1列目の値が与えられるので, 表の右下の値を求めよ.

普通に右上から順に計算していくだけです. 問題文に"解が定まらない場合は0を返す"と書いてあったようなきがしたんですが, そんなケースは存在しないのでスルーしました.

class SumRectangle {
public:
  int getCorner(vector <int> leftColumn, vector <int> topRow) {
    int i, j;
    int rect[leftColumn.size()][topRow.size()];

    for (i=0; i<leftColumn.size(); i++)
      for (j=0; j<topRow.size(); j++) {
        if (j == 0)
          rect[i][j] = leftColumn[i];
        else if (i == 0)
          rect[i][j] = topRow[j];
        else
          rect[i][j] = 0;
      }

    for (i=1; i<leftColumn.size(); i++)
      for (j=1; j<topRow.size(); j++)
        rect[i][j] = rect[i-1][j-1] - rect[i][j-1] - rect[i-1][j];

    return rect[leftColumn.size()-1][topRow.size()-1];
  }
};

Medium - WhatsThisChord

ギターのタブ譜みたいなやつ(どの弦の何フレットを押さえるか)が与えられるので, そのコードを答えよ. 考慮するのはメジャー・マイナーコードの24種類のみ.

これも時間は少しかかりますがアルゴリズム的にはやるだけの問題です. vectorの初期化がえらいことになっています. 配列の初期化みたいに{}で要素を渡せたらなあといつも思っているんですが, なんとかならないのかなあ.

class WhatsThisChord {
public:
  vector <string> notes;

  string getChord(string chord, int offset) {
    int pos = 0;
    int i;
    for (i=0; i<notes.size(); i++)
      if (chord == notes[i]) {
        pos = i;
        break;
      }
    return notes[(pos + offset) % notes.size()];
  }

  void next(vector <string> &chords) {
    for (int i=0; i<chords.size(); i++)
      chords[i] = getChord(chords[i], 1);
    return;
  }

  bool isSame(vector <string> v, set <string> s) {
    bool ret = true;
    if (v.size() != s.size())
      return false;
    for (int i=0; i<v.size(); i++)
      if (s.find(v[i]) == s.end())
        ret = false;
    return ret;
  }

  string classify(vector <int> chord) {
    string ret;
    vector <string> stdTurning;
    set <string> playedChords;
    vector <string> major;
    vector <string> minor;
    int i;

    notes.clear();
    notes.push_back("C");
    notes.push_back("C#");
    notes.push_back("D");
    notes.push_back("D#");
    notes.push_back("E");
    notes.push_back("F");
    notes.push_back("F#");
    notes.push_back("G");
    notes.push_back("G#");
    notes.push_back("A");
    notes.push_back("A#");
    notes.push_back("B");

    stdTurning.push_back("E");
    stdTurning.push_back("A");
    stdTurning.push_back("D");
    stdTurning.push_back("G");
    stdTurning.push_back("B");
    stdTurning.push_back("E");

    major.push_back("C");
    major.push_back("E");
    major.push_back("G");

    minor.push_back("C");
    minor.push_back("D#");
    minor.push_back("G");

    for (i=0; i<chord.size(); i++)
      if (chord[i] != -1)
        playedChords.insert(getChord(stdTurning[i], chord[i]));

    if (playedChords.size() != 3)
      return ret;

    for (i=0; i<12; i++, next(major), next(minor)) {
      if (isSame(major, playedChords)) {
        ret = major[0] + " Major";
        break;
      } else if (isSame(minor, playedChords)) {
        ret = major[0] + " Minor";
        break;
      }
    }
    
    return ret;
  }
};

2010-06-06

SRM 472 div2 (過去問)

01:07

午前3時という珍しい時間のSRM. つかれていたので本戦には参加していません. なんか難しいなあと思っていたら, writerがrng_58さんでした.

Easy - ColorfulTilesEasy

前から順に見ていき, 同じ色がつづいていた場合, 別の色を配置してカウンタをインクリメントします.

class ColorfulTilesEasy {
public:
  int theMin(string room) {
    int ret = 0;
    int i;
    int n = room.size();

    for (i=1; i<n; i++)
      if (room[i-1] == room[i]) {
        ret++;
        room[i] = 'A';
      }
    
    return ret;
  }
};

Medium - PotatoGame

最大ケースが100000000なので, o(n)のアルゴリズムでも間に合わなそうです. しかしいい解法が思いつかず, とりあえずメモ化探索を書いてみましたが, やはり間に合わず.

他の人のコードを見てみると, 5のmodで場合分けするというシンプルなものでした. たしかにこのようなパターンになっているのですが, 思いつくことはできなかったし, またそれで正しいと言う証明もまだしていません.

class PotatoGame {
public:
  string theWinner(int n) {
    string ret;
    ret = (n%5 == 0 || n%5 == 2) ? "Hanako" : "Taro";

   return ret;
  }
};

Google Code Jam 2010 Round2

01:07

Dashboard - Round 2 2010 - Google Code Jam

たなぼた的にround1を突破しましたが, もともとさほど気合が入っていなかったのもあって, コンディションを整えずにいどんで撃沈でした.

A: Elegant Diamond

方針はなんとなく立てられたのですが, ダイアモンドの形を扱ううまい方法が思いつきませんでした.

B: Bacteria

とりあえず毎ステップシミュレーションするだけでsmallは通るので, それだけ実装しました.

bool dead(vector <vector <int> > &grid) {
  for (int i=0; i<grid.size(); i++)
    for (int j=0; j<grid[0].size(); j++)
      if (grid[i][j] == 1)
        return false;
  return true;
}

bool inRange(int x, int y, int n, int m) {
  if (0 <= x && x < n && 0 <= y && y < m)
    return true;
  return false;
}

int solve(vector <vector <int> > arg) {
  int ret = 0;
  int i, j, k;
  int xmax = 0, ymax = 0;

  for (i=0; i<arg.size(); i++) {
    xmax = max(xmax, max(arg[i][0], arg[i][2]));
    ymax = max(ymax, max(arg[i][1], arg[i][3]));
  }
  xmax++, ymax++;

  vector <vector <int> > grid(ymax, vector <int> (xmax, 0));

  for (i=0; i<arg.size(); i++) {
    int left = min(arg[i][0], arg[i][2]), top =min(arg[i][1], arg[i][3]), right = max(arg[i][0], arg[i][2]), bottom = max(arg[i][1], arg[i][3]);
    for (j=left; j<=right; j++)
      for (k=top; k<=bottom; k++)
        grid[k][j] = 1;
  }

  vector <vector <int> > tmp = grid;

  while (!dead(grid)) {
    ret++;
    for (i=0; i<grid.size(); i++)
      for (j=0; j<grid[0].size(); j++) {
        int left = (!inRange(i-1, j, grid.size(), grid[0].size()) || grid[i-1][j] == 0) ? 0 : 1;
        int top = (!inRange(i, j-1, grid.size(), grid[0].size()) || grid[i][j-1] == 0) ? 0 : 1;
        if (grid[i][j] == 0 && left == 1 && top == 1)
          tmp[i][j] = 1;
        else if (grid[i][j] == 1 && left == 0 && top == 0)
          tmp[i][j] = 0;
        else
          tmp[i][j] = grid[i][j];
      }
    grid = tmp;
  }

  return ret;
}

int main(void) {
  int probNum, i, j, lineNum, x1, y1, x2, y2;

  cin >> probNum;

  for (i=0; i<probNum; i++) {
    vector <vector <int> > arg;
    cin >> lineNum;
    for (j=0; j<lineNum; j++) {
      cin >> x1 >> y1 >> x2 >> y2;
      vector <int> tmp;
      tmp.push_back(x1-1);
      tmp.push_back(y1-1);
      tmp.push_back(x2-1);
      tmp.push_back(y2-1);
      arg.push_back(tmp);
    }

    cout << "Case #" << i + 1 << ": " << solve(arg) << endl;
  }

  return 0;
}

2010-05-25

Google Code Jam Round1 (A/B/C)

22:43

Google Code Jam

先週末はGCJのround1でした. 予想以上に苦戦して, しかも結局だめでした. 悔しいです.

Round 1A

まさかのA-largeがincorrect, B, Cもできず全然ダメでした. スコアボードを見たところAができてれば通過できてたかもしれないので, 非常にもったいない.

Rotate

ほぼstraightforwardな問題. まずは入力を問題文で指示されたように変換します. 先に右側へ寄せてから回転させると楽でした. 次はつづいている部分を探します. ここはdpっぽく, 全体の各マスについて, その時点での縦横斜めの最大長を保存していきました.

で, largeがfail. 原因は配列のインデックス間違いでした. 偶然smallが通ってしまっていたので, コンテスト中に間違えを発見できませんでした.

vector <string> rightGravity(vector <string> box) {
  vector <string> ret(box.size(), string (box[0].size(), '.'));
  int i, j, n = box.size(), m = box[0].size();

  for (i=0; i<n; i++) {
    string line;
    for (j=0; j<m; j++)
      if (box[i][j] != '.')
        line += box[i][j];
    for (j=0; j<line.size(); j++)
      ret[i][m - line.size() + j] = line[j];
  }

  return ret;
}

vector <string> rotate(vector <string> box) {
  vector <string> ret(box.size(), string (box[0].size(), '.'));
  int i, j, n = box.size(), m = box[0].size();

  for (i=0; i<n; i++)
    for (j=0; j<m; j++)
      ret[j][n - 1 - i] = box[i][j];

  return ret;
}

bool inRange(int x, int y, vector <string> &box) {
  if (0 <= x && x <= box.size() && 0 <= y && y <= box[0].size())
    return true;
  return false;
}

string solve(vector <string> box, int K) {
  string ret = "Neither";
  int i, j, k, l, n = box.size();
  int dp[2][n+1][n+1][4]; // horizontal, vertical, lt to rb, rt to lb
  bool redOk = false, blueOk = false;

  for (i=0; i<=n; i++)
    for (j=0; j<=n; j++)
      for (k=0; k<4; k++)
        for (l=0; l<2; l++)
          dp[l][i][j][k] = 0;

  box = rightGravity(box);
  box = rotate(box);

  for (i=0; i<n; i++)
    for (j=0; j<n; j++) 
      if (box[i][j] != '.') {
        int which = 0;
        if (box[i][j] == 'B')
          which = 1;
        int h = 1, v = 1, l = 1, r = 1;
        // horizontal
        if (inRange(i-1, j, box))
          h += dp[which][i-1][j][0];
        // vertical
        if (inRange(i, j-1, box))
          v += dp[which][i][j-1][1];
        // lt to rb
        if (inRange(i-1, j-1, box))
          l += dp[which][i-1][j-1][2];
        // rt to lb
        if (inRange(i-1, j+1, box))       // ここと1行下のインデックスを間違えてた
          r += dp[which][i-1][j+1][3];
        dp[which][i][j][0] = h, dp[which][i][j][1] = v, dp[which][i][j][2] = l, dp[which][i][j][3] = r;
      }
        
  for (i=0; i<n; i++)
    for (j=0; j<n; j++)
      for (k=0; k<4; k++) {
        if (dp[0][i][j][k] >= K)
          redOk = true;
        if (dp[1][i][j][k] >= K)
          blueOk = true;
      }

  if (redOk && blueOk)
    ret = "Both";
  else if (!redOk && blueOk)
    ret = "Blue";
  else if (redOk && !blueOk)
    ret = "Red";

  return ret;
}

int main(void) {
  int probNum, i, j;

  cin >> probNum;

  for (i=0; i<probNum; i++) {
    int N, K;
    vector <string> box;
    string line;

    cin >> N >> K;
    cin.ignore();

    for (j=0; j<N; j++) {
      getline(cin, line);
      box.push_back(line);
    }

    cout << "Case #" << i + 1 << ": " << solve(box, K) << endl;
  }

  return 0;
}
Make it Smooth

明らかにdpっぽいけど, どうしていいかわからない. とりあえず全探索でsmallだけでも通そうかと思ったんですが, 状態の数がめちゃめちゃ多くなって, バグる->泥沼の流れが見えたんで, 先にCを見ることにしました.

Number Game

先に複数の選択肢を持った方が勝ち(A > B のとき A >= 2 * B)が正解らしいのですが, そこまでたどり着けず. こちらもコードをいじりまわして泥沼コースに入ってしまいました. そのままタイムアップ

Round 1B

Aはまあまあさらっと解けたんですが, Bを3連続WAしてしまい, Cは間に合わず敗北. この回もBがうまく行っていればもしかしたら通っていたかもしれないので悔しかったです.

File Fix-it

あたえられたパスを/で分割して, それぞれをsetに入れていき, マッチするものがあるかを調べて行く. さくっと解きたい問題でしたが, 30分弱かかってしまいました.

vector <string> split(const string _s, const string del) {
  vector <string> ret;
  string s = _s;

  while (!s.empty())
    {
      size_t pos = s.find(del);
      string sub = "";
      sub = s.substr(0, pos);
      ret.push_back(sub);
      if (pos != string::npos)
        pos += del.size();
      s.erase(0, pos);
    }

  return ret;
}

int solve(vector <string> src, vector <string> dst) {
  int ret = 0;
  set <string> created;
  int i, j, k;

  for (i=0; i<src.size(); i++) {
    vector <string> s = split(src[i], "/");
    for (j=1; j<s.size(); j++) {
      string path = "/";
      for (k=1; k<=j; k++)
        path += s[k] + '/';
      path.erase(path.end()-1);
      created.insert(path);
    }
  }

  for (i=0; i<dst.size(); i++) {
    vector <string> s = split(dst[i], "/");
    for (j=1; j<s.size(); j++) {
      string path = "/";
      for (k=1; k<=j; k++)
        path += s[k] + '/';
      path.erase(path.end()-1);

      if (created.find(path) == created.end()) {
        created.insert(path);
        ret++;
      }
    }
  }

  return ret;
}

int main(void) {
  int probNum, i, j;
  string line;

  cin >> probNum;

  for (i=0; i<probNum; i++) {
    int N, M;
    vector <string> src, dst;
    cin >> N >> M;
    cin.ignore();
    for (j=0; j<N; j++) {
      getline(cin, line);
      src.push_back(line);
    }
    for (j=0; j<M; j++) {
      getline(cin, line);
      dst.push_back(line);
    }
    cout << "Case #" << i + 1 << ": " << solve(src, dst) << endl;
  }

  return 0;
}
Picking Up Chicks

ひとりづつ順にゴールに辿りつけるか, つけるならば最小で何人追い越せばよいかを調べました. 追い越す必要のある人数は, 自分より前にいてゴールにたどり着けない人の人数と等しくなります (前の人がゴールに辿りつける場合, その人を追い抜かずに並走すればいいため).

NのうちK人がゴールできればいいので, ゴールした人数をcという変数でカウントしようとしていたんですが, このcをインクリメントし忘れていて3連続WAをやらかしてしまいました.

long long toInt(string s) {long long r = 0; istringstream ss(s); ss >> r; return r;}
string toStr(int n) {ostringstream ss; ss << n; return ss.str();}

vector <long long> split(const string _s, const string del) {
  vector <long long> ret;
  string s = _s;

  while (!s.empty())
    {
      size_t pos = s.find(del);
      string sub = "";
      sub = s.substr(0, pos);
      ret.push_back(toInt(sub));
      if (pos != string::npos)
        pos += del.size();
      s.erase(0, pos);
    }

  return ret;
}

string solve(int N, int K, int B, int T, vector <long long> xs, vector <long long> vs) {
  string ret = "IMPOSSIBLE";
  int swapCount = 0;
  int i, j;
  int n = xs.size();
  vector <long long> goals;
  int c = 0;

  for (i=0; i<n; i++) {
    long long t = xs[i] + vs[i] * T;
    if (t < B)
      t = -1;
    goals.push_back(t);
  }

  if (n - count(goals.begin(), goals.end(), -1) < K)
    return ret;

  reverse(goals.begin(), goals.end());
  int done[n];
  for (i=0; i<n; i++)
    done[i] = -1;

  for (i=0; i<n; i++) {
    if (goals[i] == -1)
      continue;
    if (c >= K)
      break;
    
    int next = -1;
    for (j=0; j<=i; j++)
      if (done[j] != -1)
        next = j;

    int localcount = 0;
    if (next != -1)
      localcount = max(done[next], 0);

    for (j=next+1; j<i; j++)
      if (goals[j] == -1)
        localcount++;

    done[i] = localcount;
    swapCount += localcount;
    c++;
  }

  ret = toStr(swapCount);

  return ret;
}

int main(void) {
  int probNum, i;
  string line;

  cin >> probNum;

  for (i=0; i<probNum; i++) {
    int N, K, B, T;
    vector <long long> xs, vs;
    cin >> N >> K >> B >> T;
    cin.ignore();
    getline(cin, line);
    xs = split(line, " ");
    getline(cin, line);
    vs = split(line, " ");

    cout << "Case #" << i + 1 << ": " << solve(N, K, B, T, xs, vs) << endl;
  }

  return 0;
}
Your Rank is Pure

題意をつかめたのがコンテスト終了直前. 原因はinputのところの"Each contains a single integer n"という1文をなぜか見逃していたことでした.

Round 1C

Aで1度WAをやらかす. Bは問題の意味がわからなかったので先にCへ. smallが簡単だったのでsmallだけ通るコードを提出. largeは時間がかかりそうだったのでBに戻ったんですが, 結局最後まで問題文の意味がわからず終了.

結局順位は1001位で, 僅差でだめでした.

Rope Intranet

ロープの交差判定を馬鹿すぎる方法でやってしまい一度WA. 前回の反省を踏まえ手元でテストケースをいくつか作ったんですが, そこからも漏れていました. その後は慎重になりサブミットも遅れました. アルゴリズムとしては単なる全探索です. 瞬殺すべき問題でした.

int solve(vector <int> a, vector <int> b) {
  int ret = 0;
  int n = a.size();
  int i, j;

  for (i=0; i<n; i++)
    for (j=i+1; j<n; j++) {
      if ((a[i] < a[j] && b[i] > b[j]) ||
          (a[i] > a[j] && b[i] < b[j]))
        ret++;
    }

  return ret;
}

int main(void) {
  int probNum, i, j, aa, bb;

  cin >> probNum;

  for (i=0; i<probNum; i++) {
    int N;
    vector <int> a, b;
    cin >> N;

    for (j=0; j<N; j++) {
      cin >> aa >> bb;
      a.push_back(aa);
      b.push_back(bb);
    }

    cout << "Case #" << i + 1 << ": " << solve(a, b) << endl;
  }

  return 0;
}
Load Testing

結局最後まで理解できなかった問題. 解いている人もたくさんいるので理解さえしてしまえば簡単なはずだと粘ったんですが, 結局だめでした.

Making Chess Boards

とりあえずsmallは明らかに全探索で間に合うので, 急いで実装して通す. largeをやるべきかBをやるべきかで悩んだんですが, Bは問題の意味さえわかれば実装は軽いはずと予想しBへ行きました. その後戻ってくることはできませんでした.

以下のコードはanalysisを読んで実装してみたコード. ただワーストケースで全然間に合わないので, もっと工夫が必要です.

map <char, string> pattern;

bool check(int x, int y, int n, vector <string> &board) {
  int i, j;
  for (i=0; i<n; i++) {
    char cur = board[x+i][y];
    if (i > 0)
      if (cur == board[x+i-1][y])
        return false;
    for (j=0; j<n; j++) {
      if (board[x+i][y+j] == '.')
        return false;
      if (board[x+i][y+j] != cur)
        return false;
      cur = ((cur - '0') + 1) % 2 + '0';
    }
  }

  return true;
}

void cut(int x, int y, int n, vector <string> &board) {
  int i, j;
  for (i=0; i<n; i++)
    for (j=0; j<n; j++)
      board[x+i][y+j] = '.';
  return;
}

vector <pair <int, int> >  solve(vector <string> board) {
  vector <pair <int, int> > ret;
  int most = min(board.size(), board[0].size());
  int i, j, k;

  for (i=most; i>=1; i--) {
    int num = 0;
    for (j=0; j<=board.size()-i; j++) {
      for (k=0; k<=board[0].size()-i; k++) {
        if (check(j, k, i, board)) {
          cut(j, k, i, board);
          num++;
        }
      }
    }

    if (num > 0)
      ret.push_back(make_pair(i, num));
  }

  return ret;
}

bool inRange(int x, int y, int n, int m) {
  if (0 <= x && x < n && 0 <= y && y < m)
    return true;
  return false;
}

vector <vector <int> > search(vector <string> &board, vector <vector <int> > dp, int x, int y, int n, int m) {
  vector <vector <int> > ret = dp;
  int i, j;

  for (i=0; i<n; i++)
    for (j=0; j<m; j++) 
      if (inRange(x + i, y + j, board.size(), board[0].size())) {
        if (ret[x + i][y + j] == 0)
          continue;
        if (x + i == 0 || y + j == 0) {
          if (ret[x + i][y + j] != 0)
            ret[x + i][y + j] = 1;
        } else {
          if (board[x + i][y + j] == board[x + i - 1][y + j - 1] &&
              board[x + i][y + j] != board[x + i - 1][y + j] &&
              board[x + i][y + j] != board[x + i][y + j - 1] &&
              board[x + i][y + j] > 0 && board[x + i - 1][y + j - 1] > 0 && board[x + i - 1][y + j] > 0 && board[x + i][y + j - 1] > 0)
            ret[x + i][y + j] = min(ret[x + i - 1][y + j - 1], min(ret[x + i - 1][y + j], ret[x + i][y + j - 1])) + 1;
          else
            ret[x + i][y + j] = 1;
        }
      }

  return ret;
}

vector <pair <int, int> >  solve2(vector <string> board) {
  vector <pair <int, int> > ret;
  map <int, int> memo;
  int n = board.size(), m = board[0].size();
  vector <vector <int> > dp(n, vector <int> (m, 1));
  set <vector <int> > pos;
  int i, j, k;

  dp = search(board, dp, 0, 0, n, m);

  for (i=0; i<n; i++)
    for (j=0; j<m; j++) {
      vector <int> tmp;
      tmp.push_back(-dp[i][j]);
      tmp.push_back(i);
      tmp.push_back(j);
      pos.insert(tmp);
    }
      
  while (!pos.empty()) {
    set <vector <int> >::iterator i = pos.begin();
    int len = -(*i)[0];
    int x = (*i)[1] - len + 1, y = (*i)[2] - len + 1;

    memo[(*i)[0]]++;

    pos.erase(pos.begin());

    vector <vector <int> > original = dp;

    for (j=0; j<len; j++)
      for (k=0; k<len; k++)
        if (x + j < n && y + k < m)
          dp[x + j][y + k] = 0;

    dp = search(board, dp, x, y, len*2, len*2);

//     for (int ll=0; ll<dp.size(); ll++) {
//       for (int lll=0; lll<dp[0].size(); lll++)
//         cout << dp[ll][lll];
//       cout << endl;
//     }
//     cout << endl;

    for (j=0; j<len*2; j++)
      for (k=0; k<len*2; k++) 
        if (inRange(x + j, y + k, n, m))
          if (dp[x + j][y + k] != original[x + j][y + k]) {
            vector <int> tmp;
            tmp.push_back(-original[x + j][y + k]);
            tmp.push_back(x + j);
            tmp.push_back(y + k);
            set <vector <int> >::iterator ti = pos.find(tmp);
            if (ti != pos.end()) {
              pos.erase(ti);
              if (dp[x + j][y + k] != 0) {
                tmp[0] = -dp[x + j][y + k];
                pos.insert(tmp);
              }
            }
          }
  }

  for (map <int, int>::iterator i=memo.begin(); i!=memo.end(); i++)
    ret.push_back(make_pair(-i->first, i->second));

  return ret;
}

int main(void) {
  int probNum, i, j, k;
  string line;

  pattern['0'] = "0000";
  pattern['1'] = "0001";
  pattern['2'] = "0010";
  pattern['3'] = "0011";
  pattern['4'] = "0100";
  pattern['5'] = "0101";
  pattern['6'] = "0110";
  pattern['7'] = "0111";
  pattern['8'] = "1000";
  pattern['9'] = "1001";
  pattern['A'] = "1010";
  pattern['B'] = "1011";
  pattern['C'] = "1100";
  pattern['D'] = "1101";
  pattern['E'] = "1110";
  pattern['F'] = "1111";

  cin >> probNum;

  for (i=0; i<probNum; i++) {
    int N, M;
    vector <string> board;
    cin >> N >> M;
    cin.ignore();

    for (j=0; j<N; j++) {
      string tmp;
      getline(cin, line);
      for (k=0; k<M/4; k++)
        tmp += pattern[line[k]];
      board.push_back(tmp);
    }

    vector <pair <int, int> > res = solve2(board);
    cout << "Case #" << i + 1 << ": " << res.size() << endl;
    for (j=0; j<res.size(); j++)
      cout << res[j].first << " " << res[j].second << endl;
  }

  return 0;
}

反省

  • 細かいミスに時間をとられることが多かった. "今回はたまたま集中力が足りなかった"と片付けるんではなくて, 地道な改善を重ねてミスを減らす努力をすべき.
    • 慎重にやりたいときは, コーナーケースやワーストケースだけじゃなくて, 自明なテストケースも作っておく.
    • カウンタ用の変数などは, あとでやろうとは思わないで, 考えたときにその処理を書いてしまう.
  • LLをひとつぐらい, 手になじむレベルにまで使いこなせるようにする.
    • 簡単な問題を高速に片付けたい.
    • pythonperlはまだリファレンスをひきながらでないと書けない.
    • デフォで多倍長に対応していたりするなどのオプションも.
    • 実は去年も似たような反省をしている.
  • 題意がつかめなかったことが2回あった
    • どちらも数学系の問題
    • 英文の問題というよりも数学力の問題かも
    • 数学系は避けてきたのでツケがまわってきたのかも

ffff2010/05/26 02:461001位ならたぶん大丈夫ですよ。
毎年失格者が出ますから。

cou929cou9292010/05/26 07:23なんと. そうなんですか. ありがとうございます.

2010-05-20

SRM 470 div1

03:05

なんとか250を通して, ratingが1479 -> 1507. 黄色になりました!

250はわりかし解けるようにはなってきたんですが, 500にはまだまだ手が出ません. 一発屋で終わらないようがんばります.

Easy - DoorsGame

JohnとGogoがゲームをプレイしている. N個の一列に連なった部屋があって, それぞれの間にドアがある. それぞれのドアには色が割り当てられている. 部屋の中の1つにトロフィーがあって, 2人はそこを目指す. johnは左端, gogoは右端にいて, john先攻の1ターン交代. 各ターンでプレイヤーは色を1色選ぶと, その色のドアがすべて開く. 色の選び方は, 1. 自分が勝てそうだったら最短でトロフィーを目指すように選ぶ. 2. 負けそうだったらできるだけ多くの色を消費するようにする. という行動をとる. どちらが勝って, またそのとき何色を使っているか.

題意をつかむのが非常に難しかった問題. 方針としては次のようなgreedyなアルゴリズムにしました. それぞれのスタート地点からトロフィーまでのドアの色を調べ, 各ターンで"相手に無くて自分にだけある色"から開いていきます. そのような色がない場合は適当に色を選んで開きます.

class DoorsGame {
public:
  char searchColor(set <char> a, set <char> b) {
    char ret = *(a.begin());

    for (set <char>::iterator i=a.begin(); i!=a.end(); i++)
      if (find(b.begin(), b.end(), *i) == b.end()) {
        ret = *i;
        break;
      }

    return ret;
  }

  void eraseColor(set <char> &a, char color) {
    set <char>::iterator i = find(a.begin(), a.end(), color);
    if (i != a.end())
      a.erase(i);
    return;
  }

  int determineOutcome(string doors, int trophy) {
    int ret = 0;
    int n = doors.size();
    set <char> john;
    set <char> gogo;
    string path = doors;
    int i;
   
    for (i=0; i<n; i++)
      if (i < trophy)
        john.insert(doors[i]);
      else
        gogo.insert(doors[i]);

    for (i=0;; i++) {
      ret++;
      if (i%2 == 0) {
        char color = searchColor(john, gogo);
        eraseColor(john, color);
        eraseColor(gogo, color);
      } else {
        char color = searchColor(gogo, john);
        eraseColor(john, color);
        eraseColor(gogo, color);
      }

      bool j = false, g = false;
      if (john.empty())
        j = true;
      if (gogo.empty())
        g = true;

      if (j && g) {
        ret = 0;
        break;
      }
      if (j && !g)
        break;
      if (!j && g) {
        ret *= -1;
        break;
      }
    }

    return ret;
  }
};

Medium - DrawingLines

開いたんですが方針も立てられず終了.

Hard - BuildingRoads

開けてません.

2010-05-18

TCO10 Qual 2 div1 (過去問)

01:09

Hard - HandlesSpelling

1つの文字列と, いくつかの小さな文字列が与えられる. 小さな文字列で1つの文字列をカバーする. カバー出来ている最長の連続している範囲の長さをA, カバー出来ていない範囲の長さをBとして, A^2 - B の最大値を求めよ.

方針としてはメモ化探索で良さそうですが, Aはカバー出来ている範囲全体という風に題意を勘違いしていました(正しくは連続しているカバー出来ている範囲のうち最長のもの). もとのコードを活かしたくて場当たり的に対応したのですがシステムテストに通らず. 基本的な方針はあっていると思うので, また明日見直したいと思います.

class HandlesSpelling {
public:
  vector <string> badges;
  string sentence;
  string covered;
  int memo[1001];

  bool match(int pos, string badges) {
    int i;
    for (i=0; i<badges.size(); i++)
      if (pos + i >= sentence.size() || badges[i] != sentence[pos + i])
        return false;
    return true;
  }

  int search(int pos) {
    int ret = 0;
    int i;
    int best = -1;

    if (memo[pos] != -1)
      return memo[pos];

    if (pos >= sentence.size())
      return 0;

    for (i=0; i<badges.size(); i++)
      if (match(pos, badges[i])) {
        int score = (int)badges[i].size() + search(pos + (int)badges[i].size());
        if (ret < score) {
          ret = score;
          best = i;
        }
      }

    int score = search(pos + 1);
    if (ret < score) {
      ret = score;
      best = -1;
    }

    if (best != -1)
      for (i=0; i<badges[best].size(); i++)
        covered[pos + i] = '*';

    return memo[pos] = ret;
  }

  int searchA(string covered) {
    int ret = 0;
    int tmp = 0;
    int i;

    for (i=0; i<covered.size();) {
      if (covered[i] == '*') {
        tmp = 0;
        while (i < covered.size() && covered[i++] == '*')
          tmp++;
        ret = max(ret, tmp);
      } else {
        i++;
      }
    }

    return ret;
  }

  int spellIt(vector <string> parts, vector <string> _badges) {
    int i;

    badges.clear();
    sentence.clear();
    covered.clear();
    memset(memo, -1, sizeof(memo));

    badges = _badges;
    for (i=0; i<parts.size(); i++)
      sentence += parts[i];
    covered = sentence;

    int b = search(0);
    int B = sentence.size() - b;
    int A = searchA(covered);

    return A*A - B;
  }
};