ABC411個人的備忘録[A-C,E]

「450点は確率説」を立証した男の備忘録です

### コンテスト概要
ユニークビジョンプログラミングコンテスト2025 夏（AtCoder Beginner Contest 411）

https://atcoder.jp/contests/abc411

開催日:2025年6月21日 21:00-22:40

## [A - Required Length](https://atcoder.jp/contests/abc411/tasks/abc411_a)
#### 考察
要するに「パスワードの文字数は何文字ですか？」を正しく答えられればほぼ終わり。
これは専門家のlengthを使えばOK。

関数一撃問題は逆に不安になる。

#### 提出
``` c++:A.cpp
#include <bits/stdc++.h>
using namespace std;

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

    //s.length()で文字数を取得
    if(s.length() >= n) cout << "Yes" << endl;
    else cout << "No" << endl;
}
```

## [B - Distance Table](https://atcoder.jp/contests/abc411/tasks/abc411_b)
#### 考察
Nが50なので正直なところ毎回足し算しても何とかなりそう。
今回はセオリー通り累積和で実装。あらかじめ前からの総和を出して置きあとは引き算1回でおしまい。

添え字ミスってタイムロスはよくなかった。

#### 提出
``` c++:B.cpp
#include <bits/stdc++.h>
using namespace std;

int main(){
    int n;
    cin >> n;

    vector<int>sum (n,0);
    //駅[0]から駅[i]までの総和を求める
    for(int i=0;i<n-1;i++){
        int x;
        cin >> x;
        sum[i+1] += sum[i] + x;//前までの総和+区間の長さ
    }

    for(int i=0;i<n-1;i++){
        for(int j=i+1;j<n;j++){
            if(i+1 != j) cout << " ";　//空白区切り
            cout << sum[j] - sum[i];　//累積和の引き算で総和を出力
        }
        cout << endl;
    }
    
}
```

## [C - Black Intervals](https://atcoder.jp/contests/abc411/tasks/abc411_c)
#### 考察
もちろん更新のたびに毎回配列を見てしまうと時間が足りない。
なので、どうやったら連続の数が増える、減るのかを考える。

そうすると、連続している黒が分断されるときに連続数は増え、分断されている黒が接続するときに連続数が減ることがわかる。

なので、各更新ごとに隣の様子を確認してあげれば増えるか、減るか、そのままかがわかる。

全てのクエリに対して、もともとの色に注意しながら両隣を確認すればOK。

#### 提出
``` c++:C.cpp
#include <bits/stdc++.h>
using namespace std;

int main(){
    int n,q;
    cin >> n >> q;

    vector<bool>num (n+2,false);//範囲外を参照しないようにダミーを入れておく
    int ans = 0;//もちろん最初は0

    for(int i=0;i<q;i++){
        int x;
        cin >> x;

        if(num[x]){//今の色が黒の時
            num[x] = false;//とりあえず白にする

            if(num[x-1] && num[x+1]) ans++;//両隣が黒なら分断されるので増える
            else if(!num[x-1] && !num[x+1]) ans--;//両隣が白なら「1の連続」がなくなるので減る。
            //それ以外は変動なし。
        }else{//今が白の場合
            num[x] = true;//とりあえず黒にする

            if(num[x-1] && num[x+1]) ans--;//両隣が黒なら分断されていたのが結合するので減る。
            else if(!num[x-1] && !num[x+1]) ans++;//両隣が白なら「1の連続」が生まれるので増える。
            //それ以外は変動なし。
        }

        cout << ans << endl;//毎回答えを出力
    }
    
}
```

## [D - Conflict 2](https://atcoder.jp/contests/abc411/tasks/abc411_d)
#### 考察
クエリを逆走しそうというとこまでは分かったんですがどうしようもなかったですね。

こんなに歯が立たないD問題は久々ですよ。

## [E - E [max]](https://atcoder.jp/contests/abc411/tasks/abc411_e)
#### 考察
命運分けたE問題。私の苦手な確率問題。だが、D問題がお手上げな以上頑張るしかない。

とりあえず基本的な方針としては「数字Nが最大値になる確率」$\times{N}$を全部足し上げればいい。というわけで「数字Nが最大値になる確率」を求めたい。

が、これが難しい。ある場所でNが出て...かつ他は全部N未満で...でNが出うる場所はいくつあって...それぞれで考えて...と状況が複雑すぎて簡単には求まらない。
なぜ簡単ではないのか？特定の値だといろんなパターンが出てきてしまうからである。なのでもう少し広く範囲でとらえたい。要するに「数字Nが最大値になる確率」ではなく「数字N**以下**が最大値になる確率」を求めてみる。そうすれば各さいころごとにN以下が出る確率をかけるだけで値が求まる。
そうなると「数字Nが最大値になる確率」が求まらないようにも見えるが「数字N以下が最大値になる確率」-「数字N-1以下が最大値になる確率」をすればいいので問題なし。

とはいえ、毎回すべての数字に対して求めているようでは時間が足りない。もっと一気にいろんな確率を出したい。例えばさいころの目が[1,1,1,3,3,6]の時、1~2が出る確率が$\frac{1}{2}$、1~5が出る確率が$\frac{5}{6}$、1~∞が出る確率が$1$となる。
要するに各さいころごとではさほどパターンはないことがわかる。なのでそれぞれの範囲に一気に掛け算をしてしまいたい。

「広い範囲に同じ数の演算をしたい。」セグメントツリーの出番ですね！というわけで「区間積、一点取得」のセグメントツリーを作ります。遅延セグメントツリーでもいいんですが、今回は「区間、一点」なので双対セグメントを採用。
最初値は1にしておいて区間をどんどんかけていく。最後に値ごとに確率を出せば期待値が出る。
ただ全数字でセグメントツリーを作ると時間もメモリも足りないので必要なとこだけに圧縮することも忘れずに。

双対セグメントツリー実践で初めて使ったわりには応用出来て満足。

#### 提出
``` c++:E.cpp
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
ll mod = 998244353LL;
ll inv = 166374059LL;
//1/6をmodしたもの。今回分数は固定なので定数としておく。

template <typename T>
struct ST{//双対セグメント
    vector<T>num;
    int siz;

    ST(int n){
        int x = 1;
        while(n > x) x <<= 1;
        
        siz = x;
        num = vector<T> ((x<<1),1LL);//全部１にする
        num[siz-1] = 0;//0になる確率は0
    }

    void Update_sub(int n,int m,T i,int k,int l,int r){
        //範囲に確率をかけていく。
        if(r <= n || m <= l) return; //範囲外は見ない
        if(n <= l && r <= m){//完全な範囲内は掛ける
            num[k] *= i;
            num[k] %= mod;//modも忘れずに
            return;
        }

        //下の要素を確認
        k *= 2;
        Update_sub(n,m,i,k+1,l,(l+r)/2);
        Update_sub(n,m,i,k+2,(l+r)/2,r);
        return;
    }

    void Update(int n,int m,T i){
        //n番目以上m番目未満の範囲に確率iをかける。
        Update_sub(n,m,i,0,0,siz);                
    }

    
    T Serch(int n){
        //確率を上に上に掛けていく
        int now = n + siz- 1;
        ll ans = num[now];

        while(now != 0){
            now = (now-1)/2;
            ans *= num[now];
            ans %= mod;
        }

        return ans;
    }
};

int main(){
    int n;
    cin >> n;

    vector<vector<ll>>dc (n,vector<ll>(6));//さいころごとに目を管理
    set<ll> st;
    st.insert(0);
    for(int i=0;i<n;i++){
        for(int j=0;j<6;j++){
            cin >> dc[i][j];
            st.insert(dc[i][j]);
        }

        //何かと便利なので昇順に
        sort(dc[i].begin(),dc[i].end());
    }

    map<ll,int>nm;
    //それぞれの目が全体で何番目に小さい数かを管理
    //これで数値を圧縮できる。
    int cnt = 0;
    for(auto x:st){
        nm[x] = cnt;
        cnt++;
    }

    

    ST<ll> tree(st.size());//本丸・双対セグメントツリー
    for(auto vec:dc){
        tree.Update(0,nm[vec[0]],0LL);
        //一番小さい数字未満の数字は確率0
        
        for(ll i=0;i<6;i++){
            if(vec[i+1] != vec[i]){
                //変化のタイミングで更新
                ll prb = inv * (i+1LL);
                //vec[i]以上vec[i]未満の数が出る確率は(i+1)/6
                prb %= mod;
                tree.Update(nm[vec[i]],nm[vec[i+1]],prb);
            }
            //最大の数以降は確率１なので何もしない。
        }
    }

    ll ans = 0,bef = 0;
    for(auto x:st){
        ll p = tree.Serch(nm[x]);//各数字ごとに以下の確率を求める
        ll q = p + mod - bef;//ひとつ前を引きNのみの確率に
        q %= mod;
        bef = p;

        q *= x;
        q %= mod;

        ans += q;　//数字をかけて足し合わせる。
        ans %= mod;
    }
    
    cout << ans << endl;
}
```

## 結果
ABCE 4完　74:48

順位　 1432位
パフォーマンス　1349
レート　1317(+4)

## 感想
大敗北を辛勝に持ち込めたのは大きい。
何より山が当たったのが良かった。
AtCoder Ploblemsの450点問題から確率が多いと予想し、対策したのが生きた。

パフォを上げるためにも苦手を減らしたい所存