qnighy[黄色]

SRM495Div2

SRM, Practice | 18:07 |

Summary

shiftless[現在黄色]が最強だった回らしい。超準急ですねわかります

250 CarrotBoxesEasy

(にんじんの個数,-箱の番号)が最大の箱から1本食べる。これをK回繰り返す。最後に食べたにんじんの入っていた箱の番号。

「シンプルなシミュレーション」「箱をにんじんの個数(>)でソート」なども考えられるが、にんじんの個数100から下げつつ舐めて、その内部で箱番号を舐めるのが一番簡単だと思う。

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

public class CarrotBoxesEasy {
	public int theIndex(int[] carrots, int K) {
		int count = 0;
		for(int i = 99; i >= 0; i--) {
			for(int j = 0; j < carrots.Length; j++) {
				if(i < carrots[j]) count++;
				if(count == K) return j;
			}
		}
		return -1;
	}
}

525 ColorfulCards

狭義単調増加なn以下の自然数の列がある。各項目が素数かどうかだけがわかっている。数列の各項について、特定できるならその値を与えろ。

これは迷わず、「篩→上限と下限を設定」。シャクトリメソッド。

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

public class ColorfulCards {
	public int[] theCards(int N, String colors) {
		char[] cc = new char[N+1];
		cc[1] = 'B';
		for(int i = 2; i <= N; i++) cc[i] = 'R';
		for(int i = 2; i <= N; i++)
			if(cc[i] == 'R')
				for(int j = i*i; j <= N; j+=i)
					cc[j] = 'B';
		int[] ret = new int[colors.length()];
		int num = 1;
		for(int i = 0; i < colors.length(); i++) {
			while(cc[num] != colors.charAt(i)) num++;
			ret[i] = num++;
		}
		num = N;
		for(int i = colors.length()-1; i >= 0; i--) {
			while(cc[num] != colors.charAt(i)) num--;
			if(ret[i] != num--) ret[i] = -1;
		}
		return ret;
	}
}

1000 HexagonPuzzle

六角形のマス目が三角形状に存在し、マス目は互いに区別する。そのうち指定されたマスは取り除く。残ったマスの中で、互いに隣接する３マスの間で巡回swap操作を行えるとき、初期状態から到達しうる盤の状態数のモジュロ。

これは、まず、巡回swap操作でたどり着けるマス目をUnion-Findでグルーピングする。各グループ内は、2のパリティーを持つことが容易にわかる。なので、各グループごとにn!/2を計算して積を求める。

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

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

const int MOD = 1000000007;
struct HexagonPuzzle {
	int theCount(vector<string> board) {
		int n = board.size();
		UF uf(n*n);
		long long cnt = 1;
		for(int y = 0; y+2 < n; y++)
			for(int x = 0; x <= y; x++)
				if(board[y+2][x+1]=='.' && board[y+1][x]=='.' && board[y+1][x+1]=='.')
					uf.cat((y+2)*n+(x+1),(y+1)*n+x), uf.cat((y+2)*n+(x+1),(y+1)*n+(x+1));
		for(int y = 0; y+1 < n; y++)
			for(int x = 0; x <= y; x++)
				if(board[y][x]=='.' && board[y+1][x]=='.' && board[y+1][x+1]=='.')
					uf.cat(y*n+x,(y+1)*n+x), uf.cat(y*n+x,(y+1)*n+(x+1));
		for(int y = 0; y < n; y++)
			for(int x = 0; x <= y; x++)
				if(uf.isrt(y*n+x) && uf.siz(y*n+x)>1)
					for(int i = 3; i <= uf.siz(y*n+x); i++) cnt = cnt*i%MOD;
		return (int)cnt;
	}
};

まとめ

ねむい。

案外妥当にコーディングできてる気がする。

SRM496Div2

SRM, Practice | 17:39 |

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

こんにちは

16:56 |

TopCoderのPracticeを日課にするという素晴らしいアイデアを思いついたのでここの日記を開いてみることにしました。