ひらめの日常

プログラミングと読書と

ABC161-D Lunlun Number (400)

問題はこちら

atcoder.jp

以下の条件を満たす正の整数 Xのうち、小さい方から  K 番目のものを求めよ。

  •  X を10進数で表した時、隣り合うどの二つの桁の値についても、差の絶対値が1以下。

考え方

基本的に解説放送を聞いて自分の言葉に直しただけ。

www.youtube.com

まずは桁ごとに考えてみる。すると、今までに列挙した数の後ろに、条件を満たすような数を付け加えていけば良いということに気づく。

1 -> 10, 11, 12
10 -> 100, 101
11 -> 110, 111, 112
12 -> 121, 122, 123

今まで条件を満たしていた数  x の一の位  x_1 x \% 10
よって、次に条件を満たす数は  x を10倍した数に、次に条件を満たす  x_1, x_1 + 1, x_1 - 1 をつけたものになる。

これを全列挙しても  K 個程度までに答えが得られるので、間に合う。

解答

 K 個全列挙するため、桁ごとに列挙したものの数を減らしていき、 K が列挙してある数よりも小さくなった時、値を出力する。

#include <bits/stdc++.h>

using namespace std;
using ll = long long;

int main() {
    ll k;
    cin >> k;
    vector<ll> a;
    for (ll i = 1; i <= 9; ++i) a.emplace_back(i);

    while (k > a.size()) {
        k -= a.size();
        vector<ll> old = a;
        a = vector<ll>();
        for (ll x: old) {
            for (ll i = -1; i <= 1; ++i) {
                ll d = x % 10 + i;
                if (d < 0 || 9 < d) continue;
                ll nx = x * 10 + d;
                a.emplace_back(nx);
            }
        }
    }
    cout << a[k - 1] << '\n';
    return 0;
}

Submission #11557806 - AtCoder Beginner Contest 161

ABC147-E Balanced Path (500)

問題はこちら

atcoder.jp

マス  (i,j) に二つの数  A _ {ij}, B_ {ij} が書かれている.一回の移動で  (i+1, j) または  (i, j +1) に移動する.マス  (0, 0) から  (H, W) に移動しながら,数の片方を選び  X に.もう片方を  Y に追加する.移動する経路を  p とする時,以下の値を偏りと呼ぶ.

  •  |\sum{X_p} - \sum{Y_p}|

数を自由に選びながら移動した時の,偏りの最小値を求めよ.

制約は以下の通り.

  •  2\leq H\leq 80, 2\leq W\leq 80
  •  0\leq A _ {ij}\leq 80, 0\leq B _ {ij} \leq 80

考え方

まずは式変形から.

 |\sum{X_p} - \sum{Y_p}| = |\sum{(X_p - Y_p)}|

つまり,経路を辿りながら値の差を足し合わせ,最後に絶対値をとる事と等しい.全ての経路を全列挙するのは   _ {H+W}C _ {H} 程度かかるので間に合わない.今回の場合は,制約が非常に小さいことに注意する.具体的には,答えとなりうる偏りは最大でも  80 * (80+80).

そこで,今のマス目でありうる符号付偏りの値を,毎回更新することを考え,最後に絶対値をとることにする.具体的には,以下のようなbool配列でdpをする.

  • dp[i][j][l] := マス目  (i, j) で符号付偏り  l となるかどうか

 l が負の時はどうするのか?という話があるが,それは解答のところで説明することにする.一旦無視する.)

マス目  (i, j) での符号付偏りが  lとする .マス目  (i, j) から  (i+1, j) に移動した時,そのマス目までで取りうる値は次のようになる.

  •  l + (B _ {i+1\ j} - A _ {i+1\ j})
  •  l + (A _ {i+1\ j} - B _ {i+1\ j})

よって,更新式は次の通り. l を取りうる場合は,新しい値も更新するようにする.

if dp[i][j][l] == true then
 dp[i+1][j][l + B[i+1][j] - A[i+1][j]] = true;
 dp[i+1][j][l - B[i+1][j] + A[i+1][j]] = true;

マス目  (i, j+1) に移動するときも同様に考えれば良い.

解答

実装上の注意として,経路の途中で負となりうる場合はどうするかというのがある.editorialだと毎回絶対値をとっていたが,自分の実装では配列を「最大の偏り * 2」だけのサイズを取り,全ての値に「最大の偏り」分を足すことで負のindexにアクセスしないようにした.

#include <bits/stdc++.h>

using namespace std;
using ll = long long;
#define rep(i, n) for(ll i = 0; i < (ll)(n); i++)

int main() {
    ll h, w;
    cin >> h >> w;
    int a[h][w], b[h][w];
    rep(i, h) rep(j, w) cin >> a[i][j];
    rep(i, h) rep(j, w) cin >> b[i][j];

    ll max_diff = 2 * 80 * 160;
    bool dp[h][w][max_diff];
    rep(i, h) rep(j, w) rep(l, max_diff) dp[i][j][l] = false;

    ll mid = max_diff / 2;
    dp[0][0][b[0][0] - a[0][0] + mid] = true;
    dp[0][0][-b[0][0] + a[0][0] + mid] = true;

    rep(i, h) {
        rep(j, w) {
            rep(l, max_diff) {
                if (!dp[i][j][l]) continue;
                if (i + 1 <= h - 1) {
                    dp[i + 1][j][l + b[i + 1][j] - a[i + 1][j]] = true;
                    dp[i + 1][j][l - b[i + 1][j] + a[i + 1][j]] = true;
                }
                if (j + 1 <= w - 1) {
                    dp[i][j + 1][l + b[i][j + 1] - a[i][j + 1]] = true;
                    dp[i][j + 1][l - b[i][j + 1] + a[i][j + 1]] = true;
                }
            }
        }
    }
    ll ans = 1e18;
    rep(i, max_diff) {
        if (dp[h - 1][w - 1][i]) ans = min(ans, abs(i - mid));
    }
    cout << ans << '\n';
}

Submission #8980170 - AtCoder Beginner Contest 147

参考

とてもわかりやすかった.

[AtCoder 参加感想] 2019/12/08:ABC 147 | maspyのHP

ABC146-E Rem of Sum is Num (500)

問題はこちら

atcoder.jp

長さ  N の整数列  A と正の整数  K が与えられる。 A の空でない連続する部分列であって、要素の和を  K で割った余りが要素の数と等しくなるものの数を求めよ。

以下は0-indexで話を進める。

考え方

要素の和の余りに関する問題なので、とりあえず累積和を mod K で取り、式に起こしてみる。mod K における、index i までの累積和を  d_ {i  + 1} とすると、以下のようになる。

 r := j + 1, l := i とすると、以下のように問題を言い換えることができる。
「mod K において、 0 \leq l \lt r \leq N となる  l, r に対し、  d_r - d_l = r - l となるものの個数を求めよ。」

しかし、  r, l を全探索すると計算量が  O(n ^ 2 ) になり間に合わない。そこで、片方の端点  r を固定して、その条件を満たす  l の個数を数えることを考える。

ここでポイントは、 以下の二つ。

  • 要素の数が  K 以上の時は、要素の和が必ず  K 以上になり、題意を満たすことはない。つまり、 r - l \lt K である。
  •  r - l \lt K の時、mod K において以下の式変形が成り立つ d_r - d_l = r - l \Leftrightarrow d_r - r = d_l - l

なので、今までに見た index における  d _ {index} - {index} の値の個数をmapなどで管理すれば、map[d[r] - r] で条件を満たす  l の個数を数えられる。

 K \leq r - l の時には、要素の数が  K 以上になるので、queueに  d _ {index} - {index} の値を入れておき、queueのサイズが  K 以上になったら、map[queue.front()]--; queue.pop()して要素を取り除いてあげる。

解答

#include <bits/stdc++.h>

using namespace std;
using ll = long long;

#define rep(i, n) for(ll i = 0; i < (ll)(n); i++)

int main() {
    ll n, k;
    cin >> n >> k;
    vector<ll> a(n), d(n + 1);
    
    rep(i, n) cin >> a[i];
    rep(i, n) {
        d[i + 1] = d[i] + a[i];
        d[i + 1] %= k;
    }
    map<ll, ll> mp;
    ll ans = 0;
    queue<ll> que;

    rep(r, n + 1) {
        ll t = (d[r] - r) % k;
        if (t < 0) t += k;
        
        ans += mp[t];
        mp[t]++;
        
        que.push(t);
        if (que.size() >= k) {
            mp[que.front()]--;
            que.pop();
        }
    }
    cout << ans << '\n';
    return 0;
}

Submission #8703311 - AtCoder Beginner Contest 146

参考

とても分かり易かったです。

Rem of Sum is Num [AtCoder Beginner Contest 146 E] - はまやんはまやんはまやん

第二回日本最強プログラマー学生選手権-予選- D Shortest Path on a Line (600)

問題はこちら

atcoder.jp

 N個の点がある。その点に対して、以下のように M回の操作を行い、辺を追加する。

  •  L_i \le s \lt t \le R_i となる頂点 sと頂点 t の間にコスト C_iの辺を追加する。

最終的な頂点 1から Nまでの最短距離を求めよ。

以降は0-indexとして話を進める。

解法1 - seg木でdp

 L_i , R_i が与えられた時に、 R_i までの最小コストは、「 R_i」と「 L_i, L _ i +1, ..., R _ i -1に到達する最小コスト +  C_i」の小さい方 である。

なので、与えられた辺のクエリを、 L_i で昇順にして辺を張りながら上記を実装すれば正しい答えは得られそう。

しかし愚直に計算すると、一つのクエリに対して全ての頂点の組み合わせの最小コストを見なければならないので、  O(NM) となり間に合わない。

ここでのボトルネックは、「 L_i, L _ i +1, ..., R _ i -1に到達する最小コスト」を計算するところで、ここを毎回線形探索すると間に合わない。そこで、seg木を使うことで高速に区間の最小値を求め、それを用いて  R_iまでの最小コストを更新すれば、 O(Mlog(N)) となり間に合う。(なお、区間クエリ、点更新なので遅延セグ木である必要はない。)

  • dp[i] := 頂点iに到達するための最小コスト
  • segtree := 区間ごとの最小コストを管理する
  • dp[R_i] = min(dp[R_i], segtree.query(L_i, R_i) + c (頂点rに到達できる最小コストは、区間[l, r]に到達する最小コスト + c)
  • segtree[R_i] = dp[R_i] (新しい最小値でseg木自体を更新)

解答

Submission #8393394 - NIKKEI Programming Contest 2019-2

以下はその抜粋部分。

struct edge {
    ll from, to, cost;

    edge(ll from, ll to, ll cost) : from(from), to(to), cost(cost) {};
};

typedef vector<edge> ve;
void solve() {
    ll n, m;
    cin >> n >> m;

    auto fm = [](ll a, ll b) { return min(a, b); };
    SegmentTree<ll, ll> tree(n + 1, fm, ll_inf);

    ve es;
    rep(i, m) {
        ll l, r, c;
        cin >> l >> r >> c;
        l--, r--;
        es.eb(edge(l, r, c));
    }
    sort(all(es), [](edge &a, edge &b) {
        if (a.from == b.from) return a.to < b.to;
        return a.from < b.from;
    });

    vl dp(n, ll_inf);
    tree.update(0, 0);
    dp[0] = 0;
    rep(i, m) {
        ll l = es[i].from, r = es[i].to, c = es[i].cost;
        ll t = tree.query(l, r);
        dp[r] = min(dp[r], t + c);
        tree.update(r, dp[r]);
    }
    ll ans = dp[n - 1];
    if (ans == ll_inf) {
        cout << -1 << '\n';
        return;
    }
    cout << ans << '\n';
}

解法2 - 工夫してダイクストラ

これがeditorialの解法。 今回の問題における辺の張り方の本質は、 L_i から  R_i まで、 全ての  s \lt t となるような頂点の組 (s, t) の距離が等しい という点。なので、 L_i から  R_i に辺を張り、その間の点は全てどちらかと同じ点のように扱えると楽である。(ここまでは考えたけどどうやって実現するのかわからなかった。)

そこで、まず全ての頂点  (i, i-1) にコスト0の有向辺を張ってあるグラフを考える。このグラフに対して L_i から  R_i に有向辺を張ると、コスト C_i で、その間にある全ての頂点に移動可能になる。コスト0の辺を貼ることによって最短距離が変わることはないので、答えはこのグラフに対してダイクストラを行えば求まる。

計算量は  O ( ( N + M ) log(N) ) で間に合う。

解答

Submission #8392845 - NIKKEI Programming Contest 2019-2

以下はその抜粋部分。

void solve() {
    ll n, m;
    cin >> n >> m;
    Graph g(n);
    rep(i, n - 1) g.add(i + 1, i, 0);
    rep(i, m) {
        ll l, r, c;
        cin >> l >> r >> c;
        g.add(--l, --r, c);
    }
    ll ans = g.dijkstra(0).back();
    cout << (ans == ll_inf ? -1 : ans) << '\n';
}

関連

ABC142-E Get Everything (500)

問題はこちら

atcoder.jp

 1...N までの箱がある。 i 個目の鍵のコストは  a_i であり、 b_i 種類の箱を開けることができる。全ての箱を開けるために必要な費用の最小値を答えよ。不可能な場合は  -1 を出力せよ。

考え方

まず、これは割と複雑な遷移をすることが分かる。一つの鍵を使うとどうなるか?というと、前の状態から、 b_i この箱が空いた状態に遷移する。

この図は解説放送より引用

f:id:thescript1210:20190929134425p:plain:w500

さらに今回は  1 \leq N \leq 12 なので、各々の鍵を使ったか使ってないかの  2 ^ N 通りの状態を管理することが可能。

次に、状態をどうやって管理するか?という問題になる。ここではbit列を使って管理すると良い。(bit全探索とかやってる時も基本的には同じような考え方で使っている。)

  •  c _  {ij} を開けることができる ->  c _ {ij} bit目のフラグを立てることができる。
  •  i が開けることのできる箱の集合 -> 全ての  c_i の和集合。
  •  i が空いている状態 ->  i bit目のフラグが立っている。

よって、DPで解くことを考える。

  •  dp[s] : 集合 s の宝箱を開ける最小コスト
  • 遷移元 : 全ての集合
  • 遷移先 : s と 鍵が開けられる集合 の和集合

これは、計算量  O(M \times 2 ^ N ) で間に合う。

解答

#include <bits/stdc++.h>

using namespace std;

using ll = long long;
const ll ll_inf = ll(1e9) * ll(1e9);

#define rep(i, n) for(ll i = 0; i < (ll)(n); i++)

int main() {

    ll n, m;
    cin >> n >> m;
    vector<pair<ll, ll>> key;
    rep(i, m) {
        ll a, b;
        cin >> a >> b;
        ll s = 0;
        rep(j, b) {
            ll c;
            cin >> c;
            c--;
            s |= 1 << c;
        }
        key.emplace_back(s, a);
    }
    ll pow2 = 1 << n;
    vector<ll> dp(pow2, ll_inf); // dp[i]: 集合iの宝箱を開ける最小コスト
    dp[0] = 0;

    rep(s, pow2) {
        rep(i, m) {
            ll t = s | key[i].first; // 遷移先
            ll cost = dp[s] + key[i].second;
            dp[t] = min(dp[t], cost);
        }
    }
    ll ans = dp.back();
    if (ans == ll_inf) ans = -1;
    cout << ans << '\n';
    return 0;
}

Submission #7781420 - AtCoder Beginner Contest 142

別解

こちらを参考にさせていただきました。

Submission #7758800 - AtCoder Beginner Contest 142

空集合から、 2 ^ {N-1} の状態へと遷移するグラフを考えてみると、以下のように言い換えることができる。

  • 頂点は、 0...2 ^ {N-1} まである。
  •  i\ (1...m)は、
    • 今の状態を  s とすると、s と 鍵iが開けられる集合 の和集合 へと遷移する。
    • そのコストは  a[i] である。
  • このようなグラフで、頂点 0 から  2^{N-1} へと遷移する最短路を求めよ。

こうなると、ダイクストラ法などを使って解くことができる。

ポイントとして、辺の from, to が明示的に与えられるわけではないので、自分で全ての集合からどの集合へ遷移するかを管理し直さなくてはいけない。

計算量は、頂点数  2 ^ {N} 、辺の数  M \times 2 ^ {N} より、 O(M \times 2 ^ {N} \times log(2 ^ {N})) で間に合う。

#include <bits/stdc++.h>

using namespace std;

using ll = long long;
using vl = vector<ll>;
using P = pair<ll, ll>;
const ll ll_inf = ll(1e9) * ll(1e9);

#define rep(i, n) for(ll i = 0; i < (ll)(n); i++)

struct edge {
    ll from, to, cost;

    edge(ll from, ll to, ll cost) : from(from), to(to), cost(cost) {};
};

class DAG {
private:
    ll v;
    vector<vector<edge>> table;
    vl d;
public:
    // v: 頂点数
    explicit DAG(ll v) : v(v) {
        table.resize(v);
        d.resize(v, ll_inf);
    }

    void add(ll from, ll to, ll cost = 1) {
        edge e1(from, to, cost);
        table[from].emplace_back(e1);
    }

    // O(e * logv)
    vl dijkstra(ll s) {
        // pairを使っているのは、比較関数を利用するため
        priority_queue<P, vector<P>, greater<>> que;
        d[s] = 0;
        que.push(P(0, s));

        while (!que.empty()) {
            P p = que.top();
            que.pop();
            ll min_v = p.second;
            if (d[min_v] < p.first) continue;
            for (const auto &ele: table[min_v]) {
                if (d[ele.to] > d[min_v] + ele.cost) {
                    d[ele.to] = d[min_v] + ele.cost;
                    que.push(P(d[ele.to], ele.to));
                }
            }
        }
        return move(d);
    }
};

int main() {
    ll n, m;
    cin >> n >> m;
    DAG dag(1 << n);

    rep(i, m) {
        ll a, b;
        cin >> a >> b;
        ll s = 0;
        rep(j, b) {
            ll c;
            cin >> c;
            c--;
            s |= 1 << c;
        }

        rep(j, 1 << n) {
            dag.add(j, j | s, a);
        }
    }
    vl ans = dag.dijkstra(0);
    if (ans.back() == ll_inf) cout << -1 << '\n';
    else cout << ans.back() << '\n';

    return 0;
}

Submission #7781587 - AtCoder Beginner Contest 142

【感想】勝ち続ける意志力 世界一プロ・ゲーマーの「仕事術」

はじめに

勝ち続ける意志力 (小学館101新書)

勝ち続ける意志力 (小学館101新書)

この本は、世界一賞金を稼いだことでギネスブックにも載ったり、奇跡の大逆転劇として有名な戦いを演じた、プロゲーマー梅原さんの著書である。主に彼のゲームへの向き合い方やその半生について描かれている。

www.youtube.com

印象に残ったところメモ

どうやって勝ち続けるか?

一貫して、「いかにして勝ち続けるか?」に焦点を当てている。一回まぐれで勝つということは割といろんな人にできることだが、継続して勝ち続け、トップでいるためには行き当たりばったりの戦法などではだめだという考えだ。

勝ち続けるためには、勝って天狗にならず、負けてなお卑屈にならないという絶妙な精神状態を保つことで、バランスを崩さず真摯にゲームと向き合い続ける必要がある。

そしてトップにいるからこそ、かつての自分に打ち勝ち、新しい方法を模索し続けることが重要だとしている。

かつて生み出した戦術に頼らない覚悟と、新たな戦術を探し続ける忍耐があるからトップにいられるのだ。

人の目を気にしないこと

自分の人生にそれほど影響のない人の気持ちを気にかけていたら、自分らしい振る舞いなどできるはずもなく、本来やるべき行動を継続できない。

梅原さんは別の視点から、努力を継続している人こそ周りの目なんて気にしないんだというスタンスを取っている。確かに人の目を気にせず、人の評価を気にせずに自分を高めることができるのは素晴らしく楽しい。

これまでの経験から、諦めなければ結果が出るとは言い切れない。だが、諦めずに続けていれば人の目が気にならなくなる日が来るのは確かだ。そして、人の目が気にならない世界で生きることは本当に楽しい、と確信を持って断言できる。努力を続けていれば、いつか必ず人の目は気にならなくなる。

目的と目標は違うという話

大会で勝つこと自体を目的にするのではなく、これはあくまで目標である。結果だけを求めた結果良い成績に繋がったことなはいと述べている。そして、最後に自分がゲームを続ける目的としては、勝利よりも自身の成長として捉えることで、平常心を失わずモチベーションも維持している。

勝つことより成長し続けることを目的と考えるようになった。ゲームを通して自分が成長し、ひいては人生を充実させる。いまは、そのために頑張っているんだ、

自身の成長を目的としているから、勝利して結果を出したから休むということはないし、逆に1日に頑張りすぎるということもない。日々継続することで少しづつの積み重ねから自分の成長を生み出す。評価基準が他者依存ではないために、モチベーションも持続している。

大切なのは時間を費やすことではなく、短くてもいいからそれを継続し、そのなかに変化や成長を見出すことだ。

感想

小学校の頃から、好きなことをやっていない周りのクラスメートに疑問を感じ、それでいてなおゲームばかりをしている自分に対しても「このままでいいのか?」という疑問を投げかけ続けるというのはすごい早熟だなと思った。自分が小学生の頃にそんなこと何も考えてなかったな... ただ、そのような常に現状を疑う力を持っているからこそ(そしてその悩みと戦い続けてこそ)、若くして世界一のプレーヤーになれたという面もあるのかなと思う。

一貫して主張しているのは、「続ける大事さ」。羽生さんも「決断力」で述べていたが、日々継続した努力をできる人間が最後には勝つということを主張している。小さくても、毎日の努力を無理せずに続ける。そして自分の成長を幸せに感じる。そんな人間に少しでも近づきたいと思った。

ABC140-E Second Sum (500)

問題はこちら

atcoder.jp

長さ  N の順列  P が与えられた時、区間  L, R に対して以下を計算せよ。

  • 全ての重複しない区間において、二番目に大きい数の和。

考え方

簡単バージョンとしてこの問題があるので見ると良い。

atcoder.jp

step1 - 問題の言い換え

愚直にやると、全ての区間を列挙して、その区間の二番目の要素を足していくことになるが、これは[tex: N3] のオーダーとなり到底間に合わない。そこで、まずはそれぞれの要素が何回足されることになるかを考えてみる。(区間系の問題では、それぞれの要素が何回操作されるかを考えてみると良いことが多い気がする。)

f:id:thescript1210:20190910221248j:plain:w600

 X_i が足される回数は、以下のような場合である。

  •  X_i の右側に  X_i よりも大きいものが一つあり、左側には  X_i よりも小さいもののみある。
  • 上の逆。

よって、上の図のように r1, r2, l1, l2 を定めると、一つの  X_i が答えに寄与する回数は  ( ( i - l1 ) + ( r2 -r1 ) ) \times ( ( r1 - i ) + ( l1 - l2 ) )

step2 - 実装方法

問題は、これをどのようにしてTLEしないように求めるかである。愚直にそれぞれの要素を見て、自分よりも大きい要素を探しに行くと  N ^ 2 かかるので間に合わない。

どうにかしてlower_bound()などを使って、高速に自分より大きい要素を探したいが、このままだとindexの情報を保ったまま探索をすることができない。

ここでは  X の要素を大きい順に見ていき、すでに見た要素のindexsetに入れて管理する。こうすることで、今見ている要素よりも大きい要素のみのindexが入っており、lower_bound() などで高速に今見ている要素よりも大きく、かつ一番右に近いものを見つけることができる。これが見つかれば、あとは境界条件に気をつけてイテレーターを動かして二番目の要素までを得る。

また、今回の問題では、個数を数えるときに端を含まないように数えなければならない(つまり、二番目に大きい要素を含めないようにする)ので、 l -1 で初期化し、 r n で初期化することで、うまく個数を数えることができる。

解答

#include <bits/stdc++.h>

using namespace std;

using ll = long long;
using vl = vector<ll>;

#define rep(i, n) for(ll i = 0; i < (ll)(n); i++)

int main() {

    ll n;
    cin >> n;
    vl p(n);
    unordered_map<ll, ll> mp;
    set<ll> s;
    rep(i, n) {
        cin >> p[i];
        mp[p[i]] = i;
        s.insert(p[i]);
    }

    set<ll> idx;
    ll ans = 0;
    while (!s.empty()) {
        ll now = *s.rbegin();
        s.erase(now);

        ll i = mp[now];
        vl l(2, -1), r(2, n);
        {
            auto itr = idx.lower_bound(i);
            rep(j, 2) { // r
                if (itr == idx.end()) break;
                r[j] = *itr;
                itr++;
            }
        }
        {
            auto itr = idx.lower_bound(i);
            rep(j, 2) { // l
                if (itr == idx.begin()) break;
                itr--;
                l[j] = *itr;
            }
        }

        ll l1 = i - l[0], l2 = l[0] - l[1];
        ll r1 = r[0] - i, r2 = r[1] - r[0];
        ans += (l1 * r2 + l2 * r1) * now;

        idx.insert(i);
    }
    cout << ans << '\n';

    return 0;
}

Submission #7453131 - AtCoder Beginner Contest 140