Hatena::Grouptopcoder

cou929のTopCoder日記

2010-06-26

SRM 473 div2 (過去問)

13:34

またもやアルゴリズム問題をやるのは久々です. やはりしばらくやらないと, 全然できなくなってしまいます. そろそろ再開させたいところです.

Easy - OnTheFarmDivTwo

鶴亀算を解くだけの問題. 探索範囲が小さいので, コンピュータらしく全探索でさくっとやりました.

class OnTheFarmDivTwo {
public:
  vector <int> animals(int heads, int legs) {
    vector <int> ret;
    int i;

    for (i=0; i<=heads; i++) {
      if (i * 2 + (heads - i) * 4 == legs) {
        ret.push_back(i);
        ret.push_back(heads-i);
        break;
      }
    }

    return ret;
  }
};

Medium - SequenceOfCommands

2次元平面上を動くコマンドが与えられる. コマンドを無限に繰り返したとき, 軌跡がループしているかどうかを判定せよ.

シミュレーションしてループを検出します. ループの検出には, コマンドの1ターンごとに, 初期位置に帰ってきているかどうかを調べます. 何ターンのコマンドをシミュレートするかについては, このコマンド体系では90度単位でしか曲がれないので, 最大4ターンまで調べればいいことになります.

つまらないバグで時間を費やしてしまいました. 今回のようにif文を列挙する場合は, ありえない値をハンドリングする(switch分のdefaultにあたる部分)ようにすれば, コードの間違いを発見しやすいのではないかと思いました.

class SequenceOfCommands {
public:
  string whatHappens(vector <string> commands) {
    string ret = "unbounded";
    int curx = 0, cury = 0;
    int dir = 0;  // N:0, E:1, S:2, W:3
    string command;
    int i, j;
    vector <pair <int, int> > path;
    
    for (i=0; i<commands.size(); i++)
      command += commands[i];

    for (i=0; i<4; i++) {
      for (j=0; j<command.size(); j++) {
        if (command[j] == 'S') {
          if (dir == 0)
            cury++;
          else if (dir == 1)
            curx++;
          else if (dir == 2)
            cury--;
          else if (dir == 3)
            curx--;
        } else if (command[j] == 'R') {
          dir = (dir + 1) % 4;
        } else if (command[j] == 'L') {
          if (--dir < 0)
            dir = 3;
        }
      }
      if (curx == 0 && cury == 0) {
        ret = "bounded";
        break;
      }
    }

    return ret;
  }
};

MarineideMarineide2012/07/10 10:43You've imrpesesd us all with that posting!

jzaxfxwjzaxfxw2012/07/12 13:042FEYpn <a href="http://tjkastiekpwv.com/">tjkastiekpwv</a>

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;
}