Hatena::Grouptopcoder

qnighy[黄色]

 | 

2011-02-07

SRM496Div1

| 19:14 | はてなブックマーク - SRM496Div1 - qnighy[黄色]

250 ColoredStrokes

Div2で練習したので略。

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

public class ColoredStrokes {
	public bool isR(char ch) {return ch=='R' || ch=='G';}
	public bool isB(char ch) {return ch=='B' || ch=='G';}
	public char at(string[] picture,int y,int x) {
		try { return picture[y][x]; } catch (Exception) {return '.';}
	}
	public int getLeast(string[] picture) {
		int h = picture.Length;
		int w = picture[0].Length;
		int count = 0;
		for(int y = 0; y < h; y++) {
			for(int x = 0; x < w; x++) {
				if(!isR(at(picture,y,x-1)) && isR(at(picture,y,x))) count++;
				if(!isB(at(picture,y-1,x)) && isB(at(picture,y,x))) count++;
			}
		}
		return count;
	}
}

ACRushの解答見たらビット演算使ってた。

500 OneDimensionalBalls

数直線上にn個の点があり、前方向か後方向に互いに等しい正の速度で等速運動している。ある時点とそれより後のある時点の2回の写真を撮ったが、2回目のときはダミーを追加した。2枚の写真が与えられたとき、その写真の条件を満たす2枚間の点の対応関係は何通りあるか。

まず、2回の間で各点がどれだけの距離を移動したかの候補をリストアップしてunique。そうすると、2部グラフの最大マッチングの数え上げになるが、一直線上なので上手いこと走査すると簡単に計算できる。

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

public class OneDimensionalBalls {
	public long countValidGuesses(int[] firstPicture, int[] secondPicture) {
		Arrays.sort(firstPicture);
		int[] times = new int[secondPicture.length];
		for(int i = 0; i < secondPicture.length; i++) {
			times[i] = Math.abs(secondPicture[i]-firstPicture[0]);
		}
		Arrays.sort(times);
		long cnt = 0;
		for(int i = 0; i < times.length; i++) {
			if(0<i && times[i-1]==times[i]) continue;
			if(times[i] == 0) continue;
			int tim = times[i];
			boolean[] vis = new boolean[firstPicture.length];
			long local_cnt = 1;
			for(int j = 0; j < firstPicture.length; j++) {
				if(vis[j]) continue;
				vis[j] = true;
				int pos = firstPicture[j];
				boolean fst = Arrays.binarySearch(secondPicture,pos-tim)>=0;
				int dups = 2;
				while(Arrays.binarySearch(secondPicture,pos+tim)>=0 && Arrays.binarySearch(firstPicture,pos+tim+tim)>=0) {
					dups++;
					pos += tim*2;
					vis[Arrays.binarySearch(firstPicture,pos)] = true;
				}
				boolean snd = Arrays.binarySearch(secondPicture,pos+tim)>=0;
				if(fst && snd) local_cnt *= dups;
				if( (!fst) && (!snd) ) local_cnt = 0;
			}
			System.out.println(tim+" : "+local_cnt);
			cnt += local_cnt;
		}
		return cnt;
	}
}
反省

Setを使えばもっと簡単にできた。

950 YetAnotherHamiltonianPath

文字列を頂点とするグラフがある。頂点AB間の距離はlen(A)^2+len(B)^2-len(LCP(A,B))^2で与えられる。(ただしLCPは最長共通接頭辞)ここで頂点0から頂点1までの最短ハミルトン路を計算せよ。

まず明らかに、len(A)^2やlen(B)^2は経路に関係なく同じ個数だけ取り除かれるので、len(LCP(A,B))^2の和を最小化すればいいことがわかる。直感的にいって、できるだけ共通接頭辞の長い経路を通るのがよいと思われる。問題は、始点と終点がよく共通しているにもかかわらず、途中でその共通性を壊さなければいけない場合である。

あまりちゃんとした証明は行わなかったが、始点または終点ともっともよく共通している頂点を選択し、それを新しい始点または終点とする、というアルゴリズムで行ったら上手くいった。

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

int cplen(const string& s1, const string& s2) {
	int len = (int)min(s1.size(),s2.size());
	for(int i = 0; i < len; i++) {
		if(s1[i] != s2[i]) return i;
	}
	return len;
}

struct YetAnotherHamiltonianPath {
	int leastCost(vector<string> label) {
		int cost = 0;
		for(int i = 0; i < (int)label.size(); i++) {
			cost += (i<2?1:2) * label[i].size() * label[i].size();
		}
		// printf("initial cost: %d\n",cost);
		string s1 = label[0];
		string s2 = label[1];
		vector<bool> vis(label.size());
		vis[0] = vis[1] = true;
		int viscount = label.size()-2;
		while(0 < viscount) {
			// printf("%s - (%d) - %s\n", s1.c_str(), viscount, s2.c_str());
			int maxval = -1;
			int maxid = -1;
			for(int i = 0; i < (int)label.size(); i++) {
				if(vis[i]) continue;
				int val = max(cplen(s1,label[i]),cplen(s2,label[i]));
				if(maxval < val) {
					maxval = val;
					maxid = i;
				}
			}
			vis[maxid] = true; viscount--;
			cost -= maxval*maxval;
			if(cplen(s1,label[maxid]) > cplen(s2,label[maxid])) {
				s1 = label[maxid];
			} else {
				s2 = label[maxid];
			}
		}
		cost -= cplen(s1,s2)*cplen(s1,s2);
		return cost;
	}
};

Editorialによると、UdH-WiNGeRによる解答が美しい。これは、文字列をソートした順に辿る閉路のコストを求めた後に、0から1の間の辺の重みを除く。


まとめ

やっぱり、よく考えてからコーディングしたほうが…

そんじゃーね!

nqfcftypbunqfcftypbu 2011/02/27 22:35 qyJesi <a href="http://bxzaqboxfinw.com/">bxzaqboxfinw</a>, [url=http://jdozspyohzgc.com/]jdozspyohzgc[/url], [link=http://zhktgvfkhfcr.com/]zhktgvfkhfcr[/link], http://tsgmogjzvcxx.com/

ゲスト



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