Hatena::Grouptopcoder

nodchipのTopCoder日記 このページをアンテナに追加 RSSフィード

 | 

2011-08-28

ZOJ Monthly, August 2011 on August 28. 20:26 ZOJ Monthly, August 2011 on August 28.  - nodchipのTopCoder日記 を含むブックマーク はてなブックマーク - ZOJ Monthly, August 2011 on August 28.  - nodchipのTopCoder日記 ZOJ Monthly, August 2011 on August 28.  - nodchipのTopCoder日記 のブックマークコメント

東方オンリーイベント第二弾ということで急遽参加してみました。

A. Hello, Gensokyo

  • Aだから簡単なはず
  • ・・・
  • Aのくせに簡単じゃない気がする
  • ・・・
  • 全くわからない
  • なぜこんな問題が一番人気なのだろう・・・?

B. Fairy Wars

  • 殆ど考えませんでした

C. Hide and seek

  • 殆ど考えませんでした

D. Bookcase

  • 挿入する回数の最小を求めれば良いらしい
  • なんかバブルソートの交換回数に似てる気がする
  • でもぜんぜん違う・・・
  • なんだろう
  • すでにソート済みの部分は動かす必要がないから
  • ソート済みの最長部分列以外の要素の数を求めれば良いはず
  • ならばLISだ
  • スパゲティソースペタペタ
  • ・・・
  • なんか答えが合わない
  • 同じ名前の本が来るのか・・・
  • LISをちょこっといじって・・・
  • Accepted
const int inf = 99999999;
#define index_of(as, x) \
  distance(as.begin(), upper_bound(as.begin(), as.end(), x))
vector<int> lis_fast(const vector<int>& a) {
  const int n = a.size();
  vector<int> A(n, inf);
  vector<int> id(n);
  for (int i = 0; i < n; ++i) {
    id[i] = index_of(A, a[i]);
    A[ id[i] ] = a[i];
  }
  int m = *max_element(id.begin(), id.end());
  vector<int> b(m+1);
  for (int i = n-1; i >= 0; --i)
    if (id[i] == m) b[m--] = a[i];
  return b;
}

int main() {
	for (int N, M;cin >> N >> M; ) {
		string dummy;
		getline(cin, dummy);

		int answer = 0;
		REP(n, N) {
			vector<string> books;
			REP(m, M) {
				string book;
				getline(cin, book);
				books.push_back(book);
			}

			map<string, int> bookToIndex;
			REP(i, books.size()) {
				bookToIndex[books[i]] = 0;
			}

			int index = 0;
			for (map<string, int>::iterator it = bookToIndex.begin(), itEnd = bookToIndex.end(); it != itEnd; ++it) {
				it->second = index++;
			}

			vector<int> seq;
			REP(i, books.size()) {
				seq.push_back(bookToIndex[books[i]]);
			}

			const vector<int> lis = lis_fast(seq);
			answer += M - lis.size();
		}

		cout << answer << endl;
	}
}

E. Crazy Shopping

  • 殆ど考えませんでした

F. Disappearance

  • 殆ど考えませんでした

G. Weekend Party

  • これは焼きなましに違いない!(<-違います
  • 焼きなましペタペタ
  • TLE & WA
  • ・・・
  • 焼きなましなんてなかった
  • じゃあなんだろう?
  • 同じ属性の人はバラケさせるより並べたほうがお得だよなぁ
  • 特にソロの人
  • なら同じ属性の人は1度しか使わなくていいのかなぁ?
  • Wrong Answer
  • ソロの人は1回でそれ以外は2回まで?
  • Wrong Answer
  • ううむ
  • A G C AGCがいる場合はAGCは3人必要なのか
  • なら属性が同じ人は属性の個数人まででどうだろう?
  • Accepted
bool check(const vector<int>& v) {
	const int n = v.size();
	for (int i = 0; i < n; ++i) {
		if (v[i] & v[(i + 1) % n]) {
			continue;
		}

		return false;
	}

	return true;
}

// 立っているビットの数を数える
int countPop(int x){
	x = (x & 0x55555555) + ((x >> 1) & 0x55555555);
	x = (x & 0x33333333) + ((x >> 2) & 0x33333333);
	x = (x & 0x0f0f0f0f) + ((x >> 4) & 0x0f0f0f0f);
	x = (x & 0x00ff00ff) + ((x >> 8) & 0x00ff00ff);
	x = (x & 0x0000ffff) + ((x >> 16) & 0x0000ffff);
	return x;
}

int main() {
	static int flag[256];
	flag['A'] = 1;
	flag['C'] = 2;
	flag['G'] = 4;

	for (int N; cin >> N; ) {
		map<int, int> s;
		REP(n, N) {
			string name, acg;
			cin >> name >> acg;

			int mask = 0;
			REP(j, acg.size()) {
				const char ch = acg[j];
				mask |= flag[ch];
			}

			++s[mask];
		}

		
		vector<int> v;
		for (map<int, int>::iterator it = s.begin(), itEnd = s.end(); it != itEnd; ++it) {
			int count = min(it->second, countPop(it->first));
			REP(i, count) {
				v.push_back(it->first);
			}
		}

		bool ok = false;
		do {
			ok = check(v);
		} while (!ok && next_permutation(ALL(v)));

		cout << (ok ? "Yes" : "No") << endl;
	}
}

H. Shinryaku! Kero Musume

  • 侵略されとる・・・
  • あまり考えていません

I. Parterre

  • ・・・
  • これはもしややるだけ問題なのではなかろうか?
  • 各長方形の上下左右の花を矩形として保存
  • あとはクエリとの積をとるだけ・・・
  • Accepted
struct RECT {
	int left, top, right, bottom;
};

int cross(const RECT& a, RECT& b) {
	RECT c;
	c.left = max(a.left, b.left);
	c.right = min(a.right, b.right);
	c.top = max(a.top, b.top);
	c.bottom = min(a.bottom, b.bottom);
	if (c.left < c.right && c.top < c.bottom) {
		return (c.right - c.left) * (c.bottom - c.top);
	}
	return 0;
};

struct FLOWER {
	RECT rect;
	int index;
};

int main() {
	for (int N, M; cin >> N >> M; ) {
		const int NN = (min(N, M) + 1) / 2;

		vector<FLOWER> flowers;
		REP(i, NN) {
			int A;
			cin >> A;

			if (i != NN - 1) {
				RECT r;
				FLOWER f;
				f.index = A;

				// top
				r.left = i;
				r.right = M - i;

				r.top = i;
				r.bottom = i + 1;

				f.rect = r;
				flowers.push_back(f);

				// bottom
				r.bottom = N - i;
				r.top = N - i - 1;

				f.rect = r;
				flowers.push_back(f);

				// left
				r.top = i + 1;
				r.bottom = N - i - 1;

				r.left = i;
				r.right = i + 1;

				f.rect = r;
				flowers.push_back(f);

				// right;
				r.right = M - i;
				r.left = M - i - 1;

				f.rect = r;
				flowers.push_back(f);

			} else {
				// 最後の1ラインだけ
				RECT r;
				FLOWER f;
				f.index = A;

				r.left = i;
				r.right = M - i;
				r.top = i;
				r.bottom = N - i;
				f.rect = r;

				flowers.push_back(f);
			}
		}

		int Q;
		cin >> Q;
		REP(q, Q) {
			RECT rect;
			cin >> rect.top >> rect.left >> rect.bottom >> rect.right;
			++rect.bottom;
			++rect.right;

			// index -> count
			int bestIndex = -1;
			int bestCount = -1;

			map<int, int> kinds;
			for (vector<FLOWER>::iterator it = flowers.begin(), itEnd = flowers.end(); it != itEnd; ++it) {
				const int count = cross(it->rect, rect);
				if (!count) {
					continue;
				}

				const int currentCount = (kinds[it->index] += count);
				if (bestCount < currentCount || (bestCount == currentCount && bestIndex > it->index)) {
					bestCount = currentCount;
					bestIndex = it->index;
				}
			}

			cout << kinds.size() << " " << bestIndex << " " << bestCount << endl;
		}
	}
}

Result

RankNameSolvedAyaCirnoFlandreMukyuNitoriRemiliaSuikaSuwakoYuukaPenalty
97 nodchip310048 (2)00210 (16)0108 (1)686

残り90分くらいのところで放棄してしまったので微妙な成績になってしまいました。90分あればもう一問解けたのでしょうか・・・。

トラックバック - http://topcoder.g.hatena.ne.jp/nodchip/20110828
 |