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

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

エイシング プログラミング コンテスト 2020 に出ました

企業さんが主催ですが、Ratedとのことで参加しました。
atcoder.jp
絶対4完するぞ!と思いながら取り組むも、4問目であるD問題がTLEのまま終了・・・(しかも現在も理由がわかっていない)
ただ、無事レーティングはほぼ変わらずという結果になりました。D問題いつもより難しかったよね。

というわけで、D問題のTLEのコードも含め、書いていきます。A、B問題はメインの部分だけ、C、 D部分はフルなコードを書きます。

A問題

  public static void main(String[] args) {
    InputReader sc = new InputReader(System.in);
 
    int n = sc.nextInt();
    int m = sc.nextInt();
    int d = sc.nextInt();
 
    int ans = 0;
    for(int i = n; i <= m; i++){
      if(i % d == 0){
        ans++;
      }
    }
    System.out.println(ans);
 
 
  }

シンプルに全探索で数え上げ。割り算使って高速なものにもできるが、ミスが怖くこの形に。

B問題

  public static void main(String[] args) {
    InputReader sc = new InputReader(System.in);
 
    int n = sc.nextInt();
    int ans = 0;
    for(int i = 0; i < n; i++){
      int nownum = sc.nextInt();
      if(i % 2 == 0 && nownum % 2 == 1){
        ans++;
      }
    }
 
    System.out.println(ans);
 
  }

これもそのまま探索。今思うと、forループの3つ目のやつ、i++じゃなくてi=i+2にしてたらif文ももう少しシンプルに書けたし、そっちの方がミスしなさそう。

C問題

これのACが出たのが開始から9分半というタイミング。おかげで、あまりレーティングを落とさずに済みました。
Nを固定して探していくのではなく、(x,y,z)のペアを全探索→その結果できるNの値をカウントしていく
というのがポイントですね。
x^2+y^2+z^2+xy+yz+zx という、「おっ因数分解か?」みたいな式にしているのがいやらしい。

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[] sums = new int[n+1];
 
    for(int i = 1; i <= n; i++){
      sums[i] = 0;
    }
 
    for(int x = 1; x < 101; x++){
      for(int y = 1; y < 101; y++){
        for(int z = 1; z < 101; z++){
          int nowsum = x * x + y * y + z * z + x * y + y * z + z * x;
          if(nowsum <= n){
            sums[nowsum]++;
          }
        }
      }
    }
 
    for(int i = 1; i <= n; i++){
      System.out.println(sums[i]);
    }
 
  }
 
 //ここからテンプレ
  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問題

回答と同じように書けたと思うのですが、TLE・・・Schemeだからなのか、どこか致命的な間違いをしているのか?
あと、書きながら考えながらとSchemeを書いていくと毎回かなり汚いコードになってしまうので、そこは直したい。
ちなみに開始から70分で提出しTLEでした。
あと、複数の入力例に対してTLEとACの数がいくつだったか表示されるようになってました!このコードはAC*8、TLE*13でした。このシステム、いいですね。助かる〜

(define n (read))
(define str (read))
(define digitnum (number->string str))
(define (add0 str ketalimit)
  (if (>= (string-length str) ketalimit) str
      (add0 (string-append "0" str) ketalimit)))
(define (ruijo2 i modseed)
  (cond ((= i 0) 1)
        ((= i 1) (modulo 2 modseed))
        ((= (modulo i 2) 0)
         (let* ((half (modulo (ruijo2 (quotient i 2) modseed) modseed))) (modulo (* half half) modseed)))
        (#t (let* ((half (modulo (ruijo2 (quotient (- i 1) 2) modseed) modseed))) (modulo (* 2 half half) modseed)))))
(define (popcount n)
  (cond ((= n 0) 0)
        ((= (modulo n 2) 0) (popcount (quotient n 2)))
        (#t (+ 1 (popcount (quotient n 2))))))
(define (loopcount n);一発目終わった後はこの関数使えばいい、最後に+1
  (if (= n 0) 0
      (+ 1 (loopcount (modulo n (popcount n))))))

(define (string-mod str modseed)
  (define (sub keta sum)
    (cond ((>= keta (string-length str)) sum)
          ((char=? (string-ref str keta) #\0) (sub (+ keta 1) sum))
          (#t (sub (+ keta 1) (modulo (+ sum (ruijo2 (- (string-length str) (+ keta 1)) modseed)) modseed)))))
  (sub 0 0))
(define (count1 str)
  (define (sub keta sum)
    (cond ((>= keta (string-length str)) sum)
          ((char=? (string-ref str keta) #\1) (sub (+ keta 1) (+ sum 1)))
          (#t (sub (+ keta 1) sum))))
  (sub 0 0))

(define (baseplus str) (string-mod str (+ (count1 str) 1)))
(define (baseminus str)
  (if (<= (count1 str) 1) 0 (string-mod str (- (count1 str) 1))))

(define numberstring (add0 digitnum n))
(define basefor1 (baseminus numberstring))
(define basefor0 (baseplus numberstring))
(define have1 (count1 numberstring))

(define (solve str)
  (define (sub keta)
    (cond ((>= keta (string-length str)) 0)
          ((char=? (string-ref str keta) #\0)
           (let* ((afteroneloop (modulo (+ basefor0 (ruijo2 (- (string-length str) (+ keta 1)) (+ have1 1))) (+ have1 1)))
                  (answer (+ 1 (loopcount afteroneloop))))
             (begin (display answer) (newline) (sub (+ keta 1)))))
          (#t (if (= have1 1) (begin (display "0") (newline) (sub (+ keta 1)))
                  (let* ((afteroneloop (modulo (+ (- have1 1) (- basefor1 (ruijo2 (- (string-length str) (+ keta 1)) (- have1 1)))) (- have1 1)))
                         (answer (+ 1 (loopcount afteroneloop))))
                    (begin (display answer) (newline) (sub (+ keta 1))))))))
  (sub 0))
  
(solve numberstring)


そして結果は
パフォーマンス:1228
レーティング:1238 → 1237 (-1)
でした。
9月あたりにガッツリ勉強の時間取れそうなので、青色目指してがんばっぺ