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

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

AtCoder Beginner Contest 112 に出ました(全完！嬉しっ)

AtCoder Java 競技プログラミング

リアルタイムでAtCoder出ました。
AtCoder Beginner Contest 112です。

開始46分で4問全完できました！とても嬉しい。ただ、3回提出ミス(全部C問題)があったので、"開始61分で全問正解"換算です。もったいない・・・
4問目の解き方がすぐ分かったのが幸いでした。

AtCoder Beginner Contestは、1200未満の人にはレーティングつきません。
現在のレーティングは1182。多分今回でBeginner卒業かと・・・！レーティングどうなるか、楽しみです。

では、解答を書いていきます。

全部Javaで書きました。
※A⇒B⇒D⇒Cの順で解きました。
※正しくは、A⇒B⇒C(解けず)⇒D⇒Cの順で解きました。

A問題

問題文の指示通りに書きました。

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();
 
    if(n == 1){
      System.out.println("Hello World");
    }else{
     int a = sc.nextInt();
     int b = sc.nextInt();
    System.out.println(a+b);
    }
 
  }
 
 //ここからテンプレ
  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);
      }
  }
}

B問題

指示通りに全探索します。

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 limit = sc.nextInt();
    int ans = 9999;
    for(int i = 0; i < n; i++){
      int c = sc.nextInt();
      int t = sc.nextInt();
      if(t <= limit && c < ans){
        ans = c;
      }
    }
 
    if(ans == 9999){
      System.out.println("TLE");
    }else{
      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);
      }
  }
}

D問題(解けた順で書いてます)

aが答え候補だとします。その場合、整数h(>=0)を使って

a + a + ... + a(ここまででaがN個) + a * h = M

となるようにできるハズです。
こうできる、というのは、数式でこう書けます。

(M % (a * N)) % a == 0

そして、ありえる最大の答えはM/N。
よって、答え候補をM/Nから下げていき、上記の式でチェックしていきます。
解答コードはかなりシンプルになりました。

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 m = sc.nextInt();
 
    int ansmax = m / n;
 
    for(int ans = m / n; ans > 0; ans--){
      if((m % (ans * n)) % ans == 0){
        System.out.println(ans);
        break;
      }
    }
 
 
  }
 
 //ここからテンプレ
  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問題(手こずった)

間違い＆TLEを繰り返し、3回エラーの後にAC取れました・・・！
"中心座標を全探索する"という考え方は合ってたのですが、高さをなかなか定められず・・・
ただ、よくよく考えると、

Cx座標の候補は0〜100
Cy座標の候補も0〜100
高さHの候補は (h1 - 200) 〜 (h1 + 200)

としてしまってもOKなことが分かります。本当はHの候補はもう少し絞れますが、計算量的に問題なさそうなのである程度適当にします。

あとは、h_iの計算式にちゃんと適っているか確かめていくだけです。
計算時間はギリギリになりましたが、なんとかACとなりました。

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[][] table = new int[n][4];
    for(int i = 0; i < n; i++){
      table[i][0] = sc.nextInt();
      table[i][1] = sc.nextInt();
      table[i][2] = sc.nextInt();
    }
 
    for(int x = 0; x <= 100; x++){
      for(int y = 0; y <= 100; y++){
        for(int h = Math.max(table[0][2] - 250, 1); h < table[0][2] + 250; h++){
          boolean check = true;
          for(int i = 0; i < n; i++){
            if(table[i][2] != Math.max(h - Math.abs(x - table[i][0]) - Math.abs(y - table[i][1]), 0)){
              check = false;
            }
          }
          if(check){
            System.out.print(x);
            System.out.print(" ");
            System.out.print(y);
            System.out.print(" ");
            System.out.print(h);
          }
        }
 
 
      }
    }
 
  }
 
 //ここからテンプレ
  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問題で何度も手こずったのがダメでしたね・・・自分のコードでカバーできてない例を考えるのを怠っていました。
競プロではスピードと同じくらい慎重さ、正確さも大切であることを痛感しました。


さて、レーティングどうなるかな・・・！1200超えたら嬉しいですね。
来週以降も、なるべく参加して、目標1600を目標に頑張っていきます！蟻本も読んでいくぞー！


(追記 同日23:16)
P.S.さてさて、今回の結果は・・・パフォーマンス1561、そしてレーティングは1182⇒1235になりました！！！！水色！！！！！！！青色を目指して精進します。