Overall Editorial by cirno3153
このユーザー解説はJava/Kotlinにおける実装例を紹介するものとなっています。
A問題 - A Unique Letter
愚直に実装するならば条件式を並べれば良いですが、あえてそうではない実装を紹介します。
\(F(x)\) を文字 \(x\) の出現回数とします。 この時、 \(F(x)=1\) なる \(x\) が存在するかを判定すれば良いです。
\(F(x)\) は写像なので、つまりMap(Mapは写像という意味です)を使えばよいです。 今回の場合は文字の種類数が十分に少ないので、配列を用いて個数を管理しても構いません。
計算量は \(O(|S|)\) です。
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)) {
char[] S = sc.next().toCharArray();
int[] frequency = new int[26]; // 度数分布を管理する
for (char c : S) ++ frequency[c - 'a']; // ASCII上でアルファベットは連続しているので、これで文字を[0, 26)の範囲にマッピングできる
for (int i = 0;i < frequency.length;++ i) {
if (frequency[i] == 1) { // 1個だけ出現する文字が見つかったなら
out.println((char)(i + 'a'));
return;
}
}
out.println(-1);
}
}
}
Kotlinの実装例
import java.util.Scanner
fun main() {
Scanner(System.`in`).use { sc ->
val S = sc.next()
val frequency = IntArray(26) // 度数分布を管理する
for (c in S) ++ frequency[c - 'a'] // ASCII上でアルファベットは連続しているので、これで文字を[0, 26)の範囲にマッピングできる
for (i in frequency.indices) {
if (frequency[i] == 1) { // 1個だけ出現する文字が見つかったなら
println((i + 'a'.toInt()).toChar())
return
}
}
println(-1)
}
}
B問題 - Better Students Are Needed!
適切にソートをする問題です。
Java/Kotlinでは比較関数を渡してソートすることができ、しかもそのソートは安定ソートです。
従って、単に3回ソート関数を渡せば良いですね。
実装上は6回ソートをするのが楽なのでそうしています。
Javaの実装例
import java.util.ArrayList;
import java.util.Comparator;
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(), X = sc.nextInt(), Y = sc.nextInt(), Z = sc.nextInt();
int[] A = new int[N];
for (int i = 0;i < N;++ i) A[i] = sc.nextInt();
int[] B = new int[N];
for (int i = 0;i < N;++ i) B[i] = sc.nextInt();
ArrayList<Integer> candidate = new ArrayList<>(N);
for (int i = 0;i < N;++ i) candidate.add(i);
candidate.sort((l, r) -> Integer.compare(A[r], A[l]));
candidate.subList(X, N).sort(Comparator.naturalOrder());
candidate.subList(X, N).sort((l, r) -> Integer.compare(B[r], B[l]));
candidate.subList(X + Y, N).sort(Comparator.naturalOrder());
candidate.subList(X + Y, N).sort((l, r) -> Integer.compare(A[r] + B[r], A[l] + B[l]));
candidate.subList(0, X + Y + Z).sort(Comparator.naturalOrder());
for (int i : candidate.subList(0, X + Y + Z)) out.println(i + 1);
}
}
}
Kotlinの実装例
import java.util.Scanner
fun main() {
Scanner(System.`in`).use { sc ->
val N = sc.nextInt()
val X = sc.nextInt()
val Y = sc.nextInt()
val Z = sc.nextInt()
val A = IntArray(N) {sc.nextInt()}
val B = IntArray(N) {sc.nextInt()}
val candidate = Array(N) {it}
candidate.sortWith((compareBy<Int> {A[it]}).reversed())
candidate.sort(X, N)
candidate.sortWith((compareBy<Int> {B[it]}).reversed(), X, N)
candidate.sort(X + Y, N)
candidate.sortWith((compareBy<Int> {A[it] + B[it]}).reversed(), X + Y, N)
println(candidate.sliceArray(0 until X + Y + Z).sorted().map {it + 1}.joinToString(separator="\n"))
}
}
C問題 - C - Changing Jewels
\(r_n\) をレベル \(n\) の赤い宝石の個数、 \(b_n\) をレベル \(n\) の青い宝石の個数とします。 初め、 \(r_N = 1\) であり、それ以外は \(0\) です。
問題文の式では宝石を配る形になっていますが、これを貰う形に変更してみます。 すると、 \(r_{n-1} = (1 + X)r_n + b_n\) であり、 \(b_{n - 1} = X Y r_n + Yb_n\) です。
これをそのままコードに落とし込み、 \(b_1\) を出力すれば正答となります。
Javaの実装例
import java.util.ArrayList;
import java.util.Comparator;
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(), X = sc.nextInt(), Y = sc.nextInt();
long[] r = new long[N + 1], b = new long[N + 1];
r[N] = 1;
for (int i = N - 1;i > 0;-- i) {
r[i] = (1 + X) * r[i + 1] + b[i + 1];
b[i] = X * Y * r[i + 1] + Y * b[i + 1];
}
out.println(b[1]);
}
}
}
Kotlinの実装例
import java.util.Scanner
fun main() {
Scanner(System.`in`).use { sc ->
val N = sc.nextInt()
val X = sc.nextInt()
val Y = sc.nextInt()
val r = LongArray(N + 1)
val b = LongArray(N + 1)
r[N] = 1
for (i in N - 1 downTo 1) {
r[i] = (1 + X) * r[i + 1] + b[i + 1]
b[i] = X * Y * r[i + 1] + Y * b[i + 1]
}
println(b[1])
}
}
もう少し計算を高速化してみましょう。
まず、添え字が減っていくのは面倒なので、変数を反転させます。 つまり、最初はレベル \(1\) の赤い宝石が1個から始めて、レベル \(n\) の青い宝石の個数を求めることにします。
従って、与式は以下の形になります。
\( \begin{array}{l} r_{n+1} = (1 + X)r_n + b_n \\ b_{n+1} = X Y r_n + Yb_n \end{array} \)
これを式変形していきます。
\(r_n = \frac{1}{XY}b_{n+1} - \frac{1}{X}b_n\) なので、
\( \begin{array}{ll} & \frac{1}{XY}b_{n+2} - \frac{1}{X}b_{n+1} = (1 + X)(\frac{1}{XY}b_{n+1} - \frac{1}{X}b_n) + b_n \\ \rightarrow & \frac{1}{XY}b_{n+2} - \frac{1 + X + Y}{XY}b_{n+1} + \frac{1}{X}b_n = 0 \\ \rightarrow & b_{n+2} - (1 + X + Y)b_{n+1} + Y b_n = 0 \end{array} \)
これは三項間漸化式なので、三項間漸化式の解き方を用いれば解けます。 \(x^2 - (1+X+Y)x + Y=0\) を満たす二つの解を \(\alpha, \beta\) とすると、二次方程式の解の公式より \(\alpha = \frac{1+X+Y + \sqrt{(1+X+Y)^2-4Y}}{2}, \beta = \frac{1+X+Y - \sqrt{(1+X+Y)^2-4Y}}{2}\) であることが分かります。
これを用いて、
\( \begin{array}{l} b_{n+2} - \alpha b_{n+1} = \beta(b_{n+1} - \alpha b_n) \\ b_{n+2} - \beta b_{n+1} = \alpha(b_{n+1} - \beta b_n) \\ \end{array} \)
が導かれます。 更に式変形すると、
\( \begin{array}{l} b_{n+1} - \alpha b_{n} = \beta^{n-1}(b_2 - \alpha b_1) \\ b_{n+1} - \beta b_{n} = \alpha^{n-1}(b_2 - \beta b_1) \\ \end{array} \)
であり、 \(b_1 = 0, b_2 = XY\) であることから
\( \begin{array}{l} b_{n+1} - \alpha b_{n} = X Y \beta^{n-1} \\ b_{n+1} - \beta b_{n} = X Y \alpha^{n-1} \\ \rightarrow (\alpha - \beta) b_n = XY (\alpha^{n-1} - \beta^{n-1}) \\ \rightarrow b_n = XY\frac{\alpha^{n-1} - \beta^{n-1}}{\alpha - \beta} \end{array} \)
が導かれます。
とはいえ、これは平方根が登場し、とても計算しにくい形です。 別のアプローチから解法を導いてみましょう。
\( \left( \begin{array}{l} r_{n} \\ b_{n} \end{array} \right) = \left( \begin{array}{c} 1 + X & 1 \\ X Y & Y \end{array} \right) \left( \begin{array}{l} r_{n-1} \\ b_{n-1} \end{array} \right) = \left( \begin{array}{c} 1 + X & 1 \\ X Y & Y \end{array} \right) \left( \left( \begin{array}{c} 1 + X & 1 \\ X Y & Y \end{array} \right) \left( \begin{array}{l} r_{n-2} \\ b_{n-2} \end{array} \right) \right)= \cdots = \left( \begin{array}{c} 1 + X & 1 \\ X Y & Y \end{array} \right)^{n-1} \left( \begin{array}{l} r_{1} \\ b_{1} \end{array} \right) \)
です。左辺はそのまま行列累乗をしても \(O(\log n)\) 時間で解けるので、十分高速です。
何故 \(O(\log n)\) で解けるのか？
行列を \(M\) として、 \(M^n\) を求めることを考えます。
もし \(n\) が偶数ならば、 \(M^n = (M^2)^{\frac{n}{2}}\) なので、 計算回数が半分+1回になります。 また、もし \(n\) が奇数ならば \(M^n = M (M^2)^{\frac{n-1}{2}}\) なので、計算回数が半分+2回になります。
つまり、 \(n\) がどんどん半分以下になっていくので、 \(O(\log n)\) 回で \(n=1\) になり、計算量 \(O(\log n)\) が導かれます。
この手法は行列だけでなく、様々な演算で成り立ちます。
集合 \(S\) 及び集合の元に対する二項演算 \(\cdot: (S, S) \rightarrow S\) に対して、次の性質が成り立つとします。
- 結合則: \(a, b, c \in S\) を満たす任意の \(a, b, c\) に対して、 \((a \cdot b) \cdot c = a \cdot (b \cdot c)\) が成り立つ
このような演算を半群と呼びますが、半群ならば先ほどの手法を用いて \(O(log n)\) 回の計算で解くことができます。
例えば \(a^4\) を求める時、 \(a \cdot a \cdot a \cdot a = (a \cdot a) \cdot (a \cdot a)\) であり、これは \(a \cdot a = a^2\) を求めることで \(a^2 \cdot a^2\) となります。
このように、半群であれば演算の順番を変えることができるので、前後で分割して計算し、それを合体させる分割統治法が利用できます。
発展的話題: 沢山の色の宝石が有っても高速に解ける
宝石の色が沢山ある場合でも、連立方程式の形にすることが可能ならば行列になります。
その時の行列を \(M\) とすると、求めたいものは \(M^n\) に初項のベクトル \(v\) を掛けたものです。
実は \(M^n v\) はベクトルの長さを \(k\) として \(O(k^3 + k \log k \log n)\) で求めることができます。
このような方法はBlack Box Linear Algebraと呼ばれており、色々と高速化に役立つので興味があれば調べてみると良いです。参考
D問題 - Draw Your Cards
実際にシミュレーションする方法で解いてみましょう。
まず、シミュレーションするには場の山や、場を作る必要があります。
まずは場の山を管理するクラスDeckを定義します。
Deckは次の機能を持つ必要があります。
- 一番上のカードに書かれた整数の値を得る
- 一番上にカードを一つ重ねる
- 山にあるカードの枚数を得る
- 山にあるカードを列挙する
これら全ての機能を満たすものとしては動的配列やキューがあるので、これを用いて実装すると良いでしょう。
次に、場を管理するクラスFieldを定義します。
Fieldは次の機能を持つ必要があります。
Deckのうち、 \(X\) 以上で最小の値がカードを表にしているもの(存在しなければ空のDeck)を求める
さて、このようなFieldは写像であると考えられます。
つまり、関数 \(f(x)\) を \(x\) を渡すと条件を満たす山を返す写像である、と解釈できます。
特に、 \(X\) 以上で最小のものを求めるという操作はTreeMap.ceilingEntry(X).getValue()に対応していると考えられるので、FieldはTreeMapなどの順序付き写像を用いて実装することができます。
Javaの実装例
import static java.lang.System.out;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.Iterator;
import java.util.Scanner;
import java.util.TreeMap;
public class Main {
public static void main(String[] args) {
try (Scanner sc = new Scanner(System.in)) {
int N = sc.nextInt(), K = sc.nextInt();
int[] ans = new int[N];
Arrays.fill(ans, -1); // 最後まで食べられないなら-1なので、これを単位元にする
Field field = new Field();
for (int turn = 1;turn <= N;++ turn) {
int P = sc.nextInt();
Deck deck = field.put(P); // 場にカードを追加
if (deck.size() >= K) { // カードがK枚以上になったなら、食べる
for (int card : deck) {
ans[card - 1] = turn;
}
field.remove(deck);
}
}
for (int i : ans) out.println(i);
}
}
static class Deck implements Iterable<Integer>{
private ArrayList<Integer> deck;
public Deck(int card) {
deck = new ArrayList<>();
deck.add(card);
}
public int size() {
return deck.size();
}
public int top() {
return deck.get(deck.size() - 1);
}
public void put(int card) {
deck.add(card);
}
@Override
public Iterator<Integer> iterator() {
return deck.iterator();
}
}
static class Field {
private TreeMap<Integer, Deck> decks = new TreeMap<>();
public Deck put(int card) {
Iterator<Deck> iterator = decks.tailMap(card).values().iterator();
if (iterator.hasNext()) {
Deck deck = iterator.next();
iterator.remove();
deck.put(card);
decks.put(deck.top(), deck);
return deck;
}
Deck deck = new Deck(card);
decks.put(deck.top(), deck);
return deck;
}
public void remove(Deck deck) {
decks.remove(deck.top());
}
}
}
Kotlinの実装例
import java.util.Scanner
import java.util.TreeMap
fun main() {
Scanner(System.`in`).use { sc ->
val N = sc.nextInt()
val K = sc.nextInt()
val ans = IntArray(N) {-1} // 最後まで食べられないなら-1なので、これを単位元にする
val field = Field()
for (turn in 1..N) {
val P = sc.nextInt()
val deck = field.put(P) // 場にカードを追加
if (deck.size() < K) continue // 山がK枚未満なら処理終わり、そうでなければ食べる
for (card in deck) ans[card - 1] = turn
field.remove(deck)
}
for (i in ans) println(i)
}
}
class Deck(card: Int) : Iterable<Int> {
private val deck = mutableListOf<Int>()
init {
deck.add(card)
}
fun size() = deck.size
fun top() = deck.last()
fun put(card: Int) {
deck.add(card)
}
override fun iterator() = deck.iterator()
}
class Field {
private val decks = TreeMap<Int, Deck>()
fun put(card: Int): Deck {
val iterator = decks.tailMap(card).values.iterator()
val deck = if (iterator.hasNext()) {
val tmp = iterator.next()
iterator.remove()
tmp.put(card)
tmp
} else Deck(card)
decks[deck.top()] = deck
return deck
}
fun remove(deck: Deck) {
decks.remove(deck.top())
}
}
余談
上記の解法では計算量 \(O(N \log N)\) ですが、この計算量のボトルネックはTreeMap、つまり \(X\) 以上で最小の要素を求める部分に対応しています。
実はこの部分はPredecessor Dictionary Problemと呼ばれており、van Emde Boas Treeやy-fast Trieを用いることで \(O(N \log \log N)\) に改善することができます。
posted:
last update: