Overall Editorial by cirno3153
このユーザー解説はJava/Kotlinにおける実装例を紹介するものとなっています。
A問題 - Intersection
区間の共通集合は、 \([\max(L_1, L_2), \min(R_1, R_2)]\) で求めることができます。
この理由を確認しておきましょう。
- \(\max(L_1, L_2) \leq i \leq \min(R_1, R_2)\) を満たす任意の \(i\) に対して、 \(i\) は両方の色で塗られる。
\(\max(L_1, L_2) \leq i \leq \min(R_1, R_2)\) ならば \(L_1 \leq i \leq R_1\) かつ \(L_2 \leq i \leq R_2\) なので、これは正しいです。
- \(i < \max(L_1, L_2)\) か \(\min(R_1, R_2) < i\) を満たす任意の \(i\) に対して、 \(i\) は少なくとも片方の色で塗られない。
\(i < \max(L_1, L_2)\) を満たすならば少なくとも片方の区間より左側にあるので、その色で塗られません。 \(\min(R_1, R_2) < i\) も同様なので、これは正しいです。
\([\max(L_1, L_2), \min(R_1, R_2)]\) が空の区間である可能性も考えると、答えは \(\max(0, \min(R_1, R_2) - \max(L_1, L_2))\) です。
Javaの実装例
import java.util.Scanner;
import static java.lang.System.out;
public class Main {
public static void main(String[] args) {
try (Scanner sc = new Scanner(System.in)) {
int L1 = sc.nextInt(), R1 = sc.nextInt(), L2 = sc.nextInt(), R2 = sc.nextInt();
out.println(Math.max(0, Math.min(R1, R2) - Math.max(L1, L2)));
}
}
}
Kotlinの実装例
import java.util.Scanner
import kotlin.math.max
import kotlin.math.min
fun main() {
Scanner(System.`in`).use { sc ->
val red = sc.nextInt() .. sc.nextInt()
val blue = sc.nextInt() .. sc.nextInt()
println(max(0, min(red.last, blue.last) - max(red.first, blue.first)))
}
}
あるいは、こんな実装もできます。
import java.util.Scanner
fun main() {
Scanner(System.`in`).use { sc ->
val red = sc.nextInt() until sc.nextInt()
val blue = sc.nextInt() until sc.nextInt()
println(red.intersect(blue).size)
}
}
B問題 - Tournament Result
任意の \((i, j)\) に対して、その結果が矛盾しているかを調べれば良いです。
実装上は、まず \(A_{i, j}\) と \(A_{j, i}\) が与えられたときに矛盾しているかを判定する関数を作り、次に各 \((i, j)\) に対してその関数を呼ぶことで矛盾を調べると良いです。
Javaの実装例
import java.util.Scanner;
import static java.lang.System.out;
public class Main {
public static void main(String[] args) {
try (Scanner sc = new Scanner(System.in)) {
int N = sc.nextInt();
char[][] A = new char[N][];
for (int i = 0;i < N;++ i) A[i] = sc.next().toCharArray();
for (int i = 0;i < N;++ i) {
for (int j = 0;j < i;++ j) {
if (!check(A[i][j], A[j][i])) {
out.println("incorrect");
return;
}
}
}
out.println("correct");
}
}
public static boolean check(char i, char j) {
if (i == 'W' && j == 'L') return true;
if (i == 'D' && j == 'D') return true;
if (i == 'L' && j == 'W') return true;
return false;
}
}
Kotlinの実装例
import java.util.Scanner
fun main() {
Scanner(System.`in`).use { sc ->
val N = sc.nextInt()
val A = Array(N) {sc.next()}
for (i in A.indices) {
for (j in 0 until i) {
if (!check(A[i][j], A[j][i])) {
println("incorrect")
return
}
}
}
println("correct")
}
}
fun check(i: Char, j: Char): Boolean {
return when (i) {
'W' -> {j == 'L'}
'D' -> {j == 'D'}
'L' -> {j == 'W'}
else -> {false}
}
}
余談
判定関数ですが、実は技巧的な手法を用いて簡潔に実装することができます。
Wは文字コード \(87\) 、Lは文字コード \(76\) 、Dは文字コード \(68\) です。
これらを \(3\) で割った余りはそれぞれ \(0, 1, 2\) なので、次のような判定方法が存在します。
- \(A_{i, j} + A_{j, i} \equiv 1 \pmod 3\) かつ、その時に限り表は矛盾していない。
C問題 - NewFolder(1)
今までに同じ文字列が何回出現したかが分かる写像があると良いです。
そのような写像を \(f\) とすると、 \(f(x)\) は \(x\) が登場した回数を返す写像です。
つまり、 \(f\) は写像(Map)なので、Mapを用いて管理すると良いです。
Javaの実装例
import java.util.HashMap;
import java.util.Scanner;
import static java.lang.System.out;
public class Main {
public static void main(String[] args) {
try (Scanner sc = new Scanner(System.in)) {
int N = sc.nextInt();
HashMap<String, Integer> count = new HashMap<>(); // 今までに同じ文字列が何回登場したかを管理する関数
while(N --> 0) {
String S = sc.next();
int result = count.merge(S, 1, (l, r) -> l + r) - 1; // 今までに登場した回数を追加するとともに、その前の時の値を求める
out.print(S);
if (result != 0) out.print("(" + result + ")"); // 2回目以降なら括弧で囲まれた値を出力
out.println();
}
}
}
}
Kotlinの実装例
import java.util.Scanner
fun main() {
Scanner(System.`in`).use { sc ->
val N = sc.nextInt()
val count = mutableMapOf<String, Int>() // 今までに同じ文字列が何回登場したかを管理する関数
repeat(N) {
val S = sc.next()
val result = count.merge(S, 1) { l: Int, r: Int -> l + r }!! - 1 // 今までに登場した回数を追加するとともに、その前の時の値を求める
print(S)
if (result != 0) print("($result)") // 2回目以降なら括弧で囲まれた値を出力
println()
}
}
}
D問題 - Flipping and Bonus
まず、 \(B_i\) をカウンタの数値が丁度 \(i\) になった時に貰える連続ボーナスの総和とします。
\(dp_{i, j}\) を、 \(i\) 回目のコイントスが終わった時点でカウンタの数値が \(j\) の時、貰ったお金の総和の最大値と定義します。
この \(dp\) は次のように遷移します。
- \(dp_{i+1, 0} = \underset{0 \leq j \leq i}{\max}(dp_{i, j})\)
- \(dp_{i+1, j} = dp_{i, j-1} + X_i + B_j (1 \leq j \leq i+1)\)
この \(dp\) の初項は \(dp_{0, 0} = 0, dp_{0, j} = -\infty (1 \leq j \leq N)\) であり、求めるべき答えは \( \underset{0 \leq j \leq N}{\max}(dp_{N, j})\) です。 実装上は \(dp_{N+1, 0}\) を求める方が簡単かもしれません。
従ってこれを実装すれば良く、計算量は \(O(N^2)\) です。
Javaの実装例
import java.util.Arrays;
import java.util.Scanner;
import static java.lang.System.out;
public class Main {
public static void main(String[] args) {
try (Scanner sc = new Scanner(System.in)) {
int N = sc.nextInt(), M = sc.nextInt();
int[] X = new int[N + 1];
for (int i = 0;i < N;++ i) X[i] = sc.nextInt();
int[] B = new int[N + 2]; // B[i] は、カウンタが丁度iになった時に貰える連続ボーナス
while(M --> 0) B[sc.nextInt()] += sc.nextInt();
long[][] dp = new long[N + 2][N + 2]; // dp[i][j]は、i回目のコイントスが終わってカウンタがjである時に貰ったお金の総和の最大値 実装を簡便化するため、N+1回目に必ず裏になるコイントスをする
for (int i = 1;i < dp.length;++ i) {
long[] last = dp[i - 1], next = dp[i];
next[0] = last[0];
for (int j = 1;j <= i;++ j) {
next[j] = last[j - 1] + X[i - 1] + B[j];
next[0] = Math.max(next[0], last[j]);
}
}
out.println(dp[N + 1][0]);
}
}
}
Kotlinの実装例
import java.util.Scanner
import kotlin.math.max
fun main() {
Scanner(System.`in`).use { sc ->
val N = sc.nextInt()
val M = sc.nextInt()
val X = IntArray(N + 1) {if (it == N) 0 else sc.nextInt()}
val B = IntArray(N + 2) // B[i] は、カウンタが丁度iになった時に貰える連続ボーナス
repeat(M) { B[sc.nextInt()] += sc.nextInt()}
val dp = Array(N + 2) {LongArray(N + 2)} // dp[i][j]は、i回目のコイントスが終わってカウンタがjである時に貰ったお金の総和の最大値 実装を簡便化するため、N+1回目に必ず裏になるコイントスをする
for (i in 1 until dp.size) {
val last = dp[i - 1]
val next = dp[i]
next[0] = last[0]
for (j in 1..i) {
next[j] = last[j - 1] + X[i - 1] + B[j]
next[0] = max(next[0], last[j])
}
}
println(dp[N + 1][0])
}
}
posted:
last update: