問題
6
6
タイピング大会 (Typing Contest)
解説担当：米田寛峻 (square1001)
## 小課題 1（累計 2 点） この小課題では、文字列 $S$ は `AAA...A` の形をしているので、タイピング大会の参加者は同じキーを $N$ 回打ち続けることになります。したがって、答えは $A_1 \times N$ ミリ秒であり、これを出力するプログラムを書けば小課題 1 に正解します。 ```cpp #include <string> #include <iostream> using namespace std; int main() { // 入力 int N; string S; int Q; long long A, L, R; cin >> N >> S >> Q >> A >> L >> R; // 出力 cout << A * N << endl; return 0; } ``` 注意点として、この問題の制約は $1 \leqq N \leqq 10^6$ および $1 \leqq A_i \leqq 10^{11}$ であるため、答えは最大で $10^{17}$ になります。そのため、例えば C++ で int 型を使った場合、int 型の整数が扱える範囲に収まりきらず 「オーバーフロー」 が起こります。その代わりに long long 型などを使いましょう。（※ Python の場合はあまり気にする必要はありません。） ## 小課題 2・3（累計 9 点） 小課題 3 では、文字列 $S$ は `A`, `B`, `C` の 3 種類からなります。ここで、`A`, `B`, `C` のキーをひとつながりの位置に置けば、`D` 以降のキーのことを考えずに「キーボードに `A`, `B`, `C` の 3 つのキーを配置する」と思っても大丈夫です。 このように考えると、キーボードの配置 `ABC`, `ACB`, `BAC`, `BCA`, `CAB`, `CBA` の 6 通りについて、文字列 $S$ を打つのに何ミリ秒かかるかを求めれば、この最小値が答えになります。うまく実装するためには、以下のプログラムのように、キーボードの配置に対してかかる時間を計算する関数を作っておくとよいでしょう。 ```cpp #include <string> #include <iostream> #include <algorithm> using namespace std; // キーボードの配置が与えられたとき、文字列 S を打つのにかかる時間を返す関数 long long calc(int N, string S, long long A, long long L, long long R, string keyboard) { long long cost = 0; for (int i = 0; i < N; i++) { if (i >= 1) { int prev_pos = keyboard.find(S[i - 1]); int next_pos = keyboard.find(S[i]); if (prev_pos < next_pos) { cost += (next_pos - prev_pos) * R; } if (prev_pos > next_pos) { cost += (prev_pos - next_pos) * L; } } cost += A; } return cost; } int main() { // 入力 int N; string S; int Q; long long A, L, R; cin >> N >> S >> Q >> A >> L >> R; // 各キーボードの配置に対して、タイピングにかかる時間の計算 long long CostABC = calc(N, S, A, L, R, "ABC"); long long CostACB = calc(N, S, A, L, R, "ACB"); long long CostBAC = calc(N, S, A, L, R, "BAC"); long long CostBCA = calc(N, S, A, L, R, "BCA"); long long CostCAB = calc(N, S, A, L, R, "CAB"); long long CostCBA = calc(N, S, A, L, R, "CBA"); // 出力 cout << min({ CostABC, CostACB, CostBAC, CostBCA, CostCAB, CostCBA }) << endl; return 0; } ``` ## 小課題 4（累計 18 点） 小課題 4 では、文字が最大で 8 種類あります。$S$ に含まれる文字の種類数を $K$ とすると、キーボードの配置は $K! = 1 \times 2 \times \cdots \times K$ 通りあります。例えば、$K = 8$ なら 40320 通りです。 小課題 3 と同様、これを全探索したいです。ここで、配列や文字列の並び替えを全探索するのは、C++ では `next_permutation`、Python では `itertools.permutations` を使うことでできます。 ```cpp // C++ による実装（小課題 4）：calc 関数は省略（小課題 3 の実装の通り） int main() { // 入力 int N; string S; int Q; long long A, L, R; cin >> N >> S >> Q >> A >> L >> R; // キーボードの配置を全探索 string keyboard = "ABCDEFGH"; long long answer = 9'000'000'000'000'000'000; // 最初は非常に大きい値にセット do { // keyboard = "ABCDEFGH", "ABCDEFHG", "ABCDEGFH", ..., "HGFEDCBA" の順に 8! = 40320 通りそれぞれに対して処理が行われる long long cost = calc(N, S, A, L, R, keyboard); answer = min(answer, cost); } while (next_permutation(keyboard.begin(), keyboard.end())); // 出力 cout << answer << endl; return 0; } ``` ```python # Python による実装（小課題 4） import itertools # キーボードの配置が与えられたとき、文字列 s を打つのにかかる時間を返す関数 def calc(n, s, a, l, r, keyboard): pos = [ keyboard.index(s[i]) for i in range(n) ] cost = a for i in range(n - 1): if pos[i] < pos[i + 1]: cost += r * (pos[i + 1] - pos[i]) if pos[i] > pos[i + 1]: cost += l * (pos[i] - pos[i + 1]) cost += a return cost # 入力 n = int(input()) s = input() q = int(input()) a, l, r = map(int, input().split()) # キーボードの配置を全探索 answer = 10 ** 20 for keyboard in itertools.permutations('ABCDEFGH', 8): subanswer = calc(n, s, a, l, r, keyboard) answer = min(answer, subanswer) # 出力 print(answer) ``` C++ や Python などの標準ライブラリに頼らずとも、再帰関数を使って同様の全探索を行うことができます。興味のある方はぜひインターネットなどで調べてみましょう。 小課題 3 の実装例にある `calc` 関数をそのまま使うと計算量は $O(K! \times K \times N)$ になりますが、どのキーがどの位置にあるかを前計算しておけば計算量 $O(K! \times N)$ になります。前者の計算量でも、C++ などの高速な言語であれば十分余裕をもって実行時間制限に間に合います。 ## 小課題 5（累計 32 点） 小課題 5 でも文字の種類数は最大 8 個ですが、$N \leqq 10^6$ なので小課題 4 の解法では TLE になってしまいます。何か工夫をして、キーボードの配置に対して文字列 $S$ を打つのにかかる時間を高速に求められないでしょうか。 ここで、"同類のもの" をまとめて考えて効率化しましょう。$i$ 文字目のキーから $i+1$ 文字目のキーに移動するのにかかる時間は、ペア $(S[i], S[i+1])$ によって決まります。このペア $(S[i], S[i+1])$ としてあり得るパターンは $K^2 \leqq 64$ 通りしかありません。それぞれのペアが何カ所に現れるのかを前もって計算しておけば、各キーボードの配置に対して $O(K^2)$ で答えが求められます。 例えば、文字列 `ABCACCABBCACACABCAABBCCCCCCCCA` をタイピングすることを考えます。このとき、各 (前の文字, 次の文字) のペアの出現数は以下の表のようになります。 | **前＼後** | **A** | **B** | **C** | |:-:|:-:|:-:|:-:| | **A** | 1 | 4 | 3 | | **B** | 0 | 2 | 4 | | **C** | 7 | 0 | 8 | ここで、例えば $A = 99, L = 50, R = 70$、キーボードの配置が `BAC` の場合： * A → B に移動するのに 50 ミリ秒、B → C に移動するのに 140 ミリ秒、C → A に移動するのに 50 ミリ秒、A → C に移動するのに 70 ミリ秒かかります。 * そのため、移動だけで 50×4 + 140×4 + 50×7 + 70×3 = 1320 ミリ秒、と求まります。 * キーを打つのにかかる時間も含めると、1320 + 99×30 = 4290 ミリ秒、と求まります。 このように、文字列 $S$ がいくら長かったとしても、(前の文字, 次の文字) のペアの出現数の表さえ作ってしまえば、各キーボードの配置に対してすぐに答えが求められます。 これを C++ で実装すると以下のようになります。計算量は $O(N + K! \times K^2)$ であり、小課題 5 に正解します。 ```cpp #include <string> #include <vector> #include <iostream> #include <algorithm> using namespace std; int main() { // 入力 int N; string S; int Q; long long A, L, R; cin >> N >> S >> Q >> A >> L >> R; // 各 (前の文字, 後の文字) の出現数を前計算する const int K = 8; vector<vector<int> > table(K, vector<int>(K, 0)); for (int i = 0; i < N - 1; i++) { int prev_char = int(S[i] - 'A'); int next_char = int(S[i + 1] - 'A'); table[prev_char][next_char] += 1; } // キーボードの配置を全探索 vector<int> perm(K); for (int i = 0; i < K; i++) { perm[i] = i; } long long answer = 9'000'000'000'000'000'000; // 最初は非常に大きい値にセット do { // キーボードの配置を表す数列 perm を全探索（例：perm = { 3, 5, 1, 2, 4, 6, 7, 0 } はは位置 "DFBCEGHA" に対応） long long cost = 0; for (int i = 0; i < K; i++) { for (int j = 0; j < K; j++) { // 「左から i 番目のキー」から「左から j 番目のキー」に移動するケース // 1 回あたりの時間 unit_cost を求める（i < j なら (j - i) * L, i >= j なら (i - j) * R） long long unit_cost = (i < j ? (j - i) * L : (i - j) * R); cost += table[perm[i]][perm[j]] * unit_cost; } } cost += A * N; // キーを打つのにかかる時間も足す answer = min(answer, cost); } while(next_permutation(perm.begin(), perm.end())); // 出力 cout << answer << endl; return 0; } ``` ## 小課題 6（累計 58 点） この小課題を特にあたって重要な考察は、左に移動する回数と、右に移動する回数の差が、最初に打つキーと最後に打つキーの位置関係だけで決まるということです。 例えば、下図では `EACHBAG` という文字列を、`ABCDEFGHIJ` と並んだキーボードで打つ例を示しています。ここでは、左に 11 回、右に 13 回移動しているので、右の方が 2 回多いです。なぜなら、最初に打つキー `E` よりも最後に打つキー `G` の方が 2 つ右にあるから、2 回多く右に移動しなければならないからです。  この性質を使って解いてみましょう。次の値を前計算しておくことを考えます。 * $left[d]$：最初に打つキーの場所と最後に打つキーの場所の差が $d$ であるとき、文字列 $S$ を打つために最小で左に何回移動する必要があるか ここで、$left[-K+1], left[-K+2], \dots, left[K-1]$ を前計算しておけば、最終的な答えは $N \times A + left[j] \times L + (left[j] + j) \times R$ の最小値で求まります。したがって、各参加者に対して $O(K)$ で答えを求められるようになりました。全体計算量は $O(N + K! \times K^2 + QK)$ なので、小課題 6 に正解します。 なお、小課題 6 の実装例は [こちらのリンク (C++)](https://www.ioi-jp.org/joig/2022/2023-ho/2023-joig-ho-t6-sample-sub6.cpp) に掲載されています。 ## 小課題 7（累計 81 点） 小課題 7 は動的計画法 (DP) で解くことができます。キーボードの配置を左から順に決めていくことを前提に、以下の値を計算していきます。 * $dp[T]$：既にキーボードに配置した文字の集合が $T$ であるときの、現時点での合計時間の最小値 DP の漸化式は次のようになります。ただし、$c_{a, b}$ を 「文字列 $S$ 中で、文字 $a$ の次に文字 $b$ が来る箇所の個数」 とします（小課題 5 で作った表を思い出してください）。 $$dp[T] = \min_{a \in T}(dp[T \setminus \{a\}]) + L \sum_{x \in T} \sum_{y \notin T} c_{y, x} + R \sum_{x \in T} \sum_{y \notin T} c_{x, y}$$ 少し式が難しいですが、$L \sum_{x \in T} \sum_{y \notin T} c_{y, x} + R \sum_{x \in T} \sum_{y \notin T} c_{x, y}$ の部分は： * 左から $i+1$ 番目のキーから $i$ 番目まで左に移動する回数が 「$x \in T, y \notin T$ となる $(x, y)$ に対する $c_{y, x}$ の合計」 で * 左から $i$ 番目のキーから $i+1$ 番目まで右に移動する回数が 「$x \in T, y \notin T$ となる $(x, y)$ に対する $c_{x, y}$ の合計」 で 求められるから、消費時間にその分だけ足される、という意味です。なお、このように $T$ のような集合を記録する DP は「ビット DP」と呼ばれ、$T$ の代わりに 2 進数の値を配列の添字に使います。興味のある方はインターネット等で調べてみましょう。 この漸化式にしたがった DP の計算には、計算量 $O(2^K \times K^2)$ がかかります。ただし、各 $T$ に対して 前計算も含めて考えると、全体計算量は $O(N + 2^K \times K^2)$ となり、小課題 7 に正解します。 （コードは準備中） なお、$Q$ 人の参加者に対して計算する場合は計算量が $O(N + Q \times 2^K \times K^2)$ となり、一見正解しないと思われますが、各 $T$ に対して $\sum_{x \in T} \sum_{y \notin T} c_{y, x}$ と $\sum_{x \in T} \sum_{y \notin T} c_{x, y}$ の値を前計算することによって、計算量を $O(N + 2^K \times K^2 + Q \times 2^K \times K)$ に改善できます。そうすると、実装によっては小課題 6 にも正解できる場合があります。 ## 小課題 8（累計 88 点） $L = R$ の場合は、合計移動回数を最小化することが、タイピングにかかる時間を最小化することになります。合計移動回数は、$A = 0, L = 1, R = 1$ の場合を解けば求まります。したがって、小課題 7 の解法をそのまま使って、全体計算量 $O(N + 2^K \times K + Q)$ で小課題 8 に正解することができます。 ## 小課題 9（累計 100 点） 小課題 6 の解法と小課題 7 の解法を組み合わせると、この問題の最後の小課題を解くことができます。 小課題 6 の解法のアイデアは、最初に打つ文字の位置と最後に打つ文字の位置によって、左に移動する回数と右に移動する回数の差が決まるということでした。つまり、次の値をすべての $(a, b)$ に対して計算すれば、$left[-K+1], left[-K+2], \dots, left[K-1]$ の値が求まります。 * 文字 $S[1]$ のキーと文字 $S[N]$ のキーがそれぞれ左から $a, b$ 番目のキーであるとき、タイピング中に左に移動する回数の最小値はいくつか？ 上の問題の答えは、小課題 7 の DP で計算量 $O(2^K \times K)$ で求まります。ただし、小課題 7 の解説の最後に書かれているように、各 $T$ に対して $\sum_{x \in T} \sum_{y \notin T} c_{y, x}$ と $\sum_{x \in T} \sum_{y \notin T} c_{x, y}$ の前計算を行うものとします。よって、$left[-K+1], left[-K+2], \dots, left[K-1]$ の値は、計算量 $O(2^K \times K^3)$ で求まります。よって、この問題は全体計算量 $O(N + 2^K \times K^3 + QK)$ で解くことができ、満点を獲得することができます。 なお、実装例は [こちらのリンク (C++)](https://www.ioi-jp.org/joig/2022/2023-ho/2023-joig-ho-t6-sample.cpp) および [こちらのリンク (Python)](https://www.ioi-jp.org/joig/2022/2023-ho/2023-joig-ho-t6-sample.py) に掲載されています。
## 小課題 1（累計 2 点） この小課題では、文字列 $S$ は `AAA...A` の形をしているので、タイピング大会の参加者は同じキーを $N$ 回打ち続けることになります。したがって、答えは $A_1 \times N$ ミリ秒であり、これを出力するプログラムを書けば小課題 1 に正解します。 ```cpp #include <string> #include <iostream> using namespace std; int main() { // 入力 int N; string S; int Q; long long A, L, R; cin >> N >> S >> Q >> A >> L >> R; // 出力 cout << A * N << endl; return 0; } ``` 注意点として、この問題の制約は $1 \leqq N \leqq 10^6$ および $1 \leqq A_i \leqq 10^{11}$ であるため、答えは最大で $10^{17}$ になります。そのため、例えば C++ で int 型を使った場合、int 型の整数が扱える範囲に収まりきらず 「オーバーフロー」 が起こります。その代わりに long long 型などを使いましょう。（※ Python の場合はあまり気にする必要はありません。） ## 小課題 2・3（累計 9 点） 小課題 3 では、文字列 $S$ は `A`, `B`, `C` の 3 種類からなります。ここで、`A`, `B`, `C` のキーをひとつながりの位置に置けば、`D` 以降のキーのことを考えずに「キーボードに `A`, `B`, `C` の 3 つのキーを配置する」と思っても大丈夫です。 このように考えると、キーボードの配置 `ABC`, `ACB`, `BAC`, `BCA`, `CAB`, `CBA` の 6 通りについて、文字列 $S$ を打つのに何ミリ秒かかるかを求めれば、この最小値が答えになります。うまく実装するためには、以下のプログラムのように、キーボードの配置に対してかかる時間を計算する関数を作っておくとよいでしょう。 ```cpp #include <string> #include <iostream> #include <algorithm> using namespace std; // キーボードの配置が与えられたとき、文字列 S を打つのにかかる時間を返す関数 long long calc(int N, string S, long long A, long long L, long long R, string keyboard) { long long cost = 0; for (int i = 0; i < N; i++) { if (i >= 1) { int prev_pos = keyboard.find(S[i - 1]); int next_pos = keyboard.find(S[i]); if (prev_pos < next_pos) { cost += (next_pos - prev_pos) * R; } if (prev_pos > next_pos) { cost += (prev_pos - next_pos) * L; } } cost += A; } return cost; } int main() { // 入力 int N; string S; int Q; long long A, L, R; cin >> N >> S >> Q >> A >> L >> R; // 各キーボードの配置に対して、タイピングにかかる時間の計算 long long CostABC = calc(N, S, A, L, R, "ABC"); long long CostACB = calc(N, S, A, L, R, "ACB"); long long CostBAC = calc(N, S, A, L, R, "BAC"); long long CostBCA = calc(N, S, A, L, R, "BCA"); long long CostCAB = calc(N, S, A, L, R, "CAB"); long long CostCBA = calc(N, S, A, L, R, "CBA"); // 出力 cout << min({ CostABC, CostACB, CostBAC, CostBCA, CostCAB, CostCBA }) << endl; return 0; } ``` ## 小課題 4（累計 18 点） 小課題 4 では、文字が最大で 8 種類あります。$S$ に含まれる文字の種類数を $K$ とすると、キーボードの配置は $K! = 1 \times 2 \times \cdots \times K$ 通りあります。例えば、$K = 8$ なら 40320 通りです。 小課題 3 と同様、これを全探索したいです。ここで、配列や文字列の並び替えを全探索するのは、C++ では `next_permutation`、Python では `itertools.permutations` を使うことでできます。 ```cpp // C++ による実装（小課題 4）：calc 関数は省略（小課題 3 の実装の通り） int main() { // 入力 int N; string S; int Q; long long A, L, R; cin >> N >> S >> Q >> A >> L >> R; // キーボードの配置を全探索 string keyboard = "ABCDEFGH"; long long answer = 9'000'000'000'000'000'000; // 最初は非常に大きい値にセット do { // keyboard = "ABCDEFGH", "ABCDEFHG", "ABCDEGFH", ..., "HGFEDCBA" の順に 8! = 40320 通りそれぞれに対して処理が行われる long long cost = calc(N, S, A, L, R, keyboard); answer = min(answer, cost); } while (next_permutation(keyboard.begin(), keyboard.end())); // 出力 cout << answer << endl; return 0; } ``` ```python # Python による実装（小課題 4） import itertools # キーボードの配置が与えられたとき、文字列 s を打つのにかかる時間を返す関数 def calc(n, s, a, l, r, keyboard): pos = [ keyboard.index(s[i]) for i in range(n) ] cost = a for i in range(n - 1): if pos[i] < pos[i + 1]: cost += r * (pos[i + 1] - pos[i]) if pos[i] > pos[i + 1]: cost += l * (pos[i] - pos[i + 1]) cost += a return cost # 入力 n = int(input()) s = input() q = int(input()) a, l, r = map(int, input().split()) # キーボードの配置を全探索 answer = 10 ** 20 for keyboard in itertools.permutations('ABCDEFGH', 8): subanswer = calc(n, s, a, l, r, keyboard) answer = min(answer, subanswer) # 出力 print(answer) ``` C++ や Python などの標準ライブラリに頼らずとも、再帰関数を使って同様の全探索を行うことができます。興味のある方はぜひインターネットなどで調べてみましょう。 小課題 3 の実装例にある `calc` 関数をそのまま使うと計算量は $O(K! \times K \times N)$ になりますが、どのキーがどの位置にあるかを前計算しておけば計算量 $O(K! \times N)$ になります。前者の計算量でも、C++ などの高速な言語であれば十分余裕をもって実行時間制限に間に合います。 ## 小課題 5（累計 32 点） 小課題 5 でも文字の種類数は最大 8 個ですが、$N \leqq 10^6$ なので小課題 4 の解法では TLE になってしまいます。何か工夫をして、キーボードの配置に対して文字列 $S$ を打つのにかかる時間を高速に求められないでしょうか。 ここで、"同類のもの" をまとめて考えて効率化しましょう。$i$ 文字目のキーから $i+1$ 文字目のキーに移動するのにかかる時間は、ペア $(S[i], S[i+1])$ によって決まります。このペア $(S[i], S[i+1])$ としてあり得るパターンは $K^2 \leqq 64$ 通りしかありません。それぞれのペアが何カ所に現れるのかを前もって計算しておけば、各キーボードの配置に対して $O(K^2)$ で答えが求められます。 例えば、文字列 `ABCACCABBCACACABCAABBCCCCCCCCA` をタイピングすることを考えます。このとき、各 (前の文字, 次の文字) のペアの出現数は以下の表のようになります。 | **前＼後** | **A** | **B** | **C** | |:-:|:-:|:-:|:-:| | **A** | 1 | 4 | 3 | | **B** | 0 | 2 | 4 | | **C** | 7 | 0 | 8 | ここで、例えば $A = 99, L = 50, R = 70$、キーボードの配置が `BAC` の場合： * A → B に移動するのに 50 ミリ秒、B → C に移動するのに 140 ミリ秒、C → A に移動するのに 50 ミリ秒、A → C に移動するのに 70 ミリ秒かかります。 * そのため、移動だけで 50×4 + 140×4 + 50×7 + 70×3 = 1320 ミリ秒、と求まります。 * キーを打つのにかかる時間も含めると、1320 + 99×30 = 4290 ミリ秒、と求まります。 このように、文字列 $S$ がいくら長かったとしても、(前の文字, 次の文字) のペアの出現数の表さえ作ってしまえば、各キーボードの配置に対してすぐに答えが求められます。 これを C++ で実装すると以下のようになります。計算量は $O(N + K! \times K^2)$ であり、小課題 5 に正解します。 ```cpp #include <string> #include <vector> #include <iostream> #include <algorithm> using namespace std; int main() { // 入力 int N; string S; int Q; long long A, L, R; cin >> N >> S >> Q >> A >> L >> R; // 各 (前の文字, 後の文字) の出現数を前計算する const int K = 8; vector<vector<int> > table(K, vector<int>(K, 0)); for (int i = 0; i < N - 1; i++) { int prev_char = int(S[i] - 'A'); int next_char = int(S[i + 1] - 'A'); table[prev_char][next_char] += 1; } // キーボードの配置を全探索 vector<int> perm(K); for (int i = 0; i < K; i++) { perm[i] = i; } long long answer = 9'000'000'000'000'000'000; // 最初は非常に大きい値にセット do { // キーボードの配置を表す数列 perm を全探索（例：perm = { 3, 5, 1, 2, 4, 6, 7, 0 } はは位置 "DFBCEGHA" に対応） long long cost = 0; for (int i = 0; i < K; i++) { for (int j = 0; j < K; j++) { // 「左から i 番目のキー」から「左から j 番目のキー」に移動するケース // 1 回あたりの時間 unit_cost を求める（i < j なら (j - i) * L, i >= j なら (i - j) * R） long long unit_cost = (i < j ? (j - i) * L : (i - j) * R); cost += table[perm[i]][perm[j]] * unit_cost; } } cost += A * N; // キーを打つのにかかる時間も足す answer = min(answer, cost); } while(next_permutation(perm.begin(), perm.end())); // 出力 cout << answer << endl; return 0; } ``` ## 小課題 6（累計 58 点） この小課題を特にあたって重要な考察は、左に移動する回数と、右に移動する回数の差が、最初に打つキーと最後に打つキーの位置関係だけで決まるということです。 例えば、下図では `EACHBAG` という文字列を、`ABCDEFGHIJ` と並んだキーボードで打つ例を示しています。ここでは、左に 11 回、右に 13 回移動しているので、右の方が 2 回多いです。なぜなら、最初に打つキー `E` よりも最後に打つキー `G` の方が 2 つ右にあるから、2 回多く右に移動しなければならないからです。  この性質を使って解いてみましょう。次の値を前計算しておくことを考えます。 * $left[d]$：最初に打つキーの場所と最後に打つキーの場所の差が $d$ であるとき、文字列 $S$ を打つために最小で左に何回移動する必要があるか ここで、$left[-K+1], left[-K+2], \dots, left[K-1]$ を前計算しておけば、最終的な答えは $N \times A + left[j] \times L + (left[j] + j) \times R$ の最小値で求まります。したがって、各参加者に対して $O(K)$ で答えを求められるようになりました。全体計算量は $O(N + K! \times K^2 + QK)$ なので、小課題 6 に正解します。 なお、小課題 6 の実装例は [こちらのリンク (C++)](https://www.ioi-jp.org/joig/2022/2023-ho/2023-joig-ho-t6-sample-sub6.cpp) に掲載されています。 ## 小課題 7（累計 81 点） 小課題 7 は動的計画法 (DP) で解くことができます。キーボードの配置を左から順に決めていくことを前提に、以下の値を計算していきます。 * $dp[T]$：既にキーボードに配置した文字の集合が $T$ であるときの、現時点での合計時間の最小値 DP の漸化式は次のようになります。ただし、$c_{a, b}$ を 「文字列 $S$ 中で、文字 $a$ の次に文字 $b$ が来る箇所の個数」 とします（小課題 5 で作った表を思い出してください）。 $$dp[T] = \min_{a \in T}(dp[T \setminus \{a\}]) + L \sum_{x \in T} \sum_{y \notin T} c_{y, x} + R \sum_{x \in T} \sum_{y \notin T} c_{x, y}$$ 少し式が難しいですが、$L \sum_{x \in T} \sum_{y \notin T} c_{y, x} + R \sum_{x \in T} \sum_{y \notin T} c_{x, y}$ の部分は： * 左から $i+1$ 番目のキーから $i$ 番目まで左に移動する回数が 「$x \in T, y \notin T$ となる $(x, y)$ に対する $c_{y, x}$ の合計」 で * 左から $i$ 番目のキーから $i+1$ 番目まで右に移動する回数が 「$x \in T, y \notin T$ となる $(x, y)$ に対する $c_{x, y}$ の合計」 で 求められるから、消費時間にその分だけ足される、という意味です。なお、このように $T$ のような集合を記録する DP は「ビット DP」と呼ばれ、$T$ の代わりに 2 進数の値を配列の添字に使います。興味のある方はインターネット等で調べてみましょう。 この漸化式にしたがった DP の計算には、計算量 $O(2^K \times K^2)$ がかかります。ただし、各 $T$ に対して 前計算も含めて考えると、全体計算量は $O(N + 2^K \times K^2)$ となり、小課題 7 に正解します。 （コードは準備中） なお、$Q$ 人の参加者に対して計算する場合は計算量が $O(N + Q \times 2^K \times K^2)$ となり、一見正解しないと思われますが、各 $T$ に対して $\sum_{x \in T} \sum_{y \notin T} c_{y, x}$ と $\sum_{x \in T} \sum_{y \notin T} c_{x, y}$ の値を前計算することによって、計算量を $O(N + 2^K \times K^2 + Q \times 2^K \times K)$ に改善できます。そうすると、実装によっては小課題 6 にも正解できる場合があります。 ## 小課題 8（累計 88 点） $L = R$ の場合は、合計移動回数を最小化することが、タイピングにかかる時間を最小化することになります。合計移動回数は、$A = 0, L = 1, R = 1$ の場合を解けば求まります。したがって、小課題 7 の解法をそのまま使って、全体計算量 $O(N + 2^K \times K + Q)$ で小課題 8 に正解することができます。 ## 小課題 9（累計 100 点） 小課題 6 の解法と小課題 7 の解法を組み合わせると、この問題の最後の小課題を解くことができます。 小課題 6 の解法のアイデアは、最初に打つ文字の位置と最後に打つ文字の位置によって、左に移動する回数と右に移動する回数の差が決まるということでした。つまり、次の値をすべての $(a, b)$ に対して計算すれば、$left[-K+1], left[-K+2], \dots, left[K-1]$ の値が求まります。 * 文字 $S[1]$ のキーと文字 $S[N]$ のキーがそれぞれ左から $a, b$ 番目のキーであるとき、タイピング中に左に移動する回数の最小値はいくつか？ 上の問題の答えは、小課題 7 の DP で計算量 $O(2^K \times K)$ で求まります。ただし、小課題 7 の解説の最後に書かれているように、各 $T$ に対して $\sum_{x \in T} \sum_{y \notin T} c_{y, x}$ と $\sum_{x \in T} \sum_{y \notin T} c_{x, y}$ の前計算を行うものとします。よって、$left[-K+1], left[-K+2], \dots, left[K-1]$ の値は、計算量 $O(2^K \times K^3)$ で求まります。よって、この問題は全体計算量 $O(N + 2^K \times K^3 + QK)$ で解くことができ、満点を獲得することができます。 なお、実装例は [こちらのリンク (C++)](https://www.ioi-jp.org/joig/2022/2023-ho/2023-joig-ho-t6-sample.cpp) および [こちらのリンク (Python)](https://www.ioi-jp.org/joig/2022/2023-ho/2023-joig-ho-t6-sample.py) に掲載されています。