Pku JudgeOnline
与えられた重みつきグラフの直径を求めよという問題．ただし，グラフは木である．なお，グラフの直径とはグラフの任意の点対の最短距離の中の最も大きい値のことをいう．
Floyd-Warshallとかは計算量的に間に合わないので，木であることを利用して適当な再帰式をでっちあげてメモ化することによりO(E)で解ける．
追記
なんか近くの問題で前間違えてたやつがあったので解きなおす．
2643:簡単なシミュレーション．なんで間違えたんだろう．
2689:|U-L|はそれほど大きくないので，その部分に関してだけふるう．
以下ソース
Pku2631
import java.util.*;
class Edge{
int from;
int to;
int weight;
Edge(int f,int t,int w){
from = f;
to = t;
weight = w;
}
@Override
public int hashCode() {
int hash = from * 7919 + to;
return hash;
}
@Override
public boolean equals(Object obj) {
Edge e = (Edge)obj;
return from==e.from && to==e.to;
}
}
class Vertex{
List<Edge> adjoint;
Vertex(){
adjoint = new LinkedList<Edge>();
}
public void addEdge(Edge e){
adjoint.add(e);
}
}
public class Main {
static Map<Edge,Integer> memo;
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
List<Edge> lst = new LinkedList<Edge>();
int vNum = 0;
while(sc.hasNext()){
int from = sc.nextInt();
int to = sc.nextInt();
int weight = sc.nextInt();
vNum = Math.max(vNum, Math.max(from,to));
lst.add(new Edge(from-1,to-1,weight));
lst.add(new Edge(to-1,from-1,weight));
}
Vertex vs[] = new Vertex[vNum];
for(Edge e:lst){
if(vs[e.from]==null){
vs[e.from] = new Vertex();
}
vs[e.from].addEdge(e);
}
memo = new HashMap<Edge,Integer>();
int max = 0;
for(Edge e:lst){
max = Math.max(max,f(e, vs));
}
System.out.println(max);
}
static int f(Edge e,Vertex vs[]){
if(memo.containsKey(e)){
return memo.get(e);
}
int res = e.weight;
int max = 0;
for(Edge adj:vs[e.to].adjoint){
if(adj.to==e.from)continue;
max = Math.max(max,f(adj, vs));
}
memo.put(e, res+max);
return res+max;
}
}
Pku2643
import java.util.*;
public class Main {
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
int n = sc.nextInt();
Map<String,String> candidates = new HashMap<String, String>();
sc.nextLine();
for(int i=0;i<n;i++)candidates.put(sc.nextLine(), sc.nextLine());
int m = sc.nextInt();
Map<String,Integer> vote = new HashMap<String, Integer>();
sc.nextLine();
for(int i=0;i<m;i++){
String cand = sc.nextLine();
if(!candidates.containsKey(cand))continue;
if(vote.containsKey(cand))vote.put(cand, vote.get(cand)+1);
else vote.put(cand, 1);
}
int max = 0;
boolean tie = true;
String winner = null;
for(String str:vote.keySet()){
int num = vote.get(str);
if(num==max)tie = true;
else if(num>max){
winner = str;
max = num;
tie = false;
}
}
if(tie)System.out.println("tie");
else System.out.println(candidates.get(winner));
}
}
Pku2689
import java.util.*;
public class Main {
static final long MAX = 2147483647;
public static void main(String[] args) {
//sqrt(MAX)までの素数表を生成.
boolean primes[] = new boolean[1+(int)Math.sqrt(MAX)];
Arrays.fill(primes, true);
primes[0] = false;
primes[1] = false;
for(int i=2;i<primes.length;i++){
if(!primes[i])continue;
for(int j=2*i;j<primes.length;j+=i)primes[j] = false;
}
Scanner sc = new Scanner(System.in);
while(sc.hasNext()){
long l = sc.nextLong();
long u = sc.nextLong();
boolean ps[] = new boolean[(int)(u-l+1)];
Arrays.fill(ps, true);
for(int p=0;p<primes.length;p++){
if(!primes[p])continue;
//素数pでpsをふるう
long lp = 0;//l以上の最小のpの倍数
if(l%p==0)lp = l;
else lp = ((l/p)+1)*p;
if(lp>u)continue;
for(long j=lp;j<=u;j+=p){
ps[(int)(j-l)] = false;
}
if(lp==p){
ps[(int)(lp-l)] = true;
}
}
if(l==1)ps[0] = false;
List<Integer> lst = new Vector<Integer>();
for(int i=0;i<ps.length;i++){
if(ps[i]){
lst.add(i);
}
}
if(lst.size()==1){
System.out.println("There are no adjacent primes.");
}else{
int mindist = Integer.MAX_VALUE;
int maxdist = Integer.MIN_VALUE;
int min1=0;
int min2=0;
int max1=0;
int max2=0;
int fst = lst.get(0);
for(int i=1;i<lst.size();i++){
int snd = lst.get(i);
int diff = snd - fst;
if(mindist>diff){
min1 = fst;
min2 = snd;
mindist = diff;
}
if(maxdist<diff){
max1 = fst;
max2 = snd;
maxdist = diff;
}
fst = snd;
}
System.out.printf("%d,%d are closest, %d,%d are most distant.\n", min1+l,min2+l,max1+l,max2+l);
}
}
}
}
