Hatena::Grouptopcoder

qnighy[黄色]

 | 

2011-02-06

SRM496Div2

| 17:39 | はてなブックマーク - SRM496Div2 - qnighy[黄色]

250 AnagramFree

文字列集合をアナグラムで割ったときの個数。

「文字列の出現頻度を数え上げる」または「文字列内の文字列をソートして数え上げ」。

前者はC#においては配列の辞書順比較が存在しないため難しい。後者がお得のようだ。

// Passed System Test
using System;
using System.Collections.Generic;

public class AnagramFree {
	public int getMaximumSubset(string[] S) {
		for(int i = 0; i < S.Length; i++) {
			char[] cc = S[i].ToCharArray();
			Array.Sort(cc);
			S[i] = new string(cc);
		}
		Array.Sort(S);
		int count = 1;
		for(int i = 1; i < S.Length; i++) {
			if(S[i-1] != S[i]) count++;
		}
		return count;
	}
}

500 ColoredStrokes

横に赤く線を引くか、縦に青く線を引く。結果のマップが与えられたとき、最小ストローク数を求めよ。

赤と青は独立して数えればよい。シンプルな区間数え上げになる。

JavaはcharAtとか書くのが面倒だよねー。

// Passed System Test
import java.util.*;

public class ColoredStrokes {
	public boolean isR(char ch) { return ch=='R' || ch=='G'; }
	public boolean isB(char ch) { return ch=='B' || ch=='G'; }
	public int getLeast(String[] picture) {
		int h = picture.length;
		int w = picture[0].length();
		int count = 0;
		for(int x = 0; x < w; x++) {
			for(int y = 0; y < h; y++) {
				if((x==0 || !isR(picture[y].charAt(x-1))) && isR(picture[y].charAt(x))) count++;
				if((y==0 || !isB(picture[y-1].charAt(x))) && isB(picture[y].charAt(x))) count++;
			}
		}
		return count;
	}
}

1000 PalindromfulString

M文字の回文部分文字列をK種類もつようなN文字の文字列を数え上げろ。

僕の戦略は以下のとおり。

包除原理の拡張を用いることで、「N-M+1種類ある部分文字列のうち少なくとも決められたもの全てが回文になるような文字列の個数」の数え上げに帰着できる。

それは、Union-Findで必要な同値条件を数え上げ、独立に動かせる文字を26の指数に置けばよい。

// Passed System Test
#include <cstdio>
#include <algorithm>
#include <vector>
using namespace std;

long long negcomb(long long a, long long b) {
	a--; b--;
	if(a > b) return 0;
	long long x = 1;
	for(long long i = 0; i < b-a; i++) {
		x = -x * (b-i) / (i+1);
	}
	return x;
}

struct UF {
	int rtcnt;
	vector<int> p;
	UF(int n):rtcnt(n),p(n,-1) {}
	int rt(int x) {return p[x]<0?x:(p[x]=rt(p[x]));}
	bool isrt(int x) {return rt(x)==x;}
	void cat(int x, int y) {
		x=rt(x); y=rt(y);
		if(x==y) return;
		rtcnt--;
		if(p[x]<p[y]) swap(x,y);
		p[y] += p[x];
		p[x] = y;
	}
};

struct PalindromfulString {
	long long count(int N, int M, int K) {
		for(int y = 0; y < 5; y++) {
			for(int x = 0; x < 5; x++)
				printf("%3lld, ",negcomb(y,x));
			printf("\n");
		}
		long long cnt = 0;
		int n = N-M+1;
		for(int i = 0; i < (1<<n); i++) {
			UF uf(N);
			for(int j = 0; j < n; j++) {
				if((i>>j)&1) {
					for(int k = 0; k < M; k++) {
						uf.cat(j+k, j+M-1-k);
					}
				}
			}
			long long pp = negcomb(K, __builtin_popcount(i));
			for(int i = 0; i < uf.rtcnt; i++) pp*=26;
			cnt += pp;
		}
		return cnt;
	}
};
反省

解説によると、どの文字どうしが等しくてどの文字どうしは異なるかをあらわすグルーピングの組合せは全探索で数えられる程度しかないので、それらについて26Pnの総和を求めればよいだけらしい。

全探索の有効活用。ちぃ覚えた。

まとめ

ねむい。

あと、C#のArrays.Sortで80000程度以上の要素を比較するのは危険だということを研究していました。→https://gist.github.com/813142

xgwkffxxgwkffx2011/02/27 20:10W85Grp <a href="http://yipbnhvjunvp.com/">yipbnhvjunvp</a>, [url=http://gxgxyqnixacr.com/]gxgxyqnixacr[/url], [link=http://mmjhqkcmkdkm.com/]mmjhqkcmkdkm[/link], http://fvwfjuhdzkvi.com/

 |