nodchipのTopCoder日記

■ Codeforces Round 313 10:22

A. Gerald's Hexagon

• いきなり面倒そうな問題
• 三角格子が出てきた時はとりあえず正方格子に変換することを考える
• 正方格子に変換すると長方形から対角上の二等辺直角三角形を2つ取り除いた図形になる
• 各頂点の座標は元の六角形の座標からすぐに分かる
• ならば面積を求められるか・・・
• Accepted

int main() {
	std::ios::sync_with_stdio(false);

  int x0 = 0;
  int y0 = 0;

  int length;
  cin >> length;
  int x1 = x0 - length;
  int y1 = y0 + length;

  cin >> length;
  int x2 = x1 - length;
  int y2 = y1;

  cin >> length;
  int x3 = x2;
  int y3 = y2 - length;

  cin >> length;
  int x4 = x3 + length;
  int y4 = y3 - length;

  cin >> length;
  int x5 = x4 + length;
  int y5 = y4;

  cin >> length;
  int x6 = x5;
  int y6 = y5 + length;

  assert(x0 == x6);
  assert(y0 == y6);

  int area = (x5 - x2) * (y2 - y5) * 2;
  area -= (x4 - x3) * (x4 - x3);
  area -= (x1 - x0) * (x1 - x0);
  cout << area << endl;
}

B. Equivalent Strings

• これ再帰するだけに見えるんだけど・・・
• CodeForcesだから絶対何かあるはず
• ・・・
• よく分からないorz
• とりあえず枝刈りだけでも入れておこう
• 部分文字列に含まれる文字の種類と数が違っていたらrejectすることにする
• Accepted

int counterA[256 * 1024][32];
int counterB[256 * 1024][32];
string a, b;

bool equals(int beginA, int endA, int beginB, int endB) {
  if ((endA - beginA) & 1) {
    return equal(a.begin() + beginA, a.begin() + endA, b.begin() + beginB);
  }

  int diffA[32];
  REP(i, 26) {
    diffA[i] = counterA[endA][i] - counterA[beginA][i];
  }
  int diffB[32];
  REP(i, 26) {
    diffB[i] = counterB[endB][i] - counterB[beginB][i];
  }

  if (!equal(diffA, diffA + 26, diffB)) {
    return false;
  }

  return (equals(beginA, (beginA + endA) / 2, beginB, (beginB + endB) / 2) &&
    equals((beginA + endA) / 2, endA, (beginB + endB) / 2, endB)) ||
    (equals(beginA, (beginA + endA) / 2, (beginB + endB) / 2, endB) &&
    equals((beginA + endA) / 2, endA, beginB, (beginB + endB) / 2));
}

int main() {
	std::ios::sync_with_stdio(false);

  cin >> a >> b;
  REP(i, a.size()) {
    copy(counterA[i], counterA[i] + 26, counterA[i + 1]);
    ++counterA[i + 1][a[i] - 'a'];
    copy(counterB[i], counterB[i] + 26, counterB[i + 1]);
    ++counterB[i + 1][b[i] - 'a'];
  }

  cout << (equals(0, a.size(), 0, b.size()) ? "YES" : "NO") << endl;
}

C. Gerald and Giant Chess

• げ・・・分からない・・・
• 座標圧縮でもするのだろうか・・・
• DPと数え上げ苦手orz

D. Randomizer

• 幾何っぽいと思ったら全然わからなかったorz

E. Gerald and Path

• とりあえず焼きなまし送りつけておく
• Pretest通っちゃった
• まぁいいや
• Wrong answer on test 15
• N=4のテストケースで引っかかってる。
• なんでだろう・・・

結果

#	Who	=	*	A 500	B 1000	C 1500	D 2250	E 2250
329	Japan nodchip	1336		480 00:10	856 00:36			-1

1951 -> 2018 普通の成績だったにも関わらずレーティングが上がりました。とりあえず現状維持が目標です。

ツイートする