解説

3個のサイコロの目をそれぞれ $a, b, c$ とすると、各サイコロについて $1 \le a, b, c \le 6$ となります。

出た目の合計 $a + b + c = X$ において：

• 最小値： $a=1, b=1, c=1$ のとき、3
• 最大値： $a=6, b=6, c=6$ のとき、18

したがって、3つのダイスを振ったとき、3以上18以下の値のすべてを作ることができます。

組み合わせの例（メモより抜粋）

解説

まず、サイコロの面が必ずしも 1, 2, 3, 4, 5, 6 とは限らない点に注意してください。
入力例2のように、同じ数字が複数ある場合や、特定の数字が含まれない場合があります。

解法：全探索

各サイコロは 6 面なので、3 つのサイコロの目の出方は全部で $6 \times 6 \times 6 = 216$ 通りです。
この 216 通りをすべて調べ、条件（4, 5, 6 が 1 つずつ出る）を満たす数を count とすると、答えは count / 216 となります。

条件の判定方法（詳細図解）

画像メモに基づいた、具体的な判定処理のイメージです。

「4, 5, 6 が 1 つずつ出る」という条件を判定するための主な実装例です：

sort(t.begin(), t.end());
if(t[0] == 4 && t[1] == 5 && t[2] == 6){ count++; }

vector<int> temp(7, 0);
for(int i = 0; i < 3; i++){ 
    temp[t[i]]++;
}
if(temp[4] == 1 && temp[5] == 1 && temp[6] == 1){
    count++;
}

int sum = t[0] + t[1] + t[2];
int temp = t[0] * t[1] * t[2];
if(sum == 15 && temp == 120){
    count++;
}

int v1 = t[0], v2 = t[1], v3 = t[2];
if((v1 == 4 && v2 == 5 && v3 == 6) || (v1 == 4 && v2 == 6 && v3 == 5) ||
   (v1 == 5 && v2 == 4 && v3 == 6) || (v1 == 5 && v2 == 6 && v3 == 4) ||
   (v1 == 6 && v2 == 4 && v3 == 5) || (v1 == 6 && v2 == 5 && v3 == 4)){
    count++;
}

使用アルゴリズム：全探索

解説

1. 区間分割の考え方

「部分文字列」は元の文字列から連続した範囲を抜き出したものです。 もし元の文字列に aa や bb のように同じ文字が隣り合っている箇所があれば、その境界をまたいで抜き出した部分文字列は、必ず「同じ文字が隣り合う」ことになり、条件を満たしません。

そのため、同じ文字が連続する地点を「区切り」として文字列を分割し、それぞれの独立した各区間内で条件を満たす部分文字列の数を計算します。

2. 三角数による計数（一般化と具体例）

隣り合う重複がない長さ $n$ の区間において、そこから取り出せる部分文字列の総数は、以下の図のように三角数の形で一般化できます。

3. シミュレーション：区間の抽出

文字列 abbcabbcabcc を左から走査し、同じ文字が隣り合った瞬間にそれまでの文字数を記録します。

使用アルゴリズム：しゃくとり法

#include <bits/stdc++.h>
using namespace std;

int main(void){
    string s;
    cin >> s;

    int l = s.length();
    vector<long long> c;
    int count = 1;

    // 隣り合う文字を比較して区間の長さを確定させる
    for(int i = 1; i < l; i++){
        if(s[i] == s[i-1]){
            c.push_back(count); // 重複地点でそれまでの長さを保存
            count = 1;          // 新しい区間のカウントを開始
        }
        else {
            count++;
        }
    }
    c.push_back(count); // 最後の区間を忘れずに追加

    long long ans = 0;
    long long MOD = 998244353;

    // 各区間の長さ n に対して n*(n+1)/2 を加算
    for(int i = 0; i < c.size(); i++){
        ans += (c[i] * (c[i] + 1) / 2);
        ans %= MOD;
    }

    cout << ans << endl;
    return 0;
}

解説

1. 状態の定義とDPの考え方

C問題との最大の違いは、文字を飛ばして選べる「部分列」である点です。 「今見ている文字を末尾に追加できるか」は、直前に選んだ文字にのみ依存します。

次のように状態を保存していくことで、効率的に計算できます。

2. 遷移のシミュレーション（abbc の場合）

各文字に到達したとき、それ以前の「自分と異なる文字で終わる部分列」の末尾に自分をくっつけることができます。

合計： $1 + 4 + 6 = \mathbf{11}$

3. 遷移式（一般化）

現在見ている文字 $S[i]$ が $x$ ($x \in \{a, b, c\}$) のとき：

例：$S[i] = a$ の場合

$$dp[a]_{\text{new}} = dp[b] + dp[c] + 1$$

使用アルゴリズム：動的計画法 (DP)