B - AtCoder Language Editorial
by 
E869120
注意：解説の最後に「解法の思いつき方」が掲載されています。ぜひ本文を読んだ後にご覧ください。
ステップ 1
まず、以下の \(2\) つの事柄はまったく同じです。
- すべての \(K\) 文字の部分列が異なる
- どの「\(2\) つの同じ文字」の間にも \(N-K\) 文字以上入っている
したがって、2. を満たす文字列の数を \(998244353\) で割った余りがそのまま答えになります。
具体例 1
\(5\) 文字の文字列 abacb について、\(K = 4\) の場合を考えましょう。
abacbの \(4\) 文字の部分列はすべて異なるため、1. は Yes です。- \(2\) つの同じ文字としては「\(1, 3\) 文字目」「\(2, 5\) 文字目」がありますが、いずれも間に \(5-4=1\) 文字以上入っているため、2. も Yes です。
具体例 2
\(5\) 文字の文字列 abacb について、\(K = 3\) の場合を考えましょう。
abacbの \(3\) 文字の部分列は、\(1, 4, 5\) 文字目を抜き出したacbと \(3, 4, 5\) 文字目を抜き出したacbが同じになるため、1. は No です。- \(2\) つの同じ文字としては「\(1, 3\) 文字目」「\(2, 5\) 文字目」がありますが、前者は間に \(5-3=2\) 文字以上入っていないため、2. も No です。
証明 (2. が No の場合 1. も No)
2 が No である場合、以下のような方法で \(2\) つの \(K\) 文字の同じ部分列を得ることができるため、1. も No となります。
- 文字列の \(a\) 文字目と \(b\) 文字目が同じであり、その間に \(N-K\) 文字未満しか入っていないとする。
- ここで以下の \(2\) つの部分列を考える。
- (a) 文字列の \(1, 2, \dots, a-1,a, b+1, \dots, N\) 文字目を抜き出した部分列。
- (b) 文字列の \(1, 2, \dots, a-1,b, b+1, \dots, N\) 文字目を抜き出した部分列。
- (a) と (b) は文字列として同じであり文字数が \(K\) 以上であるため、(a) と (b) の最初 \(K\) 文字は「\(2\) つの \(K\) 文字の同じ部分列」になっている。
たとえば文字列 codeforces の場合、下図のようにして \(5\) 文字の同じ部分列を得ることができます。ここでは \(N = 10, K = 5\) であることに注意してください。
証明 (1. が No の場合 2. も No)
1 が No であり、特に以下の 2 つの (異なる場所から抜き出した) 部分列が同じであるとします。
- 文字列の \(s_1, s_2, \dots, s_K\) 文字目を順に抜き出した部分列
- 文字列の \(t_1, t_2, \dots, t_K\) 文字目を順に抜き出した部分列
このとき、すべての \(i\) について \(|t_i - s_i| \leq N - K\) を満たします。この理由は以下の通りです。なお、ここでは \(s_i \leq t_i\) を仮定して証明していますが、そうでない場合も \(s\) と \(t\) を逆にすると証明できます。
- \(s_i\) は部分列の前から \(i\) 文字目なので、\(s_i \geq i\)
- \(t_i\) は部分列の後ろから \(K-i+1\) 文字目なので、\(t_i \leq N-K+i\)
- したがって \(t_i - s_i \leq N-K\)
ここで、部分列 \(s\) と \(t\) が異なる場所から抜き出されているため、\(s_i \neq t_i\) を満たす \(i\) が存在します。しかしこのような \(i\) でも \(|t_i - s_i| \leq N - K\) が満たされるため、ある \(2\) つの同じ文字の間に \(N-K\) 文字未満しか入っていないことになり、2. が No であるとわかります。
ステップ 2
それでは、どの「\(2\) つの同じ文字」の間にも \(N-K\) 文字以上入っている AtCoder 語の文字列は何通りあるのでしょうか。まずは例として、\(N = 5, K = 3\) であり文字種が a から z までの \(26\) 個ある場合を考えてみましょう。\(1, 2, 3, 4, 5\) 文字目の順に考察していくと、
- \(1\) 文字目の決め方：何でも良いので \(26\) 通り
- \(2\) 文字目の決め方：\(1\) 文字目と被ってはいけないので \(25\) 通り
- \(3\) 文字目の決め方：\(1, 2\) 文字目と被ってはいけないので \(24\) 通り
- \(4\) 文字目の決め方：\(2, 3\) 文字目と被ってはいけないので \(24\) 通り
- \(5\) 文字目の決め方：\(3, 4\) 文字目と被ってはいけないので \(24\) 通り
となり、答えが \(26 \times 25 \times 24 \times 24 \times 24 = 8985600\) 通りであるとわかります。
また、一般の場合も同様に考えると、\(i\) 文字目の決め方のパターン数が以下のようになります。
- \(i \leq N-K\) のとき：\(\max(0, L+1-i)\) 通り
- \(i > N-K\) のとき：\(\max(0, L-(N-K))\) 通り
したがって、以下の実装例のようなプログラムを書くと AC となります。計算量は \(O(N)\) ですが、本問題の制約は \(N \leq 500000\) なので実行時間制限に間に合います。
実装例 (C++)
#include <iostream>
using namespace std;
const long long mod = 998244353;
long long N;
long long K;
long long L;
long long Answer;
int main() {
// Step 1. 入力
cin >> N >> K >> L;
// Step 2. 計算
Answer = 1;
for (int i = 1; i <= N; i++) {
if (i <= N - K) {
Answer *= max(0LL, L + 1 - i);
}
else {
Answer *= max(0LL, L - (N - K));
}
Answer %= mod; // オーバーフローしないように毎回 mod を取る
}
// Step 3. 出力
cout << Answer << endl;
return 0;
}
実装例 (Python)
# Step 1. 入力
N, K, L = map(int, input().split())
# Step 2. 計算
Answer = 1
for i in range(1, N + 1):
if i <= N - K:
Answer *= max(0, L + 1 - i)
else:
Answer *= max(0, L - (N - K))
Answer %= 998244353 # オーバーフローしないように毎回 mod を取る
# Step 3. 出力
print(Answer)
補足：どうやって解法を思いつくか？
皆さんの中には、この問題の解法を思いつくには「天才的なひらめき」が必要なのではないかと思う方もいると思います。特に、ステップ 1 の考察はかなり非自明で思いつくのが難しいと感じた方も多いでしょう。しかし、適切な手順を踏めば、ひらめきがなくても思いつくことが可能です。
解説を見る
まずは \(K = 1\) の場合、特に \((N, K, L) = (4, 1, 26)\) の場合を考えてみましょう。
- この場合はすべての文字が異なっていなければなりません。
- したがって、答えは \(26 \times 25 \times 24 \times 23\) という式になります。
次に \(K = 2\) の場合、特に \((N, K, L) = (4, 2, 26)\) の場合を考えてみましょう。
- もちろん、すべての文字が異なっている場合は明らかに条件を満たします。
- それでは、そうでない場合はどうでしょうか。
- まず、文字列
javaの場合、\(1, 2\) 文字目と \(1, 4\) 文字目の部分列が同じになり、条件を満たしません。 - また、文字列
kissの場合、\(1, 3\) 文字目と \(1, 4\) 文字目の部分列が同じになり、条件を満たしません。
- まず、文字列
- このように考えると、ほとんどのケースでは条件を満たさないことがわかります。
- しかし考察を進めると、
aquaのように最初と最後の文字が同じ場合だけは例外であるとわかります。 - したがって、答えは \(26 \times 25 \times 24 \times 24\) という式になります。
ここで、なぜ最初と最後の文字が同じ場合だけ例外になるかを考えてみましょう。
- \(a\) 文字目と \(b\) 文字目が同じであるとします \((a < b)\)。
- もし \(a \neq 1\) の場合、\(1, a\) 文字目と \(1, b\) 文字目の部分列が同じになり、条件を満たしません。
- もし \(b \neq N\) の場合、\(a, N\) 文字目と \(b, N\) 文字目の部分列が同じになり、条件を満たしません。
- しかし \((a, b) = (1, N)\) の場合、このような部分列の取り出し方はできないため、例外になります。
それでは、この考え方を \(K=3\) の場合に応用できないのでしょうか。
- \(a\) 文字目と \(b\) 文字目が同じであるとします \((a < b)\)。
- もし \(a \geq 3\) の場合、\(1, 2, a\) 文字目と \(1, 2, b\) 文字目の部分列が同じになり、条件を満たしません。
- もし \(b \leq N - 2\) の場合、\(a, N-1, N\) 文字目と \(b, N-1, N\) 文字目の部分列が同じになり、条件を満たしません。
- もし \(a \geq 2\) かつ \(b \leq N - 1\) の場合、\(1, a, N\) 文字目と \(1, b, N\) 文字目の部分列が同じになり、条件を満たしません。
- 上記以外の文字列としては
pastaやstarsなどがありますが、これらは条件を満たしそうです。 - それでは、前述の \(3\) 条件をまとめてみましょう。
- まとめると、\(b-a \leq N-3\) のとき条件を満たさないと分かります。
- つまり、\(2\) つの同じ文字の間隔が \(N-3\) 文字以下であるとき条件を満たしません。
これで ステップ 1 と非常に近い形になりました。ここまで考察が進めば、\(K \geq 4\) の場合を解くのもそれほど難しくないはずです。
このように、競技プログラミングでは小さい入力の場合に答えがどうなるかを考えると、自然に問題が解けてしまう場合があります。ARC では頻出のテクニックですので、ぜひ覚えておくようにしましょう。
posted:
last update: