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．

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

□コード

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．

□コード

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を生成すれば良かったのでした．

□コード

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

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