Codeforces Beta Round #24

Codeforces Beta Round #24 7/26(22:00~24:00)

■A. Ring road

□問題
n個の都市がある．
ある都市a_iとある都市b_iの間には，一方通行の道路がある．
一方通行の向きを変えるには，c_iのコストがかかる．
ある都市から他のn-1都市全てに辿れるよう一方通行の向きを変えたい．
最小コストはいくらか．

□解法
グラフが環になっているので，一方通行の流れを時計回り/反時計回りとする時のそれぞれのコストを計算し，小さい方を出力するだけ．一発AC．

# 実は反時計回りでのコストは，総コストから時計回りのコストを引くだけで計算できます．

□コード

view plainprint?

1. import java.util.Scanner;  
2.   
3. public class A{  
4.   
5.  Scanner sc=new Scanner(System.in);  
6.   
7.  int n;  
8.  int[] a, b, c;  
9.   
10.  public void run(){  
11.   n=sc.nextInt();  
12.   a=new int[n];  
13.   b=new int[n];  
14.   c=new int[n];  
15.   for(int i=0; i<n; i++){  
16.    a[i]=sc.nextInt();  
17.    b[i]=sc.nextInt();  
18.    c[i]=sc.nextInt();  
19.   }  
20.   int cost1=0;  
21.   boolean[] visited=new boolean[n];  
22.   visited[0]=true;  
23.   int p=b[0];  
24.   for(int k=1; k<n; k++){  
25.    for(int i=0; i<n; i++){  
26.     if(visited[i])  
27.      continue;  
28.     if(a[i]==p){  
29.      p=b[i];  
30.      visited[i]=true;  
31.      break;  
32.     }else if(b[i]==p){  
33.      cost1+=c[i];  
34.      p=a[i];  
35.      visited[i]=true;  
36.      break;  
37.     }  
38.    }  
39.   }  
40.   int cost=0;  
41.   for(int x : c)  
42.    cost+=x;  
43.   int cost2=cost-cost1;  
44.   println(""+Math.min(cost1, cost2));  
45.  }  
46.   
47.  void println(String s){  
48.   System.out.println(s);  
49.  }  
50.   
51.  void print(String s){  
52.   System.out.print(s);  
53.  }  
54.   
55.  public static void main(String[] args){  
56.   new A().run();  
57.  }  
58.   
59. }  

import java.util.Scanner;

public class A{

 Scanner sc=new Scanner(System.in);

 int n;
 int[] a, b, c;

 public void run(){
  n=sc.nextInt();
  a=new int[n];
  b=new int[n];
  c=new int[n];
  for(int i=0; i<n; i++){
   a[i]=sc.nextInt();
   b[i]=sc.nextInt();
   c[i]=sc.nextInt();
  }
  int cost1=0;
  boolean[] visited=new boolean[n];
  visited[0]=true;
  int p=b[0];
  for(int k=1; k<n; k++){
   for(int i=0; i<n; i++){
    if(visited[i])
     continue;
    if(a[i]==p){
     p=b[i];
     visited[i]=true;
     break;
    }else if(b[i]==p){
     cost1+=c[i];
     p=a[i];
     visited[i]=true;
     break;
    }
   }
  }
  int cost=0;
  for(int x : c)
   cost+=x;
  int cost2=cost-cost1;
  println(""+Math.min(cost1, cost2));
 }

 void println(String s){
  System.out.println(s);
 }

 void print(String s){
  System.out.print(s);
 }

 public static void main(String[] args){
  new A().run();
 }

}

■B. F1 Champions

□問題
F1のレースがt回行われた．
最終順位のつけ方は以下の2種類の以下の優先度順に決める．
Original
勝ち点が大きい->1位になった回数が多い->2位になった回数が多い->…
Alternative rule
1位になった回数が多い->勝ち点が大きい->2位になった回数が多い->…
勝ち点は，1位から順に，25, 18, 15, 12, 10, 8, 6, 4, 2, 1, 0, …．
それぞれのルールでの最終順位が1位のドライバーの名前を出力せよ．

□解法
ソートするだけ．一発AC．

□コード

view plainprint?

1. import java.util.Arrays;  
2. import java.util.Comparator;  
3. import java.util.HashMap;  
4. import java.util.Scanner;  
5.   
6. public class B{  
7.   
8.  Scanner sc=new Scanner(System.in);  
9.   
10.  int m, n;  
11.  HashMap<String, R> map=new HashMap<String, R>();  
12.  int[] ps={25, 18, 15, 12, 10, 8, 6, 4, 2, 1};  
13.   
14.  public void run(){  
15.   m=sc.nextInt();  
16.   for(int i=0; i<m; i++){  
17.    n=sc.nextInt();  
18.    for(int k=0; k<n; k++){  
19.     String s=sc.next();  
20.     if(!map.containsKey(s))  
21.      map.put(s, new R(s));  
22.     R r=map.get(s);  
23.     if(k<ps.length)  
24.      r.score+=ps[k];  
25.     r.rank[k]++;  
26.    }  
27.   }  
28.   
29.   R[] rs=map.values().toArray(new R[0]);  
30.   
31.   Arrays.sort(rs, new Comparator<R>(){  
32.    @Override  
33.    public int compare(R r1, R r2){  
34.     if(r1.score!=r2.score)  
35.      return r2.score-r1.score;  
36.     for(int i=0; i<50; i++)  
37.      if(r1.rank[i]!=r2.rank[i])  
38.       return r2.rank[i]-r1.rank[i];  
39.     return 0;  
40.    }  
41.   });  
42.   println(rs[0].name);  
43.   
44.   Arrays.sort(rs, new Comparator<R>(){  
45.    @Override  
46.    public int compare(R r1, R r2){  
47.     if(r1.rank[0]!=r2.rank[0])  
48.      return r2.rank[0]-r1.rank[0];  
49.     if(r1.score!=r2.score)  
50.      return r2.score-r1.score;  
51.     for(int i=1; i<50; i++){  
52.      if(r1.rank[i]!=r2.rank[i])  
53.       return r2.rank[i]-r1.rank[i];  
54.     }  
55.     return 0;  
56.    }  
57.   });  
58.   println(rs[0].name);  
59.  }  
60.   
61.  final class R{  
62.   int score=0;  
63.   int[] rank=new int[50];  
64.   String name;  
65.   
66.   R(String name){  
67.    this.name=name;  
68.   }  
69.  }  
70.   
71.  void println(String s){  
72.   System.out.println(s);  
73.  }  
74.   
75.  void print(String s){  
76.   System.out.print(s);  
77.  }  
78.   
79.  public static void main(String[] args){  
80.   new B().run();  
81.  }  
82.   
83. }  

import java.util.Arrays;
import java.util.Comparator;
import java.util.HashMap;
import java.util.Scanner;

public class B{

 Scanner sc=new Scanner(System.in);

 int m, n;
 HashMap<String, R> map=new HashMap<String, R>();
 int[] ps={25, 18, 15, 12, 10, 8, 6, 4, 2, 1};

 public void run(){
  m=sc.nextInt();
  for(int i=0; i<m; i++){
   n=sc.nextInt();
   for(int k=0; k<n; k++){
    String s=sc.next();
    if(!map.containsKey(s))
     map.put(s, new R(s));
    R r=map.get(s);
    if(k<ps.length)
     r.score+=ps[k];
    r.rank[k]++;
   }
  }

  R[] rs=map.values().toArray(new R[0]);

  Arrays.sort(rs, new Comparator<R>(){
   @Override
   public int compare(R r1, R r2){
    if(r1.score!=r2.score)
     return r2.score-r1.score;
    for(int i=0; i<50; i++)
     if(r1.rank[i]!=r2.rank[i])
      return r2.rank[i]-r1.rank[i];
    return 0;
   }
  });
  println(rs[0].name);

  Arrays.sort(rs, new Comparator<R>(){
   @Override
   public int compare(R r1, R r2){
    if(r1.rank[0]!=r2.rank[0])
     return r2.rank[0]-r1.rank[0];
    if(r1.score!=r2.score)
     return r2.score-r1.score;
    for(int i=1; i<50; i++){
     if(r1.rank[i]!=r2.rank[i])
      return r2.rank[i]-r1.rank[i];
    }
    return 0;
   }
  });
  println(rs[0].name);
 }

 final class R{
  int score=0;
  int[] rank=new int[50];
  String name;

  R(String name){
   this.name=name;
  }
 }

 void println(String s){
  System.out.println(s);
 }

 void print(String s){
  System.out.print(s);
 }

 public static void main(String[] args){
  new B().run();
 }

}

■C. Sequence of points

□問題
座標M₀, A₀, …, A_n-1が与えられる．
M_iは，A_(i-1)%nに関してM_i-1と対称である．
M_jを計算せよ．

□解法
1≦j≦10¹⁸だと…?!
これは漸化式みたいにして解くのかな?
問題より，
M_i=2A_(i-1)%n-M_i-1
だから…(弄る
周期2nになった．j%2nでOKではないですか．
ついでにi=0~2n-1についての(一応)閉じた式が計算できたの実装．
一発AC．

# 無駄に頑張りましたが，実は，閉じた式なんか要らなくて，周期2nと分かった時点で上の漸化式もどきからM₀, …, M_2n-1を生成すれば良かったのでした．

□コード

view plainprint?

1. import java.util.Scanner;  
2.   
3. public class C{  
4.   
5.  Scanner sc=new Scanner(System.in);  
6.   
7.  int n;  
8.  long j;  
9.   
10.  public void run(){  
11.   n=sc.nextInt();  
12.   j=sc.nextLong();  
13.   int[] mx=new int[2*n];  
14.   int[] my=new int[2*n];  
15.   mx[0]=sc.nextInt();  
16.   my[0]=sc.nextInt();  
17.   int[] ax=new int[n];  
18.   int[] ay=new int[n];  
19.   for(int i=0; i<n; i++){  
20.    ax[i]=sc.nextInt();  
21.    ay[i]=sc.nextInt();  
22.   }  
23.   for(int i=1; i<2*n; i++){  
24.    mx[i]=2*ax[(i-1)%n]-mx[i-1];  
25.    my[i]=2*ay[(i-1)%n]-my[i-1];  
26.   }  
27.   int k=(int)(j%(2*n));  
28.   println(mx[k]+" "+my[k]);  
29.  }  
30.   
31.  void println(String s){  
32.   System.out.println(s);  
33.  }  
34.   
35.  void print(String s){  
36.   System.out.print(s);  
37.  }  
38.   
39.  public static void main(String[] args){  
40.   new C().run();  
41.  }  
42.   
43. }  

import java.util.Scanner;

public class C{

 Scanner sc=new Scanner(System.in);

 int n;
 long j;

 public void run(){
  n=sc.nextInt();
  j=sc.nextLong();
  int[] mx=new int[2*n];
  int[] my=new int[2*n];
  mx[0]=sc.nextInt();
  my[0]=sc.nextInt();
  int[] ax=new int[n];
  int[] ay=new int[n];
  for(int i=0; i<n; i++){
   ax[i]=sc.nextInt();
   ay[i]=sc.nextInt();
  }
  for(int i=1; i<2*n; i++){
   mx[i]=2*ax[(i-1)%n]-mx[i-1];
   my[i]=2*ay[(i-1)%n]-my[i-1];
  }
  int k=(int)(j%(2*n));
  println(mx[k]+" "+my[k]);
 }

 void println(String s){
  System.out.println(s);
 }

 void print(String s){
  System.out.print(s);
 }

 public static void main(String[] args){
  new C().run();
 }

}

■Result
○○○××

■Rating
1633 -> 1744

大幅に上昇．今回は割と調子が良かったです．