AtCoderの3回目の参加となった2020/09/19のABC179の記録です。
3完でした。4問目と5問目は、どちらもコードを書きましたが、時間内に正答に至りませんでした。
問題 | 結果 | 言語 |
---|---|---|
A | ○ | Java |
B | ○ | Scala (競技後にPython) |
C | ○ | Scala (競技後にPython) |
D | 競技後にJava | |
E | 競技後にJava | |
F |
茶色にはなれました。
A - Plural Form
JavaのendsWith
に相当するメソッドがほかの言語ですぐに出てこなかったので、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); } }