Mister雑記

競プロ記事がメインになりますが、内容は気分次第です。

SoundHound 2018 Masters 本戦-B 「Neutralize」 (400)

B 「Neutralize」 (400)

なんか悔しい。

問題リンク

概要

 N個の要素からなる数列 bがある。これに以下の操作を好きなだけ行う。

  • 連続した K個を選び、それらをすべて0にする。

この操作を行った後の、数列の総和の最大値を求めよ。

制約

  •  1 \leq K \leq N \leq 2 \times 10^5
  •  - 10^9 \leq b_i \leq 10^9

解説

まず考えたのが貪欲法で、「 [i, i + K) の総和が負なら操作を適用する」を i = 1 \sim Nまで実行するというもの。 実行自体はBITを使えば計算量 O(N \log N) でできるのだが、残念ながらこれは嘘解法。 具体的には、 N = 4, K = 3 (-4, 1, 5, -9) のような場合に最初の要素を消すことができない。

ここで諦めて解説を見た。editorialはちょっとよく分からなかったが、人々のブログがとても分かりやすかった。以降その解説。


一部が既に操作済みの領域に対して操作を行えることを考えると、この操作は実質「連続した K以上の要素を選び、それら全てを0にする」とみなして問題ない。

そしてこの問題の主軸となる解法はDPである。具体的には

  •  dp_i = (b_1, \dots, b_i) の場合の最適解

という値を更新していくことを考える。なお1-indexedで便宜上 dp_0 = 0とする。

 (b_1, \dots, b_{i - 1}) b_iを追加するとき、大きく以下の2つの場合に分けられる。

  •  b_iを消さずにそのまま追加する。
  •  b_iを末尾とする、連続した K個以上の要素を消す。

それぞれの場合の総和を考えてみる。

前者は b_iを追加するだけなので dp_{i - 1} + b_i

後者は連続する K + j個の要素を消した場合の総和が dp_{i - K - j}。これを j \geq 0について全て考えるので、 max(dp_0, \dots, dp_{i - K})

あとはこれに従って dpを更新していけばいいのだが、愚直にやると後者の最大値を求めるのに計算量 O(N) かかってしまい、全体の計算量は O(N^2) となってしまう。これの対策として考えうる方針は主に2つある。

  1. BITで区間最大クエリを O(\log N) で処理する。
  2.  ma_i = max(dp_0, \dots, dp_i) なる配列を同時に更新する。

以下の実装例では、後者の方針に従っている。

実装例

#include <iostream>
using namespace std;
using ll = long long;

int main() {
    ll N, K;
    cin >> N >> K;
    ll b[N + 1];
    for (int i = 1; i <= N; ++i) {
        cin >> b[i];
    }

    ll dp[N + 1], ma[N + 1];
    dp[0] = ma[0] = 0;
    // dp[i] = 1 ~ iにおける最適解
    // ただしdp[0] = 0
    // ma[i] = max(dp[0], ... ,dp[i])

    for (int i = 1; i <= N; ++i) {
        // そのまま追加した場合
        dp[i] = dp[i - 1] + b[i];

        // b[i]を消したい場合
        if (i >= K) dp[i] = max(dp[i], ma[i - K]);

        // maの更新
        ma[i] = max(ma[i - 1], dp[i]);
    }

    cout << dp[N] << endl;
    return 0;
}

感想

  • 困ったらDP。
  • もっと粘ってれば解けたかというと、五分五分という印象。
  • 色々なDPのパターンをこなしていきたい。

AGC005-B 「Minimum Sum」 (400)

600点はあると思う。

問題リンク

概要

数列 (1, 2, \dots, N)の順列 aが与えられる。

 \displaystyle \sum_{l = 1}^{N} \sum_{r = l}^{N} min(a_l, \dots, a_r)

を求めよ。

制約

  •  1 \leq N \leq 2 \times 10^5

解説

数式が表しているのは、「 aについて考えうる全ての区間に対して、その最小値を足し合わせたもの」という意味。区間は全部で N (N + 1) / 2個あるので、毎回愚直に全要素を見ていると計算量 O(N^3)で全然間に合わない。

そこでまず考えられるのが、セグ木による高速化である。セグ木は区間最小値を O(\log N)で求められるので、計算量は O(N^2 \log N)まで落ちる。しかしこれでも間に合わない。

ここで根本的な発想の転換が必要となる。「各区間の最小値はいくつか?」ではなく代わりに「値 iはいくつの区間の最小値になるか?」が求まれば、 i \times (最小値になる区間の数)を足し合わせることで答えが求まる。

さらにこの区間数は、左右両方について「一番近くにある自分より小さい要素」の位置が分かれば以下のように求められる。

f:id:misteer:20180928082257p:plain

ただこれを求める方法が結構閃きというか知識が必要で、小さい方から値を数列に加えていく必要がある。小さい方から値を加えていくと、「既に数列に存在している値は全て今見ている値より小さい」という性質が成り立つ。よって「既に加えられたもので一番近くにある要素の位置」を求めるだけで十分になる。

これはsetにindexを突っ込んでいけば、lower_boundを使うことで O(\log N)で検索できるため全体の計算量は O(N \log N)まで落ちて十分間に合う。

f:id:misteer:20180928082318p:plain

上の図がそれを実践した例で、上段が数列、下段がindexとなっている。また、上のように両端に0があると仮定すると実装しやすい。

実装例

#include <iostream>
#include <set>
using namespace std;
using ll = long long;

int main() {
    int N;
    cin >> N;
    
    ll place[N + 1];
    // place[i]...値iのaにおけるindex
    
    for (int i = 1; i <= N; ++i) {
        ll a;
        cin >> a;
        place[a] = i;
        // 保持するのはindexなので、ここが普通と逆なことに注意
    }

    ll ans = 0;
    set<ll> used = {0, N + 1};
    // すでに見た要素のindexを保持する
    
    for (int i = 1; i <= N; ++i) {
        ll r, l;
        
        auto itr = used.lower_bound(place[i]);
        r = *itr;
        // lower_boundで右端を調べる(upper_boundでもいい)
        l = *(--itr);
        // その1個手前が左端
        
        ans += i * (place[i] - l) * (r - place[i]);
        used.insert(place[i]);
    }

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

lower_boundは調べたい値「以上」の要素、upper_boundは調べたい値「より大きい」要素を検索する。今回の場合は同値なものが存在しないのでどちらでもいいが、この辺は常に意識したい。

あとlower_bound(set.begin(), set.end())をやらないように注意。これの計算量は O(\log N)ではなく O(N)である。

感想

  • 「値を小さい方から入れていく」というのは一種の典型なのだろう
  • それでも知らなきゃ思いつくのは困難だし、400点にしては難しすぎる。

AGC005-A 「STring」 (300)

典型的な括弧マッチング。

問題リンク

概要

SとTからなる文字列 Xがある。 Xの文字数は偶数で、SとTは同じ数だけ含まれている。

これからこの文字列に対して以下の操作を 10^{10,000}回行う。

  • 最も左にあるSTという連続部分列を消す。
  • このような連続部分列が存在しなければ何もしない。

最終的に残る文字列の長さを求めよ。

制約

  •  2 \leq X \leq 2 \times 10^5

解説

まず無駄に大きい操作回数の 10^{10,000}に意味はなく、消せる文字がなくなったら終了としていい。

操作の回数は高々 |X| / 2回なので、愚直に実装すると計算量は O(|X|^2)で部分点しか取れない。

実のところこの問題、Sを(、Tを)と見なすと典型的な括弧マッチング問題になる。これは以下のようにstackを使うことで O(|X|)で残った長さを判定できる。

  1. stackを用意する。
  2. 文字列を頭から順に見ていく。
    1. 文字が(だった場合、stackにpush。
    2. 文字が)だった場合、
      • stackの末尾が(ならstackからpop。
      • そうでなければ)をstackにpush。
  3. 最終的なstackの要素数が答え。

「頭から順に見ていって、括弧がマッチングしたら即消去」という操作をしている。

なお、上の操作はstackなしでも2つの変数によって実現できる。

  1.  cnt resを0で初期化する。
  2. 文字列を頭から順に見ていく。
    1. 文字が(だった場合、 cntをインクリメント。
    2. 文字が)だった場合、
      •  cnt \gt 0なら cntをデクリメント。
      • そうでなければ resをインクリメント。
  3. 最終的な cnt + resの値が答え。

 cntがstack中の(の数、 resがstack中の)の数を表している。

実装例

#include <iostream>
using namespace std;

int main() {
    string X;
    cin >> X;

    int cnt = 0, res = 0;
    for (char c : X) {
        if (c == 'S') {
            ++cnt;
        } else {
            if (cnt == 0) {
                ++res;
            } else {
                --cnt;
            }
        }
    }

    cout << res + cnt << endl;
    return 0;
}

感想

  • 括弧のマッチングは割とよく出るので解法を覚えて損はない。

ARC101-C 「Candles」 (300)

Static Candles。

問題リンク

概要

 N本のロウソクが数直線上に並んでおり、左から i本目の座標は x_iである。

原点から移動を始めて N本中 K本のロウソクに火を付けるのに、必要な最小の移動距離を求めよ。

制約

  •  1 \leq K \leq N \leq 10^5
  •  -10^8 \leq x_1 \lt x_2 \lt \dots \lt x_N \leq 10^8

解説

まずわざわざロウソクをスルーする必要もないので、連続した K個のロウソクのみについて考えればいい。

で。具体的な移動方法を考えると、

  •  x_N \leq 0の場合
  •  x_1 \lt 0かつ 0 \gt x_Nの場合
  •  0 \leq x_1の場合

が主に考えられる。1つ目と3つ目は一番遠いロウソクへ真っ直ぐ行けばいいのだが、2番目は「より近い方の端点までいって反対側までバックする」みたいな移動方法になる。

まぁ実際にこれらを場合分けすればACなんだが、実のところこのような場合分けをしないでもいい。 というのも1つ目と3つ目も2つ目と同じ方法で多少無駄があるが最短経路は出るからだ。

実装例

#include <iostream>
using namespace std;
const int INF = 1 << 30;

int main() {
    int N, K;
    cin >> N >> K;

    int x[N];
    for (int i = 0; i < N; ++i) {
        cin >> x[i];
    }

    int ans = INF;
    for (int i = 0; i < N; ++i) {
        int j = i + K - 1;
        if (j > N - 1) break;

        // 最初にx_iとx_jの近い方に行く
        // その後x_iからx_jへ、あるいはx_jからx_iへ移動する
        ans = min(ans, min(abs(x[i]), abs(x[j])) + x[j] - x[i]);
    }

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

感想

  • Static Sushiの弱体化版だなぁという印象。
  • できるだけ楽な実装をしていきたいね。

ARC098-C 「Attention」 (300)

方向音痴なので(?)混乱しがち。

問題リンク

概要

 N人の人が東西方向に一直線に並んでおり、文字列 Sについて西から i番目の人は S_iの方角を向いている。

ここで N人のうち誰か1人をリーダーとして認める。このとき、リーダー以外の全員はリーダーのいる方角を向かせる必要がある。 このとき、向きを変える人数の最小値を求めよ。

制約

  •  2 \leq N \leq 3 \times 10^5
  •  |S| = N
  •  SはEとWからなる。

解説

「そんな適当にリーダー決めて大丈夫なのか」という問題はさておき、実際に i番目の人をリーダーにしたときに何人が振り向くか考えてみよう。

まずリーダーより西にいる人。この人たちは最終的に東を向かなくてはならないため現在西を向いている人が全員振り向くことになる。 同様にリーダーより東にいる人については、現在東を向いている人が全員振り向くことになる。

これを各 iについて愚直に数え上げていると計算量が O(N^2)で間に合わない。そこで、累積和によってこれを高速化する。

具体的には、「 c_i = 西から i人目のうち西を向いている人の数 = i文字目までにいくつEがあるか」を保持する数列 c_iを作る。すると、 i人目をリーダーにしたときに振り向く人数は

  • リーダーより西にいて西を向いている人が c_{i - 1}
  • リーダーより東にいて東を向いている人が N - i - (c_N - c_i)

より、この和となる。後者は少し複雑なので、数直線に区間を書いたりすると分かりやすいだろう。

これなら累積和を求めるのに O(N)、解を求めるのに O(N)で余裕で間に合う。

実装例

#include <iostream>
#include <string>
using namespace std;

int main() {
    int N;
    string S;
    cin >> N >> S;

    int cnt[N + 1];
    // i文字目までにWがいくつあるか(1-indexed)

    // 累積和テーブルを埋めていく
    cnt[0] = 0;
    for (int i = 0; i < N; ++i) {
        cnt[i + 1] = cnt[i];
        if (S[i] == 'W') ++cnt[i + 1];
    }

    int ans = N;
    for (int i = 1; i <= N; ++i) {
        // 自分より西にいて西を向いている人が
        //  cnt[i-1]人
        // 自分より東にいて東を向いている人が
        //  (N-i)-(cnt[N]-cnt[i])人
        ans = min(ans, cnt[i - 1] + (N - i) - (cnt[N] - cnt[i]));
    }
    cout << ans << endl;
    return 0;
}

上は解説のためにも丁寧にコメントが付いているが、本番で実装するときも変数や関数の定義を書くことは非常に大切である。というのも、定義を書いておけば実装の際にいちいち思い出さなくて済むし、使うときも定義に基づいて考えることがしやすいからだ。

感想

  • 累積和はindexで闇を見がちなので慣れよう。
  • 方向音痴なので東西より左右とか前後にしてほしかった。
    • 実装中もそこそこ脳内でバグらせていた。

ARC102-D 「All Your Paths are Different Lengths」 (700)

下手な勘違いは、やめようね!

問題リンク

概要

整数 Lについて、以下を満たす有向グラフを1つ構築せよ。

  • 頂点数は20以下、各頂点には 1 \sim Nの相異なる番号が振られている。
  • 辺数は60以下、各辺には 0 \sim 10^6の長さが付いている。
  • 辺は全て番号の小さい頂点から大きい頂点へと張られている。
  • 頂点1から頂点 Nへの異なるパスはちょうど L個あり、それらの長さは 0 \sim L - 1の相異なる整数。

制約

  •  2 \leq L \leq 10^6

解説

こういう「 0 \sim Xまでの整数を全部作れ」っていう問題は大抵「 p進法を使う」と相場が決まっている。今回の場合は p = 2が一番やりやすい。本番中に p = 3でやって沼にハマったのが私。 本記事ではもちろん p = 2で解説していく。

本問の構築過程は主に

  1. 大まかに引く
  2. バイパスで調整

の2段階に分けられる。

大まかに引く

まず頂点数は調整が面倒なので常に20個とする。そして、以下のように辺を張る。

f:id:misteer:20180920202200p:plain

これで K本の辺を張ったとき、 [0, 2^K)の任意の整数を作ることができる。

辺を張れる数は最大19本なので、 2^{19} - 1 = 524,287まで作ることができる。制約に2倍弱足りないが、それは次の過程で補える。

バイパスで調整

実際に L = 334 (ん?)で考えてみよう。

上のように8本の辺を張ることで [0, 256)までは作れる。一方で9本張ってしまうと [0, 512)まで作れてしまいパスが多すぎとなる。

ではどうやって [256, 334)を作るか?そこで256を後から加えることにして [0, 78)を作ることを考える。 これは上と同様の方法で6本の辺によって [0, 64)までなら作れる。 ということで、6本の辺の先、つまり頂点7から20に向けて長さ 256バイパスを張ることで [256, 320)のパスが新たに増える。

では次は320を引いて [0, 14)を作って......と考えることで最終的に [0, 334)のパスが全部できる。

f:id:misteer:20180920202131p:plain

ちなみに一番下にあるように、バイパスの始点は Lのbitと一致している。プロはこの性質から巧みにパスを張ったりできるんだろうか。

実装例

正直この問題で真に難しいのは考察より実装である。実装が上手い人は何を意識しているのかとても気になる。

#include <iostream>
#include <vector>
using namespace std;
using ll = long long;

struct edge {
    int from;
    int to;
    int cost;
    edge(int _from, int _to, int _cost) : from(_from), to(_to), cost(_cost){};
};

vector<edge> ans;

// [add, add + L)のバイパスを作る
void bypass(int add, int L) {
    if (L <= 0) return;
    for (int k = 19; k >= 0; --k) {
        if (L >= (1 << k)) {
            // [add, add + 2^k)を作る
            // k本の辺の後、つまり頂点k+1から20に辺を張る
            ans.push_back(edge(k + 1, 20, add));

            // [add + 2^k, add + L)を作る
            bypass(add + (1 << k), L - (1 << k));
            break;
        }
    }
    return;
}

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

    // 0の辺を全部張る
    for (int i = 1; i < 20; ++i) {
        ans.push_back(edge(i, i + 1, 0));
    }

    // 大まかにグラフを作る
    for (int k = 19; k >= 1; --k) {
        if (L >= (1 << k)) {
            // k本辺を張って[0, 2^k)を作る
            for (int i = 1; i <= k; ++i) {
                ans.push_back(edge(i, i + 1, 1 << (i - 1)));
            }

            // [2^k, L)を作る
            bypass(1 << k, L - (1 << k));
            break;
        }
    }

    cout << 20 << " " << ans.size() << endl;
    for (auto e : ans) {
        cout << e.from << " " << e.to << " " << e.cost << endl;
    }
    return 0;
}

個人的に本問で得られた実装テクが1つある。 本問の様に「 L \geq 2^iを満たす iを知りたい」というケースは珍しくないのだが、このとき「超過するまで iをインクリメントして iを1引く」とするとまずバグる。 こういうときは、上のように「上から iをデクリメントする」方が自然だしかなりバグりにくい。

感想

  • 本番の私は時間切れとはいえよく3進法で通したなぁとつくづく思う
    • ちなみに3進法のコードがこちら
  • 実装のテクも1つ学んだし、時間かけて記事用に実装しただけの成果はあったと思いたい。

ARC102-C 「Triangular Relationship」 (300)

問題リンク

概要

 N以下の整数の組 (a, b, c)で、 a + b,  b + c,  c + aが全て Kの倍数であるものの個数を求めよ。

制約

  •  1 \leq N, K \leq 2 \times 10^5

解説

 a' = a \% Kとおく。 b', c'も同様。

このとき (a + b) \% K = 0 \Leftrightarrow (a' + b') \% K = 0となる。

ここで a'の値について場合分けをする。


1.  a' = 0の場合

 (a' + b') \% K = 0より、まず a' + b' = 0とすると b' = 0となる。

一方 0 \leq b' \lt Kより a' + b' \geq Kは成立しないため、これが唯一の解となる。

同様にして c' = 0となり、これは (c' + a') \% K = 0に矛盾しないため条件を満たす。

まとめると a' = b' = c' = 0は条件を満たす。これは元に戻すと「 a, b, cが全て Kの倍数」となる。

2.  a' \gt 0の場合

 (a' + b') \% K = 0 0 \leq b' \lt Kから、 a' + b' = Kのみが成立。よって b' = K - a'となる。

同様にして c' = K - b' = a'となる。

ここで (c' + a') \% K = 2a' \% K = 0が成立する条件を考える。

まず Kが奇数の場合は 0 \lt a' \lt Kにて常に 2a' \% K \gt 0より不成立。

次に Kが偶数の場合。これは a' = K / 2のみにて 2a' \% K = 0が成立する。

まとめると、 Kが偶数の場合のみ a' = b' = c' = K / 2が条件を満たす。


以上で全パターンが網羅できた。ではパターン数を数えてみよう。

まず a' = b' = c' = 0 1 \sim Nには Kの倍数が \lceil N / K \rceil個含まれているため、 各 a, b, cについてそこから1つずつ自由に選ぶことを考えるとパターン数は {\lceil N / K \rceil}^3通り。

次に Kが偶数の場合限定で a' = b' = c' = K / 2 1 \sim Nには Kで割って K/2余る値が \lceil (N + K/2) / K \rceil個含まれているため、 先と同様に考えてそのパターン数は {\lceil (N + K/2) / K \rceil}^3通り。

ここでうっかり {\lceil N / (K / 2) \rceil}^3通りとしないように。 たとえば (a', b', c') = (0, 0, K / 2)なんかは条件を満たす組ではない。

実装例

#include <iostream>
using namespace std;
using ll = long long;

ll triple(ll a) {
    return a * a * a;
}

int main() {
    ll N, K;
    cin >> N >> K;
    ll ans = triple(N / K);
    if (K % 2 == 0) {
        ans += triple((N + K / 2) / K);
    }
    cout << ans << endl;
    return 0;
}

まぁ実装に関しては何も言うことはない。

感想

  • 冷静に考察を積みましょう。
    • 本番の私は上と全く同じ考察をして通したので(6分かかった)。
  • Twitterで「A~Cまでループ構文が要らないコンテスト」と言われていたのは面白かった。
    • それでいてDがクソ難しかっただけに、数学が得意な人にはチャンスだったと言える。