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

プログラミングの勉強を始めた、情報学専攻の大学院生です。モチベーション維持のため、ブログに勉強したことを書いていきます。→就職。IT全然関係ない仕事をしています

AtCoder Grand Contest 023出ました

AtCoder Grand Contest 023 に出ました。
AtCoder Grand Contest 023 - AtCoder Grand Contest 023 | AtCoder

結果は2問正解でした。
AtCoderのレーティングについて、なんか出始めて序盤(10回以内くらい)はレーティングが低く出る傾向にあるらしいので、頑張って出場していこうと思います。
さて、とりあえず2問分のコード。

1問目。
A: Zero-Sum Ranges - AtCoder Grand Contest 023 | AtCoder
2回WAを出しながら、何とか正答しました。というのも、2回のWAの原因がどっちともintの桁オーバーという・・・もったいない!気を付けよう!

解説動画(下記)では、累積和を取る⇒各地点での累積和をソート⇒同じ数のものがいくつあるか、コンビネーション取りながら数え上げ、でした。
https://www.youtube.com/watch?v=8BHBFMrZ8VM

ただ、そういうやり方が思いつかず、別のやり方で解きました。おそらく上記解説動画でも、僕の解き方でも、オーダーは n * log(n) かと思います。

僕の解き方は、
1.まず、「合計が0のケースが1回あった」をメモ
2.数字を読み込む毎にそれまでの累積和を計算し、「それより前の累積和で同じ数字が出たか?」をチェック
という進め方です。
はじめからn番目までの和がSで、それまでに累積和がSになっていることが2回あった場合、このタイミングで"和が0になる連続した部分列"が2つ見つかったことになりますね、ということです。
コードは下記のような感じ。割とシンプルなコードにできたかと…!
初めてTreeMapという構造を使いました。

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;
import java.util.TreeMap;
import java.math.*;
 
 
 
public class Main {
  public static void main(String[] args) {
    InputReader sc = new InputReader(System.in);
 
    int n = sc.nextInt();
    long sum = 0;
    TreeMap<Long,Long> counters = new TreeMap<>();
    counters.put((long)0,(long)1);
    long count = 0;
 
    for(int i = 0; i < n; i++){
      sum += sc.nextInt();
      if(counters.containsKey(sum)){
        long nowcount = counters.get(sum);
        count += nowcount;
        counters.remove(sum);
        counters.put(sum, nowcount + 1);
      }else{
        counters.put(sum, (long)1);
      }
    }
 
    System.out.println(count);
   
 
  }
 
 //ここからテンプレ
  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);
      }
  }
}


2問目。
B: Find Symmetries - AtCoder Grand Contest 023 | AtCoder

こちらは、とりあえず全探索でやってTLEになったあと、1段階オーダーを落として解けました。
解説動画と同じ解き方かと。
https://www.youtube.com/watch?v=8BHBFMrZ8VM

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;
 
 
 
public class Main {
  public static void main(String[] args) {
    InputReader sc = new InputReader(System.in);
 
    int n = sc.nextInt();
 
    String[] strings = new String[n];
    for(int i = 0; i < n; i++){
      strings[i] = sc.nextStr();
    }
 
    char[][] banmen = new char[n][n];
    int count = 0;
 
    for(int a = 0; a < n; a++){
      // for(int b = 0; b < n; b++){
        for(int i = 0; i < n; i++){
          for(int j = 0; j < n; j++){
            banmen[(i + a) % n][j] = strings[i].charAt(j);
          }
        }
        boolean clear = true;
        for(int i = 0; i < n; i++){
          for(int j = 0; j < n; j++){
            if(banmen[i][j] != banmen[j][i]){
              clear = false;
              break;
            }
          }
        }
        if(clear){
          count += n;
        // }
      }
    }
 
    System.out.println(count);
 
  }
 
 //ここからテンプレ
  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);
      }
  }
}

以上です。
頑張ってレーティングあげてくぞー!