AtCoder参戦日記 ABC179 2020/09/19 #3 ― 茶色になる

AtCoderの3回目の参加となった2020/09/19のABC179の記録です。

3完でした。4問目と5問目は、どちらもコードを書きましたが、時間内に正答に至りませんでした。

問題 結果 言語
A Java
B Scala (競技後にPython)
C Scala (競技後にPython)
D 競技後にJava
E 競技後にJava
F

茶色にはなれました。

f:id:suzuki-navi:20201013221841p:plain

A - Plural Form

問題

JavaendsWithに相当するメソッドがほかの言語ですぐに出てこなかったので、Javaで書きました。

import java.util.Scanner;

class Main {
  public static void main(String[] args) {
    var sc = new Scanner(System.in);
    var s = sc.next();
    if (s.endsWith("s")) {
      System.out.println(s + "es");
    } else {
      System.out.println(s + "s");
    }
  }
}

B - Go to Jail

問題

JavaっぽいScalaコードになりました。練習のためにJava/Scala以外の言語を選択すればよかった。。。と思ったので、時間後にPythonで書きました。

object Main extends App {
  val sc = new java.util.Scanner(System.in);
  val n = sc.nextInt();
  val ds = Array.fill(n)((sc.nextInt(), sc.nextInt()));
  val ds2 = ds.map { case (a, b) => a == b }
  var c1: Int = 0;
  var c2: Int = 0;
  (0 until n).foreach { i =>
    if (ds2(i)) {
      c2 += 1;
      if (c1 < c2) {
        c1 = c2;
      }
    } else {
      c2 = 0;
    }
  }
  println(if (c1 >= 3) "Yes" else "No");
}
n = int(input())
ds = [[int(s) for s in input().split()] for _ in range(n)]

count = 0
for i in range(n):
    if ds[i][0] == ds[i][1]:
        count += 1
        if count == 3:
            print("Yes")
            exit(0)
    else:
        count = 0
print("No")

C - A x B + C

問題

この問題においていちばん書きやすいScalaになりました。時間後に練習のためにPythonでも書きました。

object Main extends App {
  val sc = new java.util.Scanner(System.in);
  val n = sc.nextInt();
  val answer = (1 to (n-1)).map(i => (n-1) / i).sum;
  println(answer);
}
n = int(input())
answer = sum([(n - 1) // a for a in range(1, n)])
print(answer)

D - Leaping Tak

問題

動的計画法で素直に解いてTLEになったあと、高速化の手法が思いつきませんでした。

以下は解説を読んだあとに書いたコードです。

import java.util.Scanner;

class Main {
  private static int[] table;
  private static int m = 998244353;
  private static int[][] lrs;

  private static void calc(int x) {
    long sum = table[x - 1];
    if (x == 2) sum = 0;
    for (int i = 0; i < lrs.length; i++) {
      int s = lrs[i][0];
      int e = lrs[i][1];
      if (x - e > 1) {
        sum = (sum + m - table[x - e - 1]) % m;
      }
      if (x - s >= 1) {
        sum = (sum + table[x - s]) % m;
      }
    }
    table[x] = (int)sum;
  }

  public static void main(String[] args) {
    var sc = new Scanner(System.in);
    int n = sc.nextInt();
    int k = sc.nextInt();
    lrs = new int[k][2];
    for (int i = 0; i < k; i++) {
      lrs[i][0] = sc.nextInt();
      lrs[i][1] = sc.nextInt();
    }
    table = new int[n + 1];
    table[1] = 1;

    for (int i = 2; i <= n; i++) {
      calc(i);
    }
    var answer = table[n];
    System.out.println(answer);
  }
}

E - Sequence Sum

問題

m-1 またはその約数で周期性があると思い込んでしまっていたので、WAを解決できませんでした。以下は解説を読んで、勘違いに気がついたあとに書いたコードです。

import java.util.Scanner;

class Main {
  public static void main(String[] args) {
    var sc = new Scanner(System.in);
    long n = sc.nextLong();
    int x = sc.nextInt();
    int m = sc.nextInt();

    long answer = 0;
    int x2 = x;
    long i = 0;

    var s = new int[m];
    var sb = new int[(m + 31) / 32];
    for (; ; i++) {
      if ((sb[x2 / 32] & (1 << (x2 % 32))) != 0) {
        int j = (int)i - 1;
        for (; j >= 0; j--) {
          if (s[j] == x2) {
            break;
          }
        }
        long answer2 = 0;
        for (int k = j; k < i; k++) {
          answer2 += s[k];
        }
        answer += (n - i) / (i - j) * answer2;
        i += (n - i) / (i - j) * (i - j);
        break;
      }
      if (i >= n) break;
      answer += x2;
      s[(int)i] = x2;
      sb[x2 / 32] |= 1 << (x2 % 32);
      x2 = (int)((long)x2 * x2 % m);
    }
    for (; ; i++) {
      if (i >= n) break;
      answer += x2;
      x2 = (int)((long)x2 * x2 % m);
    }

    System.out.println(answer);
  }
}