Tenka1 Programmer Contest 2019に出ました(1完)

久々にRatedなコンテストに出ました！
atcoder.jp
配点はC=300/D=600/E=800/F=800だったので、目標はCをなんとか解き、他のが奇跡的に解ければ・・・！というところ。

結果としては、C問題が2回WAを出しての開始40分でAC、その後E問題に取り組むも間に合わず時間切れ、という結果でした。
自分なりの解説です。

C問題

最終的にありえる形は
①全部白
②全部黒
③左端からm個白が並んで、その右に(N - m)個の黒が並んでいる
の3パターンのみです。
よって、①、②、そして③の全てのパターン(境界の位置がN-2通り)について、色を変更する必要がある個数を算出しました。

①、②の場合の個数はmincolor、③はansという変数が対応します。
変数の名付け型がダサい。

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();
    String s = sc.nextStr();
 
    int[] nums = new int[n];
    int bb = 0;
 
    for(int i = 0; i < n; i++){
      if(s.charAt(i) == '#'){//#が黒、#=黒=1とする
        nums[i] = 1;
        bb++;
      }else{
        nums[i] = 0;
      }
    }
 
    int mincolor = Math.min(bb, n - bb);
 
    int min = 1000000000;
 
    int[] blackcount = new int[n];//i以下にblackが何個あるか
    if(nums[0] == 1){
      blackcount[0] = 1;
    }else{
      blackcount[0] = 0;
    }
    for(int i = 1; i < n; i++){
      if(nums[i] == 1){
        blackcount[i] = blackcount[i - 1] + 1;
      }else{
        blackcount[i] = blackcount[i - 1];
      }
    }
 
    int[] whitecount = new int[n];//i以上にwhiteが何個あるか
    if(nums[n - 1] == 0){
      whitecount[n-1] = 1;
    }else{
      whitecount[n-1] = 0;
    }
 
    for(int i = n - 2; i >= 0; i--){
      if(nums[i] == 0){
        whitecount[i] = whitecount[i + 1] + 1;
      }else{
        whitecount[i] = whitecount[i + 1];
      }
    }
 
    int ans = 1000000000;
 
    for(int i = 0; i < n-1; i++){
      if(blackcount[i] + whitecount[i+1] < ans){
        ans = blackcount[i] + whitecount[i+1];
      }
    }
 
    if(ans == 1000000000){
      System.out.println(0);
    }else{
      System.out.println(Math.min(ans, mincolor));
    }
 
 
 
  }
 
 //ここからテンプレ
  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);
      }
  }
}

(解けなかったけど)E問題

僕の方針は、
・各係数の最大公約数を出す
・その最大公約数を割りきれる素数が答え
・また、最大公約数が2で割れなかったとしても、2で割れるケースがあることに注意
という解き方かと思います。
最後のは、例えば 7 x^2 - 7 x + 14 という入力例1の場合、因数分解して
7 ( x^2 - x + 2)となりますが、

x^2 - x + 2

は常に偶数となります。
それは、xと x ^ n(n >= 1)の偶奇が常に一致することから証明できます。

この辺りをうまく実装したかったんですが、最後の部分がなぜかちゃんと動作せず、、、あえなくコンテスト終了となりました。
そもそもこの予想はかなり強い制限があるので、上記を満たさないパターンがあった場合アウトです。
なんか数学的にパッと解けるやり方があるのかな・・・？

ただ、最初問題を読んだときに「全然分からんな」と思ったところから、(合ってるかはともかく)解答コードをガリガリ書くところまでいけたのは、コンテストならではの体験だと思います。
集中できる環境って大事ですね。

今後もタイミング合えば積極的に出場したいところです。
とりあえず解説出たら復習するぞー！

追記(23:02)

E問題、数学的に上手いこと解けるやり方ありましたね・・・
また、C問題で①「全部白」②「全部黒」パターンを考えていましたが、それも③に含まれますね。混乱していた・・・

追記(23:08)

パフォーマンスは1233、結果としてレーティングは6ダウンの1281となりました。
C問題の配点が300と「水色ならすぐ解いて当たり前」みたいな基準かと思っていましたが、意外とそうでもなかったようです。
あまり下がらなくて安心するとともに、青色の遠さにしょんぼりします。引き続き頑張ろう・・・！