AtCoder Beginner Contest 170に出ました - プログラミングを上達させたい

Ratedなコンテストに出ました。出ました達郎。

結果は52分で4完(A,B,C,D)、そこからF問題に取り組むも、エラー連発で時間切れでした。F問題は自分のアルゴリズムが合っているかは分からないけど、そもそもそれを実装仕切ることができなかった。細かく慎重にステップを踏んで組んでいくべきだったと反省。
ちなみに、B問題でしょうもないミスを、D問題でREを1回ずつしてしまい、ペナルティとして+10分(5分*2)。
よって、正式なスコアは62分で4完。
ちなみに今回は全てJavaで解きました。Scheme使わずの巻。

D問題以外は、main関数内の部分だけ書きます。

A問題

  public static void main(String[] args) {
    InputReader sc = new InputReader(System.in);
 
 
    for(int i = 0; i < 5; i++){
      int a = sc.nextInt();
      if(a == 0){System.out.println(i+1);}
    }
  }

いつものA問題より難しかった。

B問題

  public static void main(String[] args) {
    InputReader sc = new InputReader(System.in);
 
 
    int x = sc.nextInt();
    int y = sc.nextInt();
    boolean check = false;
    for(int i = 0; i <= x; i++){
      if(2 * i + 4 * (x - i) == y){
        check = true;
        break;
      }
    }    
 
    if(check){
      System.out.println("Yes");
    }else{
      System.out.println("No");
    }
  }

i匹の鶴(正しくはi羽)と、(x-i)匹の亀がいたとして、足の数がy本になるか試していく。
ちなみに1発目がWAに。なぜかと言うと、iの探索範囲を0 <= i <= 大きい数字、としていたため。
今回は合計でx匹しか動物がいないため、0<=i<=xとすべきだった。

C問題

  public static void main(String[] args) {
    InputReader sc = new InputReader(System.in);
 
 
    int x = sc.nextInt();
    int n = sc.nextInt();
 
    int[] nums = new int[n];
    for(int i = 0; i < n; i++){
      nums[i] = sc.nextInt();
    }
 
    if(n == 0){System.out.println(x);}else{
 
    for(int i = 0; i < 1000; i++){
      int kouho1 = x - i;
      boolean exist = false;
      for(int j = 0; j < n; j++){
        if(nums[j] == kouho1){
          exist = true;
        }
      }
      if(!exist){
        System.out.println(kouho1);
        break;
      }
 
      int kouho2 = x + i;
      exist = false;
      for(int j = 0; j < n; j++){
        if(nums[j] == kouho2){
          exist = true;
        }
      }
      if(!exist){
        System.out.println(kouho2);
        break;
      }

    }
  }
  }

X、X-1、X+1、X-2、X+2、X-3、、、、と試していくプログラム。
N=0の場合は例外として処理が必要。入力例3を見てそれに気付き、ムリヤリ修正。入力例3に救われた感じ。

D問題

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[] nums = new int[n+1];
    for(int i = 0; i < n; i++){
      nums[i] = sc.nextInt();
    }
    nums[n] = 10000000;
 
    Arrays.sort(nums);
 
    int ans = 0;
    if(nums[0] != nums[1]){
      ans++;
    }
 
 
    for(int i = 1; i < n; i++){
      if(nums[i-1] == nums[i] || nums[i] == nums[i+1]){continue;}
 
      int[] yakusu = new int[10000];
      yakusu[0] = 1;
      int count = 1;
      for(int j = 2; j * j <= nums[i]; j++){
        if(nums[i] % j == 0){
          if(j * j == nums[i]){            
            yakusu[count] = j;
            count++;
          }else{
            yakusu[count] = j;
            yakusu[count+1] = nums[i] / j;
            count += 2;
          }
        }
      }
 
      boolean exist = false;
      for(int j = 0; j < count; j++){
        int result = Arrays.binarySearch(nums, yakusu[j]);
        if(result >= 0){
          exist = true;
          break;
        }
      }
      if(!exist){
        ans++;
      }
 
    }
 
    System.out.println(ans);
 
 
  }
 
 //ここからテンプレ
  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);
      }
  }
}

手順としては、
・小さい順に並びかえる
・小さい順にチェックしていく、その数をMとして
　・まず、同じ数があったらそもそもアウト
　・ない場合は、自身を除くその数の約数を全て算出し(これにroot(M)かかる)
　・各約数が数列にでてきていないかチェック(logNかかる)
という手順。愚直に調べるより手間がかかってそうで、実はこっちの方がはやいという。
はじめ、約数を納めていく配列の上限を100にしててRE、10000に修正して無事AC。ここの数字が大きくなったってアルゴリズムの速度に影響を与えないように書けていたのだから、最初から大きめの数字を入れるべきだった・・・もったいない。

F問題

イレギュラーな幅優先探索として書いたらいけるんじゃね、と思いながらも、x座標とy座標がこんがらがり、そもそも実装できず。

E問題

F問題を解いたあと、PriorityQueueを使って解けそうだなと思っていたが、そもそもFができないまま終わり。どうなんやろ。

というわけで、無事に4完ではあるものの、そこから上は解けず・・・・
自分のいつもの力は出せたものの、飛躍はない、って感じの回でした。
アルゴリズム力と実装力の両方を問われているなーと改めて思うとともに、特に後者は普段からプログラム書かないと伸びないなとの気持ちも。
ProjectEulerなり、AtCoder過去問なり、やっぱり手を動かした量というのも必要そうですね。がんばろ。

追記(6/14 23:08)
パフォーマンスは1203。ギリギリ水色。この感じでやってるとずっと水色になったり、1段階落ちたりを繰り返すだけかと。