CADDi 2018 for Beginners@AtCoderに出ました

AtCoderでやっていたCADDi 2018 for Beginnersに出ました(前回の大会でレーティングが1200より下に下がったので、Begginnerの方に出ました)。
結果としては3問目までAC、500点問題であったD問題は解けませんでした。
caddi2018b.contest.atcoder.jp
解答など書いていきます。

A問題

数字として扱って解きました。

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 ans = 0;
    for(int i = 0; i < 4; i++){
      if(n % 10 == 2){
        ans++;
      }
      n /= 10;
    }
 
    System.out.println(ans);
 
  }
 
 //ここからテンプレ
  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);
      }
  }
}

B問題

各板について、要請を満たすか見ていくだけです。

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 a = sc.nextInt();
    int b = sc.nextInt();
 
    int ans = 0;
 
    for(int i = 0; i < n; i++){
      int a2 = sc.nextInt();
      int b2 = sc.nextInt();
 
      if(a <= a2 && b <= b2){
        ans++;
      }
    }
 
 
    System.out.println(ans);
 
  }
 
 //ここからテンプレ
  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);
      }
  }
}

C問題

これが少しつまずいた問題でした。2回のTLEを経て、無事ACとなりました。
せっかくなんで、3回の回答を全部書きます。
ちなみに、schemeで書きました。

1回目の提出(TLE)

二分累乗法を書いて、
⓪答えを1としておく
①2^nがpの約数かを調べる⇒約数だったら答えを2に更新
②3^nがpの約数かを調べる⇒約数だったら答えを3に更新
・・・というのを、i^nがpを超えるまで調べ、持っている最新の答えを出力
というアルゴリズムです。

(define n (read))
(define p (read))
 
(define (ruijo n m)
  (cond ((= m 0) 1)
        ((= m 1) n)
        ((= (modulo m 2) 0)
         (let ((sub (ruijo n (quotient m 2)))) (* sub sub)))
        (#t (let ((sub (ruijo n (quotient m 2)))) (* sub sub n)))))
 
(define (ans x max)
  (let ((jo (ruijo x n)))
    (cond ((> jo p) max)
          ((= (modulo p jo) 0) (ans (+ x 1) x))
          (#t (ans (+ x 1) max)))))
 
(display (ans 2 1))
(newline)

これがTLEとなりました(WAとはならず)。
詳細を見ると、サンプルケースのうち6個がTLEでした。

2回目の提出(またまたTLE)

入力がn=1、p=10^12だったときに、試していく数が結局10^12通りになるじゃん！と気付き、n=1のときだけ特別に処理することに。

(define n (read))
(define p (read))
 
(define (ruijo n m)
  (cond ((= m 0) 1)
        ((= m 1) n)
        ((= (modulo m 2) 0)
         (let ((sub (ruijo n (quotient m 2)))) (* sub sub)))
        (#t (let ((sub (ruijo n (quotient m 2)))) (* sub sub n)))))
 
(define (ans x max)
  (let ((jo (ruijo x n)))
    (cond ((> jo p) max)
          ((= (modulo p jo) 0) (ans (+ x 1) x))
          (#t (ans (+ x 1) max)))))
 
;n=1の場合だけ特別な処理
(display (cond ((= n 1) p)
               (#t (ans 2 1))))
(newline)

こちらも結局TLE。
ただ、サンプルケースのうちTLEなのは3つと、少し減りました。

3回目の提出(ACでした！)

自分の環境で入力として、n、pともにありうる最大値である

1000000000000 1000000000000

を入れてみたら、メモリオーバーで出力が出ない。なるほど、累乗に問題があったのか・・・
思うと、nがとんでもなく大きいときには2^nを計算するだけでメチャクチャな大きさになります。
じゃあ、ここを小さくしなければ・・・と考えて、二分累乗法の一部を修正することにしました。
そもそも、1000000000000より大きい数になったら解答としてはどうでもよいので、それ以上は無意味に大きくならないようにしました。
そしたら無事AC！よかったよかった。

(define n (read))
(define p (read))
 
(define (ruijo n m)
  (cond ((= m 0) 1)
        ((= m 1) n)
        ((= (modulo m 2) 0)
         (let ((sub (ruijo n (quotient m 2))))
           (if (>= sub 1000000000001) 1000000000001 (* sub sub))))
        (#t (let ((sub (ruijo n (quotient m 2))))
              (if (>= sub 1000000000001) 1000000000001 (* sub sub n))))))
 
(define (ans x max)
  (let ((jo (ruijo x n)))
    (cond ((> jo p) max)
          ((= (modulo p jo) 0) (ans (+ x 1) x))
          (#t (ans (+ x 1) max)))))
 
(display (cond ((= n 1) p)
               (#t (ans 2 1))))
(newline)

終わりに

そしてD問題を色々考えるも、全く光明が見えず諦めました・・・
500点問題、やはり手強いですね。。。後で解説見て復習せねば。
でも、C問題について2回のTLE(=10分のペナルティ)は防げたと思うので、そういったところはちゃんと確認する癖をつけたいですね。

さて、今回のでレーティングはどうなるか・・・ビビってBeginnerに出ましたが、水色に戻ってたらいいなぁ〜楽しみ。
次は来週のGrandContest。水色から緑に落ちたきっかけとなった憎きコンテスト。頑張ります・・・！！

追記

パフォーマンスは1131、レーティングは1157に下がりました・・・
C問題がTLEナシで出せてたら少しは上がってたんでしょうか？
練習して早く水色になりたいところ・・・！引き続き勉強します。