はまやんはまやんはまやん

hamayanhamayan's blog

Red Polyomino [AtCoder Beginner Contest 211 E]

https://atcoder.jp/contests/abc211/tasks/abc211_e

前提知識

解説

https://atcoder.jp/contests/abc211/submissions/24516205

入力例3を見ると答えの最大数はあまり大きくないので、正しい候補を列挙すればよさそうに見える。
全探索だろうという方針は見えるかもしれないが、実装が今回は問題だと思う。

状態をビットで表現する

まずは状態管理はbitで管理することにしよう。
64箇所について赤にするかしないか2通りであるが、これはunsigned long longを使えばギリギリ入れ込むことができる。
(signedでもできるんかな?ビットで見る分にはできそうだし、llのままでもいいかも)

BFSで列挙していく

BFSによる遷移をK回行うことで、1回の遷移で隣接マスに着色するようにする。
1回目は隣接判定がいらないので、別途やったほうがいい。
自分の実装では1回目だけ別にしている。

隣接マスを塗る場合は、塗られているマス基準で考えるよりも、次塗ろうとしている場所を全通り試して、
そこの隣接に塗られているマスがあるかどうかを見ていくといい。
ビット演算とマスに対する操作に慣れていればそれほど難しくない。

bfsで列挙していくときはかぶっている状態を何回も評価してしまうと遅くなるので、一般的なqueueではなく
setを使ってqueueの役目をさせた。

最後に残った状態が答えの状態となり、その個数が答え。

typedef unsigned long long ull;
int N, K;
string S[8];
int dx[4] = { 0, 1, 0, -1 }, dy[4] = { -1, 0, 1, 0 };
//---------------------------------------------------------------------------------------------------
void _main() {
    cin >> N >> K;
    rep(i, 0, N) cin >> S[i];

    set<ull> que;
    rep(y, 0, N) rep(x, 0, N) if (S[y][x] == '.') que.insert(1ull << (y * N + x));

    rep(k, 1, K) {
        set<ull> nxt;
        fore(cu, que) {
            rep(y, 0, N) rep(x, 0, N) if (S[y][x] == '.' && !(cu & (1ull << (y * N + x)))) {
                bool ok = false;
                rep(d, 0, 4) {
                    int xx = x + dx[d];
                    int yy = y + dy[d];

                    if (0 <= xx && xx < N && 0 <= yy && yy < N) {
                        if (S[yy][xx] == '.' && (cu & (1ull << (yy * N + xx)))) {
                            ok = true;
                        }
                    }
                }
                if (ok) nxt.insert(cu | (1ull << (y * N + x)));
            }
        }
        swap(que, nxt);
    }

    int ans = que.size();
    cout << ans << endl;
}

Nevus [第七回 アルゴリズム実技検定 I]

https://atcoder.jp/contests/past202107-open/tasks/past202107_i

前提知識

解説

https://atcoder.jp/contests/past202107-open/submissions/24478121

幾何問題である。複素数を使って座標を保持しながら、幾何的な操作を行っていくのがいい。
幾何問題はその場でのライブラリ整備はだいぶきついので、ライブラリを作っておく必要がある。
書き下してみると、今回必要となる要素結構多いですね…

  • 座標保持
  • 中点計算
  • 平行移動
  • 中心からの距離
  • 回転角の計算
  • 回転操作

平行移動と回転操作

2つ合わさってくると、複雑なので、どちらかを先に行ってしまって、あとは片方だけというのが理想である。
今回はこの理想を実現することができる。

移動前の頂点についての情報は何一つ分かっていないのだが、実は1つ特徴的な点を作り出すことができる。
それが、目と目の中点である。
移動前の目と目の中点は原点となっているので、移動後の目と目の中点を原点に合わせてやれば、
平行移動を行うことができる。

よって、最初に移動後の目と目の中点を計算し、それが原点になるように平行移動をしておく。
複素数で座標を持っていれば、平行移動はベクトルの加減算なので、中心の座標を全部から引いてやればいい。
これでだいぶ楽になった。

回転移動…の前に

回転移動を次は考えるが、どれだけ回転したかを考えるには、基準となる2つの点を用意する必要がある。
依然として、移動前の座標は何一つ分かっていないように見えるが、実は、平行移動によってEが計算できるようになっている。

開店前の目は原点からの距離がEであるが、原点を中心とした回転移動では距離は変わらないので、
平行移動後の目と原点との距離はEになっていることが分かる。
これでEが求められると移動前の右目の座標(-E,0)が分かるので、移動後と比べてみるとどれだけ回転しているかが
計算可能になった。

回転移動

後は回転角を求めて、すべてのほくろをそれで回転させると答えが得られる。
自分の実装では原点を中心として、移動後の右目の位置から移動前の右目の位置(-E,0)への回転角を求めて、
それを全部のほくろに適用している。
ライブラリが整備されていればこの辺はそれほど難しくない。
///////////////////////// writeup2 end *

int N;
vector<P> eyes, dots;
//---------------------------------------------------------------------------------------------------
void _main() {
    cin >> N;
    rep(i, 0, 2) {
        int x, y; cin >> x >> y;
        eyes.push_back(P(x, y));
    }
    rep(i, 0, N) {
        int x, y; cin >> x >> y;
        dots.push_back(P(x, y));
    }

    // 平行移動
    P center = (eyes[0] + eyes[1]) / 2;
    rep(i, 0, 2) eyes[i] -= center;
    rep(i, 0, N) dots[i] -= center;

    double E = abs(eyes[0]);

    // 回転移動
    double rad = argumentAntiClockwise(P(0, 0), eyes[0], P(-E, 0));
    rep(i, 0, N) {
        P ans = rotate(dots[i], rad);
        printf("%.10f %.10f\n", real(ans), imag(ans));
    }
}

Computer [第七回 アルゴリズム実技検定 O]

https://atcoder.jp/contests/past202107-open/tasks/past202107_o

前提知識

解説

https://atcoder.jp/contests/past202107-open/submissions/24477460

最初の考察方針というのはだいぶパフォーマンスに影響すると思う。
今回の問題も制約が普通で、色々方針が見えそうではある。
DPが正しい方針であるが、それをなんで見出したかといわれるととても困ってしまう。
前置きはいいとして、解説に入ろう。

性質①

まずは重要な性質を取り出しておく。
それは入力に対して適切な変換を施すことで、Bを狭義単調増加にすることができるという部分である。
仮にB[i]≧B[i+1]になっている部分があったとすると、i日目を通過できているということはB[i]円以上の
コンピュータを持っているということであり、i+1日目は必ず通過できることになる。
よって、i+1日目は考慮する必要が無く、ただ所持金が増えるだけの日として、それ以降のBが狭義単調増加している日に
マージしてしまおう。

A B  
===  
2 4  
1 3  
6 8  

となっていたら2日目は何もしなくてもお金が入ってくるので3日目とまとめてしまっていいので、

A B  
===  
2 4  
7 8  

のように変換できる。

この部分がまず分かっていないとこれ以降を理解することは難しい。
(理解はできても実装で困るかも)
自分の実装では前処理として、pre関数にてBが狭義単調増加になるように入力を変換している。
入力によっては最後に何もしなくても所持金が増える場合があるので、その分をpostとして別途分けている。

これ以降は、Bは狭義単調増加していると前提をして説明を進める。

性質②

行動として「好きな金額を支払ってコンピュータを購入できる」という部分が自由度が高い。
自由度が高いと選択肢が増えて取り扱いにくいので、少し考えてみる。
コンピュータを購入する意味は仕事を終えるためなので、仕事をこなすのに必要な金額以上のコンピュータを買う必要性はない。
加えて、自分が今持っているコンピュータより安いコンピュータを買う必要性もない。

よって、もう一つ重要な性質として、とある状況で購入するコンピュータの金額は、今持っているコンピュータより高額で、
配列Bのいずれかの金額に絞ってよいということになる。
これで少なくとも遷移はO(N)におさめることができるようになる。

DPテーブル

問題のDPテーブルは以下のようになる。

dp[i] := i日目の夜の仕事を終えた(その夜に必要なコンピュータを購入済み)ときの所持金の最大値

遷移は結構複雑。

dp[i]からdp[j]への遷移について考えてみよう。
dp[i]の状態ではi日目の夜に必要なコンピュータを持っているので、次の日はこのままでは仕事ができない。
だが、遷移先はdp[j]であるので、i+1日目の昼に買うコンピュータはj日目に必要なものになる。
よって、遷移できる条件はj日目のコンピュータの金額 ≦ dp[i] + (i+1日目の朝もらえるお金)となる。
もし、この時に買うことができるならば、j日目まではコンピュータを買わずに済むため、購入後の所持金は

dp[i] + (i+1~j日目の朝もらえるお金) - (j日目のコンピュータの金額)

となる。
高速化のために累積和を使って朝もらえる金額をうまく変換しておこう。

dp[i] + (~j日目の朝もらえるお金) - (~i日目の朝もらえるお金) - (j日目のコンピュータの金額)

これがdp[j]の候補となる。
ここまで理解できていると嬉しいが、これを貰うDPで実装したものが
提出 #24476595 - 第七回 アルゴリズム実技検定
になる。dpだけ1-indexedで、それ以外が0-indexedでなんのことか分からないかもしれないが、参考程度に見てみてほしい。
まずはここまでくればO(N2)が達成できる。
ここまでわかってくればいい所まで来ている。

DP高速化

今回高速化したい部分というのは、

  • j日目のコンピュータの金額 ≦ dp[i] + (i+1日目の朝もらえるお金) という条件をiが満たす中で
  • dp[i] + (~j日目の朝もらえるお金) - (~i日目の朝もらえるお金) - (j日目のコンピュータの金額)の最大値

2番目の部分では貰うDPだとjについては固定なので、dp[i] - (~i日目の朝もらえるお金)の最大値が欲しいということになる。

これにはいくつか解決法がある。
自分はpriority_queue, multisetで実装をしたが、色々やり方がありそうではある。

priority_queue, multiset

自分の実装では以下のような関数を用意して実装した。

  • add(i):dp[i]についてデータ構造に追加
  • cut(limit):満たすべき条件を考慮して、現在のデータ構造から候補を削る
  • getOpt(): 条件を満たす中でのdp[i] - (~i日目の朝もらえるお金)の最大値

今回この手法が使えるのは、「j日目のコンピュータの金額」が狭義単調増加しているからである。
priority_queueを使って条件に使用されるdp[i] + (i+1日目の朝もらえるお金)を保持しておき、日付が増えるにつれて、
「j日目のコンピュータの金額」が増えていくので、priority_queueの先頭(最小)を見ながら条件を満たさないものを
あぶりだして候補から消していく。
候補についてはmultisetで別途管理して、priority_queueから除外されたらmultisetからも消すようにする。
multisetでは最大値を持ってきたいdp[i] + (i+1日目の朝もらえるお金)を入れておき、消せるし、最大値も取れるしという
状況にしておく。

int N; ll A[201010]; int B[201010];
ll dp[201010];
ll post = 0;
ll tot[201010];
//---------------------------------------------------------------------------------------------------
void pre() {
    int NN = 1;
    int ma = B[0]; ll tot = 0;
    rep(i, 1, N) {
        tot += A[i];
        if (ma < B[i]) {
            A[NN] = tot;
            B[NN] = B[i];
            NN++;

            ma = B[i];
            tot = 0;
        }
    }
    post = tot;
    N = NN;
}
//---------------------------------------------------------------------------------------------------
template<typename T> using min_priority_queue = priority_queue<T, vector<T>, greater<T>>;
min_priority_queue<pair<ll, ll>> contains;
multiset<ll> candicates;
void add(int idx) {
    contains.push({ dp[idx] + A[idx], dp[idx] + A[idx] - tot[idx] });
    candicates.insert(dp[idx] + A[idx] - tot[idx]);
}
void cut(ll limit) {
    while (!contains.empty()) {
        auto to = contains.top();

        if (to.first < limit) {
            contains.pop();
            candicates.erase(candicates.find(to.second));
        }
        else return;
    }
}
ll getOpt() {
    auto ite = candicates.rbegin();
    if (ite == candicates.rend()) return -infl;
    return *ite;
}
//---------------------------------------------------------------------------------------------------
void _main() {
    cin >> N;
    rep(i, 0, N) cin >> A[i] >> B[i];

    pre();

    tot[0] = A[0];
    rep(i, 1, N) tot[i] = tot[i - 1] + A[i];
    tot[N] = tot[N - 1] + post;

    rep(i, 0, N + 1) dp[i] = -infl;
    dp[0] = 0;
    add(0);
    rep(j, 1, N + 1) {
        cut(B[j - 1]);
        ll opt = getOpt();
        if (-infl < opt) {
            dp[j] = opt + tot[j - 1] - B[j - 1];
            add(j);
        }
    }

    ll ans = -1;
    if (-infl < dp[N]) ans = dp[N] + post;

    cout << ans << endl;
}

Monochrome Design [第七回 アルゴリズム実技検定 N]

https://atcoder.jp/contests/past202107-open/tasks/past202107_n

前提知識

解説

https://atcoder.jp/contests/past202107-open/submissions/24475768

今回の問題は最低限遅延評価セグメントツリーを理解していることが前提となる。
遅延評価セグメントツリーは自分は太古に自作したものをチューニングしながら使っているが、
AtCoder Libraryに素晴らしい実装があるので、そっちをチューニングして使うことをお勧めする。
(1から作るのは勉強になるかもだけど、ややしんどい)

どうやって問題に立ち向かうか

どこから考え始めるかが難しい。
長方形区間の塗りつぶしなので2Dimosかなとも思ったりするが、座圧しても難しい。
ここで、使える手法、平面走査を導入することにする。

平面走査

平面走査とはざっくり書くと、とある座標を小さい方から順番に処理していくような方針を取ることで、
今回紹介する流れで言えばy座標を小さい方から順番に評価していくような方針を取ることで、
それ以前の状態を抽象化というか無視することができ、差分計算によって全体の計算が行える。
かなり方針がざっくりとしすぎていて、何がいいのかというのが分かりにくいかと思う。
なるべく細かく説明してみるが、平面走査の記事を読んでみるのも理解を助けるだろう。

改めて書くと、今回は区間の処理をする際にy座標を小さい方から順番に処理していく方針を取る。

操作を見直す

平面走査を簡単にするために操作を少し見直してみよう。
平面走査をする際にy座標を小さい方からと書いたが、各長方形にはy座標の始点と終点があるので、
どっちを使って大小を取るかというのは少し面倒なので、ちょっと別の考え方をする。

y座標[B[i], D[i]]について反転させるという操作をy=B[i]以降を反転する、y=D[i]以降を反転する
という2操作に分割することにする。
このように分割しても最終的には同じ反転方式となるので、操作の回数が2倍に増えるが、始点と終点で
処理を分ける必要が無く、単純化して操作を見ることができる。

平面走査に戻ろう

y座標を小さい方から処理を行っていくときに、「x座標について反転しているかの配列」を持っておくことにする。
すると、y=prevの状態で作った「x座標について反転しているかの配列」の状態というのは、その次のy=currentまで
その状態が継続していることになるので、「x座標について反転しているかの配列」の反転している区間の総和が
分かっていれば、その総和×前のy座標との差を使うことで黒色である面積が計算できることになる。

上で説明した部分が平面操作で行うときの一番本質的な部分であり、少し細かく説明すると、以下のように図解できる。

y=4 ■■■□□■■■  

例えばy=4でこの状態で、次に状態が変化するy座標が6であれば

y=4 ■■■□□■■■  
y=5 ■■■□□■■■  

のように同じ状態になっているはずなので、反転している区間の総和が分かっていれば、
それに前のy座標との差をかければ黒の面積が求められる。
で、そのあと、そのy座標での反転操作を実施して、例えば以下のようになって

y=4 ■■■□□■■■  
y=5 ■■■□□■■■  
y=6 □□■□□■■□  

次にy=9に操作があるならば、それまでは同じ状態だから、

y=4 ■■■□□■■■  
y=5 ■■■□□■■■  
y=6 □□■□□■■□  
y=7 □□■□□■■□  
y=8 □□■□□■■□  

となって同様に区間の総和×前のy座標との差で面積計算ができるような感じ。
自分の実装では、getall関数で塗られている区間の総和を取得して、rev関数で区間を反転させている。
ここまで理解できてくれば、やっと折り返し。

残った問題は遅延評価セグメントツリーで解決

残った問題はgetall関数とrev関数の実装である

  • getall関数:塗られている区間の総和を計算
  • rev関数:とある区間の塗りを反転させる

これは遅延評価セグメントツリーと座標圧縮で実現ができる。
座標圧縮はしないとセグ木に載らないので、ここまでついてこれてる人なら、必要なのは理解できていると思う。
遅延評価セグメントツリーでは、以下のようなルールで更新していけばいい。

  • 区間データ dat[k] := その区間で塗られている区間の総和
  • 更新関数 comp(a,b) := a+b 普通に区間マージは足せばいい
  • 遅延評価データ lazy[k] := 反転するかどうか
  • 遅延評価更新関数 setLazy(k,x) := lazy[k] ^= x これはxorで入れ込んでいるので反転させるような実装になる

ここまではよくって、問題が遅延評価データを使って、区間データを更新する部分である。
これにはdat[k] = (dic[r] - dic[l]) - dat[k]とすればいい。
dicは座標圧縮の元の値を保持する配列である。
反転時はその区間の長さに対して塗られていない部分の長さに変換されるので、式に書くとこのような感じになる。

実装…

今回は割と重い実装が2つ重なる問題となる。
どちらも理解していれば、それほど難しくないが、かっちり合わせるのは難しいだろうと思う。
(座圧もあるし…)
頑張ってとしか言えないんですけどね…

vector<int> dic;
template<class V, int NV> struct LazySegTree { // [L,R)
    vector<V> dat, lazy; LazySegTree() { dat.resize(NV * 2, def); lazy.resize(NV * 2, ldef); }
    void update(int a, int b, V v, int k, int l, int r) {
        push(k, l, r); if (r <= a || b <= l) return;
        if (a <= l && r <= b) { setLazy(k, v); push(k, l, r); }
        else {
            update(a, b, v, k * 2, l, (l + r) / 2); update(a, b, v, k * 2 + 1, (l + r) / 2, r);
            dat[k] = comp(dat[k * 2], dat[k * 2 + 1]);
        }
    }
    V get(int a, int b, int k, int l, int r) {
        push(k, l, r); if (r <= a || b <= l) return def;
        if (a <= l && r <= b) return dat[k]; auto x = get(a, b, k * 2, l, (l + r) / 2);
        auto y = get(a, b, k * 2 + 1, (l + r) / 2, r); return comp(x, y);
    }
    void update(int a, int b, V v) { update(a, b, v, 1, 0, NV); }
    V get(int a, int b) { return get(a, b, 1, 0, NV); }
    // ---- Template ---------------------------------------------------------------------------------
    const V def = 0, ldef = 0;
    V comp(V l, V r) { return l + r; }
    void setLazy(int i, V v) { lazy[i] ^= v; }
    void push(int k, int l, int r) {
        if (lazy[k] != ldef) {
            // modify------------------------------
            dat[k] = (dic[r] - dic[l]) - dat[k];
            // ------------------------------------
            if (r - l > 1) { setLazy(k * 2, lazy[k]); setLazy(k * 2 + 1, lazy[k]); }
            lazy[k] = ldef;
        }
    }
};








int Q, A[101010], B[101010], C[101010], D[101010];
LazySegTree<ll, 1 << 18> st;
//---------------------------------------------------------------------------------------------------
ll getall() {
    return st.get(0, 1<<18);
}
//---------------------------------------------------------------------------------------------------
void rev(int L, int R) {
    st.update(L, R, 1);
}
//---------------------------------------------------------------------------------------------------
void _main() {
    cin >> Q;
    rep(i, 0, Q) cin >> A[i] >> B[i] >> C[i] >> D[i];

    rep(i, 0, Q) dic.push_back(A[i]), dic.push_back(C[i]);
    sort(all(dic));
    dic.erase(unique(all(dic)), dic.end());
    rep(i, 0, Q) {
        A[i] = lower_bound(all(dic), A[i]) - dic.begin();
        C[i] = lower_bound(all(dic), C[i]) - dic.begin();
    }

    map<int, vector<pair<int, int>>> queries;
    rep(i, 0, Q) {
        queries[B[i]].push_back({ A[i], C[i] });
        queries[D[i]].push_back({ A[i], C[i] });
    }

    ll prev = -inf;
    ll ans = 0;
    fore(q, queries) {
        ll y = q.first;

        ans += (y - prev) * getall();
        fore(range, q.second) rev(range.first, range.second);
        prev = y;
    }

    cout << ans << endl;
}

Divide [第七回 アルゴリズム実技検定 M]

https://atcoder.jp/contests/past202107-open/tasks/past202107_m

前提知識

解説

https://atcoder.jp/contests/past202107-open/submissions/24472779

今回の問題は最小費用流が分かっていないと解けないので、どこかで学習してきてほしい。
最小費用流は分かっている前提で以降は進める。

どうやってひらめくか

フロー問題はこれはフローだと巧妙に隠してある場合が多いので、フローかなとまず発想を飛ばせるかが問題となる。
自分は大体不可能問題に当たったらフローだったみたいなパターンが多い気がする。
今回の問題でかなりややこしいのは、分解された部分列が連続しなくてもいいという部分であり、これはかなりややこしい。
DPも無理だし、貪欲も思いつかないし…フローかなとなる

フロー構築

頂点として以下の4種類を用意する

  • 始点st
  • 終点gl
  • 出頂点 x1, x2, ..., xN
  • 入頂点 y1, y2, ..., yN

ここから頂点を貼っていく。
まずはst -> glに流量N、コストCの辺を貼る。
これで流すと全部これに流れるので、すべての部分列に分解したと考えることになる。
この状態をベースに頂点と辺を増やしていこう。

すべてバラバラの状態から部分列として結合させていくようなイメージで考えていく。
例えば、A[2]とA[4]をくっつけて部分列とすることにすると、Cが1つ減ってabs(A[4]-A[2])が増えることになる。
これを流量を1つだけ別の所に流すような感じにする。
つまり、st -> x2 -> y4 -> glのように流れるように頂点を使って辺を貼ろう。
出頂点と入頂点を分けているのは、今回くっつけたときの次の要素というのはちょうど1つであり、
くっつけたときの前の要素というのもちょうど1つであるため、これをst -> x2で流量1、y4 -> glで流量1のようにして限定するためである。
ちょうどコストがかかりそうな所 x2 -> y4 について流量1、コストabs(A[4] - A[2])の辺とすればいい。
st -> x2, y4 -> glについてはコストは0にしておく。
これでくっつけた場合はCが減って、こっちの連結サイドに流れていくので、どっちが最適かなというのを最小費用流のアルゴリズムに選択してもらえばいい。

フロー構築まとめ

頂点

  • 始点st
  • 終点gl
  • 出頂点 x1, x2, ..., xN
  • 入頂点 y1, y2, ..., yN

辺 (流量,コスト)

  • st -> gl : (N,C)
  • st -> x? : (1,0)
  • x? -> y@ : (1,abs(A[@] - A[?])) ここで?<@となるように注意する
  • y? -> gl : (1,0)

こういったグラフを作って、流量Nを流した時の最小費用が答えになる。

int N, C, A[202];
//---------------------------------------------------------------------------------------------------
void _main() {
    cin >> N >> C;
    rep(i, 0, N) cin >> A[i];

    atcoder::mcf_graph<int, ll> mcf(N * 2 + 2);
    int st = N * 2;
    int gl = N * 2 + 1;

    rep(i, 0, N) mcf.add_edge(st, i, 1, 0);
    rep(i, 0, N) rep(j, i + 1, N) mcf.add_edge(i, j + N, 1, abs(A[j] - A[i]));
    rep(i, 0, N) mcf.add_edge(i + N, gl, 1, 0);
    mcf.add_edge(st, gl, N, C);

    int flow;
    ll cost;
    tie(flow, cost) = mcf.flow(st, gl, N);

    cout << cost << endl;
}

Multiple Min Query [第七回 アルゴリズム実技検定 L]

https://atcoder.jp/contests/past202107-open/tasks/past202107_l

前提知識

解説

https://atcoder.jp/contests/past202107-open/submissions/24471772

解法を思いつくのも難しいが、ならし計算量(償却計算量)も意識する必要があり、そこも難しい。
セグメントツリーの知識が要求される。もし知らない場合はどこかで学習してくるか、AtCoder Libraryを活用するのもいいだろう。

何から考え始めるか

まず問題をパッと見て、単一要素更新と、区間最小値なのでセグメントツリーっぽさがある。
区間の中の最小値そのものではなく、最小値を持つ添え字を答えるというのが特徴となるが、
まずはセグメントツリーベースで考えていこう。

全て列挙するとあるが、1つ列挙することはできないだろうか。
これはセグメントツリーのノードを工夫することで実現ができる。
通常は要素のみを入れるが、{要素,添え字}というpairで入れることにする。
つまり{A[i],i}を入れるということになるのだが、これを入れてそのままmin関数で最小値を持ってきたとする。
こうすると、pairのmin比較では、firstが小さい方が採用され、firstが同じであればsecondの小さい方が採用される。
つまり、要素が最も小さく、かつ、その中でも添え字が最も小さいものが選ばれる。
こうすることで、セグメントツリーから得られる情報は要素が最も小さく、区間の中で最も左にある要素が得られることになる。

ここまで理解できていれば、実はこれ以降はそれほど難しくなくて、区間を小さくしながら要素を愚直に持ってくるだけでいい。

クエリ1

クエリ1は単純にセグメントツリーの更新処理を走らせればいい。
{Y, X}でX番目を更新する。

クエリ2

問題はこっち。
最初に区間全体でセグメントツリーから取ってきて、最小値をメモっておこう。
ここから区間の左端を狭めながら、最小値となる添え字を全列挙していく。

最初は[X,Y]の区間でセグメントツリーから持ってきて、{min, a}が得られたとする。
これは[X,Y]の区間の最左の要素となるので、次に見る区間はそれ以降でよいということになる。
よって、区間を[a+1,Y]のように更新して再度セグメントツリーから持ってくる。
同じ最小値のものが持ってこれたら再度答えとしてメモって、区間を狭くする。

これを繰り返していけば、要素が全列挙できることは分かるだろう。

間に合うのか?

とても素直な回答で、間に合うのか?という疑問が出てくるかもしれない。
今回は制約の「列挙すべき個数は2×105を超えない」というのが効いてくる。
この探索作業は必ず「列挙すべき個数+1」回の探索を行う(1回は失敗分)。
これをすべてのクエリについて足し合わせると、「列挙すべき個数の総和+Q」回となり、
多くても4×105回となるため、全体で考えると回数的には問題ないので間に合う。

このように計算回数にばらつきはあるのだけれど、全体で見るとある一定の回数に収まるというのを
ならし計算量、償却計算量で考えると表現する。
難しい考え方ではあるが、イメージをつかめば使いこなせるだろう。

int N, Q, A[201010];
SegTree<1<<18> st;
//---------------------------------------------------------------------------------------------------
void _main() {
    cin >> N >> Q;
    rep(i, 0, N) cin >> A[i];
    rep(i, 0, N) st.update(i, { A[i], i });

    rep(_, 0, Q) {
        int T, X, Y; cin >> T >> X >> Y;
        if (T == 1) {
            X--;
            st.update(X, { Y, X });
        }
        else {
            X--;
            int mi = st.get(X, Y).first;

            vector<int> ans;
            while (X < Y) {
                auto p = st.get(X, Y);
                if (p.first != mi) break;

                ans.push_back(p.second);
                X = p.second + 1;
            }
            
            int M = ans.size();
            printf("%d", M);
            rep(i, 0, M) printf(" %d", ans[i] + 1);
            printf("\n");
        }
    }
}

Flying Trip [第七回 アルゴリズム実技検定 K]

https://atcoder.jp/contests/past202107-open/tasks/past202107_k

前提知識

解説

今回の問題は無向グラフが与えられて頂点1から頂点Nへの最短距離で、かつ、満足度が最高のものを選択することが目的。
特に前半の「無向グラフが与えられて頂点1から頂点Nへの最短距離」という所でだいぶダイクストラかなという感じがする。
今回の解説はダイクストラが分かっていることを前提として話す。
もし、わかっていない場合はどこかで勉強してから以降読み進めてほしい。
ダイクストラを学んで、手になじんできた4問目くらいに取り組むといい問題じゃないかな?

今回のダイクストラは?

今回のダイクストラでは、一般的なダイクストラに距離以外の要素を追加して、そっちも最適化するという方針になる。
一般に、ダイクストラを進めるうえで、処理済みかを示すvis配列みたいなものと、現在の最適解を保持するopt配列みたいなものを用意する。
この最適解は

opt[cu] := 頂点cuに至るまでの経路での最短距離

のように定義することが多い。
今回では最短距離が最小で、かつ、満足度が最高のものを求めていきたいので、

opt[cu] := 頂点cuに至るまでの経路での{最短距離, その中での最大満足度}

という風にpairで定義することにする。
こうすることで何が変わるかというと、以前はopt[cu]'<opt[cu]みたいな単純な大小比較で済んだものが、

  • opt[cu].first'<opt[cu].firstだったら、最短経路も満足度も更新
  • opt[cu].first'=opt[cu].firstだったら、満足度だけ大きい方で更新

みたいにちょっと工夫した比較で更新していく。
でも、普通のダイクストラに比べて定義と更新部分を変えるだけでいいので、慣れればすんなりかける。

int N, M, A[101010];
vector<pair<int, int>> E[101010];
template<typename T> using min_priority_queue = priority_queue<T, vector<T>, greater<T>>;
ll vis[101010];
pair<ll, ll> opt[101010];
//---------------------------------------------------------------------------------------------------
void _main() {
    cin >> N >> M;
    rep(i, 0, N) cin >> A[i];
    rep(i, 0, M) {
        int a, b, t; cin >> a >> b >> t;
        a--; b--;
        E[a].push_back({ b, t });
        E[b].push_back({ a, t });
    }

    rep(i, 0, N) opt[i] = { infl, 0 };
    rep(i, 0, N) vis[i] = 0;

    min_priority_queue<pair<ll, int>> que;

    opt[0] = { 0, A[0] };
    que.push({ 0, 0 });

    while (!que.empty()) {
        auto q = que.top(); que.pop();

        ll cst = q.first;
        int cu = q.second;

        if (vis[cu]) continue;
        vis[cu] = 1;

        fore(p, E[cu]) {
            ll cst2 = cst + p.second;
            int to = p.first;

            if (cst2 < opt[to].first) {
                opt[to] = { cst2, opt[cu].second + A[to] };
                que.push({ cst2, to });
            }
            else if (cst2 == opt[to].first) {
                chmax(opt[to].second, opt[cu].second + A[to]);
            }
        }
    }

    cout << opt[N - 1].second << endl;
}