みんなのプロコン 2019 に出ました

AtCoderでみんなのプロコン2019に出ました。ヤフーさんが主催のプロコンです。

最近のパフォーマンス値が良い回と悪い回を振り返ってみると、自分が解ける問題を「いかに早く解けているか」がパフォーマンス値にとても大事なことが分かりました。
ということで、今回の目標は「解ける範囲の問題をめちゃくちゃ速く解く」にしました。
事前に配点を見てみると、100-200-400-600-800-900とのことだったので、「まずB問題まで超速く解く」「C問題もできれば超速く解く」が目標です。

結果としては、"自分が解けるかどうか"である400点のC問題も無事に、しかも速く解くことができました！！
ということで、回答を書いていきます。

A問題

"差が1の組み合わせが出ないように複数の数を選ぶ"の最善策は、1からはじめて 1,3,5,,,と取っていくことです。
よって、K個を最善で選ぶと1,3,5,,, (K - 1) * 2 + 1、となります。この最後の数である「(K - 1) * 2 + 1」がN以下かをチェックすればよいです。
schemeで書きました。

(define a (read))
(define b (read))
 
(display (if (>= a (+ 1 (* 2 (- b 1)))) "YES" "NO"))
(newline)

開始から1:59経過でACでした。

B問題

・同じ街の対の間を結ぶ道が複数あることはありません。
・どの2つの街の間も、道を何本か通ることで行き来することができます。
という条件から、入力として想定されるグラフの良い例と悪い例は以下のようになります。

左が一筆書きできるグラフ

そして各グラフについて、"各頂点から出ている辺の数"を書くと以下のようになります。

一筆書き順に"1-2-2-1"になるのが良いグラフ

ということで、グラフの各頂点から出ている数を調べて、"1-2-2-1"という形になっているか確認します。
ダメな場合は"1-1-1-3"になっています。
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[] nums = new int[4];
    for(int i = 0; i < 4; i++){
      nums[i] = 0;
    }
 
    for(int i = 0; i < 6; i++){
      int point = sc.nextInt();
      nums[point-1]++;
    }
 
    Arrays.sort(nums);
 
    if(nums[3] == 2){
      System.out.println("YES");
    }else{
      System.out.println("NO");
    }
 
  }
 
 //ここからテンプレ
  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);
      }
  }
}

開始から5:15経過でACでした。よしよし

C問題

解けるかどうかと取り組んだC問題でしたが、複雑なアルゴリズムを使う問題ではなかったので何とか解けました・・・！
基本的に、
①ビスケットを叩いて1枚増やす(必要:1ターン)
②「ビスケットA枚⇒1円」⇒「1円⇒ビスケットB枚」で増やす(必要:2ターン)
の2パターンの増やし方があります。
ただ、もちろんA <= Bでないと②は成立しません。
さらによく考えると、A + 1 = B の場合も②が"①よりも得"にはなりません。ビスケットを叩きまくっても同じです。

さて、ではA + 1 < B の場合はどうすればよいかというと、
・ビスケットを叩きまくって枚数をA枚まで持って行く((A-1)ターンかかる)
・交換作戦②を繰り返しまくる(残り行動回数がなくなるまで)
・もしラスト1回残っていたら、最後の行動で叩いて1枚増やす
という作戦を実行することになります。
その際に注意すべきコーナーケースとして「A >= K」の場合があります。そのときは交換作戦に至る前に終わることになります。

さて、上記のことに注意して書いたコードがコチラです。
答えの数がとても大きくなることもあるので、schemeで書きました。

(define K (read))
(define A (read))
(define B (read))
 
(define (solve k a b)
  (if (>= a k) (+ k 1)
      (let* ((nokori (- k (- a 1)))
             (changeget (* (- b a) (quotient nokori 2))))
        (if (= (modulo nokori 2) 1) (+ a 1 changeget)
            (+ a changeget)))))
 
;交換作戦が得にならない場合はすぐ(k+1)を出力
(display (if (>= (+ A 2) B) (+ K 1)
             (solve K A B)))
 
(newline)

開始から19:57経過でACでした。20分切りました！割と速く解けている方では・・・！

そして、D問題にじっくり取り組んだものの、30分以上考えても光明が見えず・・・あえなく脱落でした。
500,600点の問題がこれまでで解けたことないので、400点問題を解いていって地力をつけたいところです。

さて、速く解けたことでパフォーマンス値が上がっていることに期待です。1600超えてたらいいなぁ〜

追記(同日23:35)
パフォーマンス値は1687となり、レーティングあがりました！！！新しいレーティングは1287です。
理論上はこのパフォーマンスを継続できればいつかは青になりますね。早くなりたい〜
仕事でプログラミングをしない中、継続的に勉強頑張っていきたいところです。