トップ > TopCoder > SRM677 Round1 Div.2

SRM677 Round1 Div.2

TopCoder

一応SRMは今年の3月に始めたのですが、基本的に深夜に行われていたり、学校にいる最中に行われていて中々参加が難しかったのですが、冬休みになって深夜の参加に挑戦してみました。

Easy PalindromePrime

問題概要

A positive integer is called a prime if it has exactly two distinct positive integer divisors: 1 and itself. The first few primes are 2, 3, 5, 7, 11, 13, ... A positive integer is called a palindrome if its base-10 representation reads the same forwards and backwards. Some palindromes: 2, 77, 101, 33333, 12344321. A positive integer is called a palindromic prime if it is both a palindrome and a prime. You are given two ints: L and R. Compute and return the number of palindromic primes between L and R, inclusive.

簡単な意訳
1000以下の自然数L,Rが与えられる。L～R（L,Rを含む）の間の素数でかつ回文数のものの数を答えよ。

解法

L,R≦1000なので特に難しくないですね。素直に篩でRまでの素数を列挙して、出てきた素数の中でL～Rのものを抽出して、あとはそれが回文数かどうか判別するだけです。
他の人のコード見ると、stringに変換して両端から1文字ずつ確認しているところが殆どだったのですが、たかが4桁なのでそんな判定時間は気にしない。C++に甘えて、stringに変換したらreverse、同じ文字列か==で判定して終了、という方針をとりました。

#include <bits/stdc++.h>
using namespace std;
class  PalindromePrime{
	public:
	int count(int l,int r){
		bool prime[r+1];
		for(int i=0;i<=r;i++)	prime[i]=true;
		vector<int> ls;
		for(int i=2;i<=r;i++){
			if(prime[i]){
				ls.push_back(i);
				for(int j=2;j*i<=r;j++)	prime[j*i]=false;
			}
		}
		vector<int> in;
		for(int i=0;i<(int)ls.size();i++){
			if(l<=ls[i]&&ls[i]<=r)	in.push_back(ls[i]);
		}
		ls=in;
		int ret=0;
		for(int i=0;i<(int)ls.size();i++){
			vector<int> num;
			for(int j=0;ls[i]>0;j++){
				num.push_back(ls[i]%10);	ls[i]/=10;
			}
			vector<int> rev=num;		reverse(rev.begin(),rev.end());
			if(rev==num)	ret++;
		}
		return ret;
	}
};

Med FourStrings

問題概要

We have four strings: a, b, c, and d. A superstring of our four strings is any string S such that each of the four strings occurs somewhere in S as a contiguous substring. Note that some superstrings of our four strings always exist. For example, the string S = a+b+c+d is obviously a superstring of a, b, c, and d. Find and return the length of the shortest superstring of a, b, c, and d.

簡単な意訳
文字列a,b,c,dが与えられる。a,b,c,dがすべて部分文字列として含まれるような文字列の内、文字数が最小の文字列の文字数を求めよ。

解法

全て10文字以内なので、a,b,c,dを適当な順に並び替え、その順番で文字列を接続していったときに、文字数が最小になればよい。
aの後ろにbを接続する時、aの左側からループを回していき、最初に接続できると判別できたところでその文字列が接続できる中では必ず最小の文字数になる。
と説明しても分かり辛いのでコード見てください。ちなみにバグを埋め込んだ自分はデバッグに30分以上を費やし、残り5秒あたりで提出。（テストケースを試し終わったのが残り7秒だったので、合っているか確認できませんでした）それでも通ってくれたので嬉しい。

#include <bits/stdc++.h>
using namespace std;
class FourStrings{
	public:
	string func(string a,string b){
		string c=a+b;
		for(int i=0;i<(int)b.size();i++){
			if(a[0]==b[i]){
				int end=0;
				bool flag=true;
				for(int j=1;i+j<(int)b.size()&&j<(int)a.size();j++){
					end++;
					if(a[j]!=b[i+j]){
						flag=false;
					}
				}
			if(flag){
					int n=a.size()+b.size()-end-1;
					cout<<n<<endl;
					if(n<(int)c.size()){
						if(n==a.size())	return a;
						if(n==b.size())	return b;
						c.clear();
						for(int j=0;j<=i;j++)	c+=b[j];
						for(int j=1;j<n-i;j++)	c+=a[j];
						return c;
					}
				}
			}
		}
		return c;
	}
	int shortestLength(string a,string b,string c,string d){
		string ans=a+b+c+d;
		vector<int> per;
		for(int i=0;i<4;i++)	per.push_back(i);
		vector<string> s;
		s.push_back(a);	s.push_back(b);	s.push_back(c);	s.push_back(d);
		do{
			string tmp=func(s[per[1]],s[per[0]]);
			for(int i=2;i<4;i++){
				tmp=func(s[per[i]],tmp);
			}
			cout<<tmp<<endl;
			if(ans.size()>tmp.size())	ans=tmp;
		}while(next_permutation(per.begin(),per.end()));
		return ans.size();
	}
};

と自分はここで時間切れ。

一応hardも。

Hard PalindromePath

問題概要

You are given an undirected graph with n nodes, labeled 0 through n-1. You are given the description of its edges in vector s a and b and in the string c. For each valid i, the vertices a[i] and b[i] are connected by an edge, and the character c[i] is the label of that edge. A walk in the graph is any sequence of consecutive edges. (In other words, a walk is a path that may visit the same vertex and also use the same edge multiple times.) The length of a walk is the number of edges it contains. The label of a walk is the concatenation of labels of edges it contains, in order. A palindrome is a string that reads the same forwards and backwards. Some palindromes: "a", "abba", "racecar", "steponnopets". We are interested in walks that go from node 0 to node 1 and have a palindromic label. Return the length of the shortest such walk. If there is no such walk, return -1 instead.

簡単な意訳
連結である保証のないn頂点からなるグラフが与えられる。vector aのi要素目とvector bのi要素の間には無向辺が張ってあり、そこには文字c[i]がある。頂点0から頂点1に向かって歩いていくが、各辺を通る度に辺上の文字を拾って持っている文字列の後ろに追加していく。最初は文字列""を持っている。頂点1に着いた時、出来た文字列が回文になる行き方のうち、移動回数の最も少ない移動方法の移動回数を求めよ。無ければ-1を返せ。頂点数は20以下。

解法（解いてないので合っている保証は全くありません）

まず、始点と終点に繋がる辺を見る。この時点で同じ文字の辺の組み合わせが無ければ答えはありません。もしその組み合わせがあれば、次は始点・終点からその辺の組み合わせに沿って1歩ずつ移動した後の地点で。再帰的にやっていけば最終的に同じ頂点に辿り着くOR地点が入れ替わるところまでいったらそれが答え。BFSをおすすめします。
（しかし時間内に終わるか怪しい）

感想

1055→1085(+30)でした。6回しかやっておらず、しかも最初の3回はバッチテストの見方を間違えて悲惨な目に。最後の2回でグレーからここまで戻ってこれたので良かった。来年は早いうちにグリーンから昇格したい。