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

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

AtCoder Regular Contest 103 に出ました

AtCoder Java 競技プログラミング

レーティングを上げるぞう、ということで、今日もAtCoder出ました。
いつもBeginner Contestですが、勇気を出してRegular Contestに出ました。

AtCoder Regular Contest 103 - AtCoder

AtCoderのシステムでは、レーティングとパフォーマンスというものがあります。
パフォーマンスは「その回だけのレーティング」で、それを何回もやっていくと「レーティング＝パフォーマンス」に収束するらしいです。
つまり、例えばゆくゆくレーティング2000を狙うなら、普段からパフォーマンス値を2000前後取っていく必要があるということです。
ただ、Beginner Contestだとどんなに成績が良くてもパフォーマンス値が1600までしか付かない仕組みとのこと。

いつかレーティング1600以上になりたいと思っている僕としては、パフォーマンス値1600より大きいのを獲得しなければならないわけで、今回Regular Contestに出る運びとなったわけです。

※最後に書きますが、この決断は合っていました！！！


さて、今回の僕の結果は、、、、C問題正解 ＆ D問題部分点ゲット、でした。
解答書いていきます。

C問題

偶数番目に現れる数の中で、1番多く出る数をa、aの出現回数がanum、2番目に多く出る数がb、bの出現回数をbnum
奇数番目に現れる数の中で、1番多く出る数をc、cの出現回数がcnum、2番目に多く出る数がd、dの出現回数をdnum
とします。
a != c なら、n - anum - cnumが答え、
a == c なら, min(n - anum - dnum, n - bnum - cnum)が答えとなります。
多分、TreeSetとか上手く使ってカウントすべきだったんですが、パッと使い方分からなかったので ソート＆頑張り で解きました。

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[] as = new int[n/2];
    int[] bs = new int[n/2];
 
    for(int i = 0; i < n/2; i++){
      as[i] = sc.nextInt();
      bs[i] = sc.nextInt();
    }
 
    Arrays.sort(as);
    Arrays.sort(bs);
 
    int maxa = 1;
    int maxnum = 0;
    int count = 1;
    for(int i = 0; i < n/2 - 1; i++){
      if(as[i] == as[i+1]){
        count++;
        if(maxa < count){
          maxa = count;
          maxnum = as[i+1];
        }
      }else{
        count = 1;
      }
    }
 
    int seconda = 0;
    int secondmaxa = 0;
 
    count = 1;
    if(as[0] != maxnum){
      seconda = 1;
    }
 
    for(int i = 0; i < n/2 - 1; i++){
      if(as[i] == as[i+1] && as[i] != maxnum){
        count++;
        if(seconda < count){
          seconda = count;
          secondmaxa = as[i+1];
        }
      }else if(as[i + 1] != maxnum && seconda == 0){
        seconda = 1;
      }else{
        count = 1;
      }
    }
 
 
 
    int maxb = 1;
    int maxnumb = 0;
    count = 1;
    for(int i = 0; i < n/2 - 1; i++){
      if(bs[i] == bs[i+1]){
        count++;
        if(maxb < count){
          maxb = count;
          maxnumb = bs[i+1];
        }
      }else{
        count = 1;
      }
    }
 
    int secondb = 0;
    int secondmaxb = 0;
 
    count = 1;
    if(bs[0] != maxnumb){
      secondb = 1;
    }
 
    for(int i = 0; i < n/2 - 1; i++){
      if(bs[i] == bs[i+1] && bs[i] != maxnumb){
        count++;
        if(secondb < count){
          secondb = count;
          secondmaxb = bs[i+1];
        }
      }else if(bs[i + 1] != maxnumb && secondb == 0){
        secondb = 1;
      }else{
        count = 1;
      }
    }
 
 
 
    if(maxnum != maxnumb){
      System.out.println(n - maxa - maxb);
    }else{
      if(n - maxa - secondb < n - maxb - seconda){
        System.out.println(n - maxa - secondb);
      }else{
        System.out.println(n - maxb - seconda);        
      }
    }
  }
 
 //ここからテンプレ
  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問題(部分点でした)

まず、スタート地点から各地点へのマンハッタン距離の偶奇が一致している必要があります。それをチェックして、まず可能かどうかさばきます(あくまで部分点のみの話です)。

そしてその後、腕は40本まで使える ＆ 部分点なら-10 < x, y < 10 という条件から、
長さ1の腕を大量に用意して、じわじわと目標地点まで行き、目標に到着した後にまだ腕が余っていたら意味なく同じ場所を往復する作戦をとりました。

問題ページにあるサンプルで実行したら下記のような感じです。
目標地点に到着した後は"UDUD..."となります。

3
-1 0
0 3
2 -1

なら

21
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
LUDUDUDUDUDUDUDUDUDUD
UUUUDUDUDUDUDUDUDUDUD
RRDUDUDUDUDUDUDUDUDUD

という解答になり、他にも

3
-7 -3
7 3
-3 -7

なら

20
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
LLLLLLLDDDUDUDUDUDUD
RRRRRRRUUUUDUDUDUDUD
LLLDDDDDDDUDUDUDUDUD

という解答になります。
これを提出した結果・・・・無事、部分点ゲットとなりました。
コードは下記のような感じです。

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[][] points = new int[n][2];
    int[] abss = new int[n];
    for(int i = 0; i < n; i++){
      points[i][0] = sc.nextInt();
      points[i][1] = sc.nextInt();
      abss[i] = points[i][0] + points[i][1];
    }
 
    boolean possible_check = true;
    for(int i = 0; i < n - 1; i++){
      if(Math.abs(abss[i]) % 2 != Math.abs(abss[i+1]) % 2){
        possible_check = false;
      }
    }
 
    if(possible_check){
      if(abss[0] % 2 == 0){
        System.out.println("20");
 
        for(int k = 0; k < 19; k++){
          System.out.print("1 ");
        }
        System.out.println("1");
 
        for(int j = 0; j < n; j++){
          char tate;
          char yoko;
          if(points[j][1] > 0){
            tate = 'U';
          }else{
            tate = 'D';
          }
          if(points[j][0] > 0){
            yoko = 'R';
          }else{
            yoko = 'L';
          }
 
          for(int i = 0; i < Math.abs(points[j][0]); i++){
            System.out.print(yoko);
          }
          for(int i = 0; i < Math.abs(points[j][1]); i++){
            System.out.print(tate);
          }
          for(int i = 0; i < (20 - Math.abs(points[j][1]) - Math.abs(points[j][0])) / 2; i++){
            System.out.print("UD");
          } 
 
          System.out.println("");
        }
 
      }else{
        System.out.println("21");
 
        for(int k = 0; k < 20; k++){
          System.out.print("1 ");
        }
        System.out.println("1");
 
        for(int j = 0; j < n; j++){
          char tate;
          char yoko;
          if(points[j][1] > 0){
            tate = 'U';
          }else{
            tate = 'D';
          }
          if(points[j][0] > 0){
            yoko = 'R';
          }else{
            yoko = 'L';
          }
 
          for(int i = 0; i < Math.abs(points[j][0]); i++){
            System.out.print(yoko);
          }
          for(int i = 0; i < Math.abs(points[j][1]); i++){
            System.out.print(tate);
          }
          for(int i = 0; i < (21 - Math.abs(points[j][1]) - Math.abs(points[j][0])) / 2; i++){
            System.out.print("UD");
          } 
 
          System.out.println("");
        }
 
      }
    }else{
      System.out.println("-1");
    }
 
  }
 
 //ここからテンプレ
  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問題の満点は無理そうで諦め、E問題に行ってみるもののテストケースの半分くらい正解までしかできず、タイムアップ・・・・
今見ると、E問題はグラフではなく"木"という制限があったんですね。いや分かってても解けませんでしたが。


さてさて、D問題の部分点までの獲得に1時間弱かかったものの、結果は・・・・
パフォーマンスは1600でした！！！
AtCoder Beginner Contestでいくらはやく全問正解してもパフォーマンスは1600がマックスですから、Regular Contestに出たのは正解ということになります。できれば1600より大きいパフォーマンス値を取りたかったですが・・・・

というわけで、今後もBeginnerとRegularの2つが同時開催の場合は、勇気を出してRegularに出場したいと思っています。
1600を超えて、Aランクになるぞー！引き続き頑張るぜよ。以上です。