プログラミングを上達させたい

情報学専攻の大学院→放送局でCMの営業など@大阪→舞台俳優＆IT営業@東京

AtCoder Beginner Contest 026 のやつ

Java 競技プログラミング

結局生活の中でプログラミングをほとんどしなくなったんですが、たまーに暇な日があれば久々に問題解いてみっか、みたいな気になります。
やっぱ問題解くタイプのプロコンはいいですね。1問解くだけでもちゃんと満足感が得られるので、少ない時間でも達成感が得られます。

さてさて、一ヶ月以上前のコンテストですが、ABC026を、開催の後日に解いてみました。
全問ミスなく解けたので、テンション上がってブログを書いてる次第です。
しかし順位表を見てみると、いやぁ満点多いですね。レベル上がってるんでしょうね。すごい。プロコン面白いですもんね。

今回解いたのは、AtCoderBeginnerContest#026です。

解説スライドはこちら。
順番に回答を書いていきます。

まずA問題から。数学の問題ですね。
nは偶数なんで、x = yの時がx * yも最大となります。
これについては、相加相乗平均のやつで簡単に証明できるんですが、なんかよく分かんないテンションの時に作ったブログの記事の内容でも説明できると思います。僕の好きな考え方を綴った記事なんで、暇だったらぜひ読んでみてください。

A問題の回答コードはこちら。schemeで書きました。

(display (let* ((x (read))
                (y (/ x 2)))
           (* y y)))
(newline)

実行時間が89msと、非常に短かったです。
これまでAtCoderのscheme処理系はMIT/GNU scheme9.1？とかだって、実行時間が遅かったんですよ(どれくらい遅かったかと言うと、こういう奮闘したくらい遅かったです)。
ところが最近、処理系がGaucheに変わったんですね。なんか、schemeで開発するならこれだよねベイべみたいなやつです。
そしたらこんな早くなりました。すばらし。


ほんでB問題。外の丸から処理していけばいいですね。
これくらいの複雑さですらschemeでは解こうと思えないので、やっぱり全然関数言語使いこなす能力ないんだろうなと思います。
でも元々数学好きだったし、いつか関数型で戦いたいですね。かっこいいし。
これ以降の問題はJavaでやりました。

import java.io.IOException;
import java.io.InputStream;
import java.io.PrintWriter;
import java.util.Arrays;
import java.util.InputMismatchException;
import java.util.LinkedList;
import java.util.PriorityQueue;
import java.util.TreeSet;
 
 
 
public class Main {
  public static void main(String[] args) {
    InputReader sc = new InputReader(System.in);
 
    int n = sc.nextInt();
    int[] radiuss = new int[n];
    for(int i = 0; i < n; i++){
      radiuss[i] = sc.nextInt();
    }
 
    Arrays.sort(radiuss);
 
    double sum = radiuss[n-1] * radiuss[n-1] * Math.PI;
 
    int tashihiki = -1;
 
    for(int i = n-2; i >= 0; i--){
      sum += radiuss[i] * radiuss[i] * Math.PI * tashihiki;
      tashihiki *= -1;
    }
 
    System.out.println(sum);
 
  }
 
//nextChar を追加したよ！
 
//System.out.printf("? %d %d\n", i, j);
 
  
// LinkedList<Integer>[] setsu = new LinkedList[n];
// for(int i = 0; i < n; i++){
//   setsu[i] = new LinkedList<Integer>();
// } 
 
 //ここからテンプレ
  static class InputReader {
      private InputStream stream;
      private byte[] buf = new byte[1024];
      private int curChar;
      private int numChars;
      private SpaceCharFilter filter;
 
      public InputReader(InputStream stream) {
          this.stream = stream;
      }
 
      public int next() {
          if (numChars == -1)
              throw new InputMismatchException();
          if (curChar >= numChars) {
              curChar = 0;
              try {
                  numChars = stream.read(buf);
              } catch (IOException e) {
                  throw new InputMismatchException();
              }
              if (numChars <= 0)
                  return -1;
          }
          return buf[curChar++];
      }
 
      public String nextStr() {
        int c = next();
        while(isSpaceChar(c)){c = next();}
        StringBuffer str = new StringBuffer();
        do{
          str.append((char)c);
          c = next();
        }while(!isSpaceChar(c));
        return str.toString();
      }
 
      public char nextChar() {
        int c = next();
        while(isSpaceChar(c)){c = next();}
        char ret;
        do{
          ret = (char)c;
          c = next();
        }while(!isSpaceChar(c));
        return ret;
      }
 
      public int nextInt() {
          int c = next();
          while (isSpaceChar(c))
              c = next();
          int sgn = 1;
          if (c == '-') {
              sgn = -1;
              c = next();
          }
          int res = 0;
          do {
              if (c < '0' || c > '9')
                  throw new InputMismatchException();
              res *= 10;
              res += c - '0';
              c = next();
          } while (!isSpaceChar(c));
          return res * sgn;
      }
 
      public boolean isSpaceChar(int c) {
          if (filter != null)
              return filter.isSpaceChar(c);
          return c == ' ' || c == '\n' || c == '\r' || c == '\t' || c == -1;
      }
 
      public interface SpaceCharFilter {
          public boolean isSpaceChar(int ch);
      }
  }
}

続いてC問題。
アルゴリズムとかは一切なく、ひたすら調べていけばよいやつです。
無駄があっても時間が間に合いそうだということで、書きやすいように書きました。

import java.io.IOException;
import java.io.InputStream;
import java.io.PrintWriter;
import java.util.Arrays;
import java.util.InputMismatchException;
import java.util.LinkedList;
import java.util.PriorityQueue;
import java.util.TreeSet;
 
 
 
public class Main {
  public static void main(String[] args) {
    InputReader sc = new InputReader(System.in);
 
    int n = sc.nextInt();
 
    LinkedList<Integer>[] bukas = new LinkedList[n];
    for(int i = 0; i < n; i++){
      bukas[i] = new LinkedList<Integer>();
    }
 
    for(int i = 1; i < n; i++){
      int joushi = sc.nextInt() - 1;
      bukas[joushi].add(i);
    }
 
    long[] kyuuyo = new long[n];
    for(int i = 0; i < n; i++){
      if(bukas[i].isEmpty()){
        kyuuyo[i] = 1;
      }else{
        kyuuyo[i] = -1;
      }
    }
 
    // for(int i = 0; i < n; i++){
    //   System.out.println(kyuuyo[i]);
    // }
 
    while(kyuuyo[0] < 0){
      for(int i = 0; i < n; i++){
        if(kyuuyo[i] > 0){continue;}
        long max = kyuuyo[bukas[i].get(0)];
        long min = kyuuyo[bukas[i].get(0)];
        for(int j = 1; j < bukas[i].size(); j++){
          long nowbukakyuuyo = kyuuyo[bukas[i].get(j)];
          if(nowbukakyuuyo > max){
            max = nowbukakyuuyo;
          }
          if(nowbukakyuuyo < min){
            min = nowbukakyuuyo;
          }
        }
        if(min < 0){continue;}
        kyuuyo[i] = max + min + 1;
      }
    }
 
 
//check
    // for(int i = 1; i <= n; i++){
    //   System.out.print(i);
    //   System.out.print(":");
    //   for(int j = 0; j < bukas[i-1].size(); j++){
    //     System.out.print(bukas[i-1].get(j) + 1);
    //     System.out.print(" ");
    //   }
    //   System.out.println("");
    // }
    // for(int i = 0; i < n; i++){
    //   System.out.println(kyuuyo[i]);
    // }
    System.out.println(kyuuyo[0]);
 
  }
 
//nextChar を追加したよ！
 
//System.out.printf("? %d %d\n", i, j);
 
  
// LinkedList<Integer>[] setsu = new LinkedList[n];
// for(int i = 0; i < n; i++){
//   setsu[i] = new LinkedList<Integer>();
// } 
 
 //ここからテンプレ
  static class InputReader {
      private InputStream stream;
      private byte[] buf = new byte[1024];
      private int curChar;
      private int numChars;
      private SpaceCharFilter filter;
 
      public InputReader(InputStream stream) {
          this.stream = stream;
      }
 
      public int next() {
          if (numChars == -1)
              throw new InputMismatchException();
          if (curChar >= numChars) {
              curChar = 0;
              try {
                  numChars = stream.read(buf);
              } catch (IOException e) {
                  throw new InputMismatchException();
              }
              if (numChars <= 0)
                  return -1;
          }
          return buf[curChar++];
      }
 
      public String nextStr() {
        int c = next();
        while(isSpaceChar(c)){c = next();}
        StringBuffer str = new StringBuffer();
        do{
          str.append((char)c);
          c = next();
        }while(!isSpaceChar(c));
        return str.toString();
      }
 
      public char nextChar() {
        int c = next();
        while(isSpaceChar(c)){c = next();}
        char ret;
        do{
          ret = (char)c;
          c = next();
        }while(!isSpaceChar(c));
        return ret;
      }
 
      public int nextInt() {
          int c = next();
          while (isSpaceChar(c))
              c = next();
          int sgn = 1;
          if (c == '-') {
              sgn = -1;
              c = next();
          }
          int res = 0;
          do {
              if (c < '0' || c > '9')
                  throw new InputMismatchException();
              res *= 10;
              res += c - '0';
              c = next();
          } while (!isSpaceChar(c));
          return res * sgn;
      }
 
      public boolean isSpaceChar(int c) {
          if (filter != null)
              return filter.isSpaceChar(c);
          return c == ' ' || c == '\n' || c == '\r' || c == '\t' || c == -1;
      }
 
      public interface SpaceCharFilter {
          public boolean isSpaceChar(int ch);
      }
  }
}


最後にD問題。
二分探索で解きました。D問題が解けるとすごく嬉しいですね。
関数の連続性がどうたらで、二分探索で解けることが分かります。大学一年生のときにそんなんわざわざ証明せなアカンのか、と思ってた、中間値の定理ですね。
こんな感じの定理です。連続な関数なら、こうなってるやろ、みたいな。
f:id:frfrfrfr:20150815140319p:plain

ほんで、今回の式が
f:id:frfrfrfr:20150815140615p:plain
これで、A,B,Cが1以上の整数なんで、t=110やったらf(t)は110以上(つまり100より大)ですよね。
多分t=101とかから始めてもいいんですけど、一応不安なんで、110から始めました。

そして回答はこんな感じ。

import java.io.IOException;
import java.io.InputStream;
import java.io.PrintWriter;
import java.util.Arrays;
import java.util.InputMismatchException;
import java.util.LinkedList;
import java.util.PriorityQueue;
import java.util.TreeSet;
 
 
 
public class Main {
  public static void main(String[] args) {
    InputReader sc = new InputReader(System.in);
 
    int a = sc.nextInt();
    int b = sc.nextInt();
    int c = sc.nextInt();
 
    double left = 0.0;
    double right = 110.0;
    double half = 55.0;
 
    while(Math.abs(a * half + b * Math.sin(c * half * Math.PI) - 100.0) >= 0.000001){
      double halfdistance = a * half + b * Math.sin(c * half * Math.PI);
      if(halfdistance > 100.0){
        right = half;
      }else{
        left = half;
      }
      half = (left + right) / 2;
    }
 
    System.out.println(half); 
  }
 
//nextChar を追加したよ！
 
//System.out.printf("? %d %d\n", i, j);
 
  
// LinkedList<Integer>[] setsu = new LinkedList[n];
// for(int i = 0; i < n; i++){
//   setsu[i] = new LinkedList<Integer>();
// } 
 
 //ここからテンプレ
  static class InputReader {
      private InputStream stream;
      private byte[] buf = new byte[1024];
      private int curChar;
      private int numChars;
      private SpaceCharFilter filter;
 
      public InputReader(InputStream stream) {
          this.stream = stream;
      }
 
      public int next() {
          if (numChars == -1)
              throw new InputMismatchException();
          if (curChar >= numChars) {
              curChar = 0;
              try {
                  numChars = stream.read(buf);
              } catch (IOException e) {
                  throw new InputMismatchException();
              }
              if (numChars <= 0)
                  return -1;
          }
          return buf[curChar++];
      }
 
      public String nextStr() {
        int c = next();
        while(isSpaceChar(c)){c = next();}
        StringBuffer str = new StringBuffer();
        do{
          str.append((char)c);
          c = next();
        }while(!isSpaceChar(c));
        return str.toString();
      }
 
      public char nextChar() {
        int c = next();
        while(isSpaceChar(c)){c = next();}
        char ret;
        do{
          ret = (char)c;
          c = next();
        }while(!isSpaceChar(c));
        return ret;
      }
 
      public int nextInt() {
          int c = next();
          while (isSpaceChar(c))
              c = next();
          int sgn = 1;
          if (c == '-') {
              sgn = -1;
              c = next();
          }
          int res = 0;
          do {
              if (c < '0' || c > '9')
                  throw new InputMismatchException();
              res *= 10;
              res += c - '0';
              c = next();
          } while (!isSpaceChar(c));
          return res * sgn;
      }
 
      public boolean isSpaceChar(int c) {
          if (filter != null)
              return filter.isSpaceChar(c);
          return c == ' ' || c == '\n' || c == '\r' || c == '\t' || c == -1;
      }
 
      public interface SpaceCharFilter {
          public boolean isSpaceChar(int ch);
      }
  }
}


やっぱ解けると嬉しいものですね。
たまにはやっていくぞー！以上！