けんちょんの競プロ精進記録

競プロの精進記録や小ネタを書いていきます

JOIG 春合宿 2022 day1-1 Relay (難易度 6)

面白かった!

問題概要

 N 人の走者がいる。 N 人の中から  3 人を選んで、100m 走る × 3 の 300m リレーを行う。

 i 人目の 100m 走のタイムは  A_i 秒、バトンパスタイムは  B_i 秒で与えられる。リレーの走者として、 i, j, k 3 人を選んでこの順に走るときの総合タイムは

 A_{i} + \max(B_{i}, B_{j}) + A_{j} + \max(B_{j}, B_{k}) + A_{k}

で与えられる。この総合タイムの最小値を求めてください。

制約

  •  3 \le N \le 2 \times 10^{5}

考えたこと:走者メンバーを固定して考える

まず一目見て複雑な数式だと思った。経験上こういう時は、少しでも簡単な式に置き換えることを考えるとよい!!

その際の方針として、走者メンバーを固定したときに、 A_{i} + \max(B_{i}, B_{j}) + A_{j} + \max(B_{j}, B_{k}) + A_{k} の値が最大になるような走順を考察しよう。

一般に、最適化問題を解く際には、ある値を固定した場合の問題を先に解くことで、活路を見出せることがとても多い!!

走者メンバーを固定すると、 A_{i} + A_{j} + A_{k} の部分は一定なので、 \max(B_{i}, B_{j}) + \max(B_{j}, B_{k}) の部分だけが問題になる!!

直感的には、二度も絡んでくる真ん中の走者が、バトンパスタイム  B が最小のメンバーを選ぶとよさそうだ。そして実際にその場合が最適になる。このことを確かめてみよう。

メンバー  a, b, c を選んで、 B_{a} \le B_{b} \le B_{c} であるとしよう。

  •  i = a, j = b, k = c のとき: \max(B_{i}, B_{j}) + \max(B_{j}, B_{k}) = B_{b} + B_{c}
  •  i = a, j = c, k = b のとき: \max(B_{i}, B_{j}) + \max(B_{j}, B_{k}) = 2 B_{c}
  •  i = b, j = a, k = c のとき: \max(B_{i}, B_{j}) + \max(B_{j}, B_{k}) = B_{b} + B_{c}
  •  i = b, j = c, k = a のとき: \max(B_{i}, B_{j}) + \max(B_{j}, B_{k}) = 2 B_{c}
  •  i = c, j = a, k = b のとき: \max(B_{i}, B_{j}) + \max(B_{j}, B_{k}) = B_{b} + B_{c}
  •  i = c, j = b, k = a のとき: \max(B_{i}, B_{j}) + \max(B_{j}, B_{k}) = B_{b} + B_{c}

このうち最小のものは  B_{b} + B_{c} である。よって、 B_{a} \le B_{b} \le B_{c} であるような走者  a, b, c をメンバーにしたときには、適宜メンバーを入れ替えることにより、最終スコアは

 A_{a} + A_{b} + A_{c} + B_{b} + B_{c} = A_{a} + (A_{b} + B_{b}) + (A_{c} + B_{c})

になるものと考えて良いことがわかった。

簡単のため、 N 人の走者を、 B が小さい順に並び替えることにしよう!!!

そうして、 B_{0} \le B_{1} \le \dots \le B_{N-1} であるものと考えることにしよう。こうすることで問題が考えやすくなるのだ。

走者  a を固定して考える

 B_{0} \le B_{1} \le \dots \le B_{N-1} という前提のもとでは、 3 人の走者  a, b, c ( a \lt b \lt c) を選ぶと、最終スコアは

 A_{a} + (A_{b} + B_{b}) + (A_{c} + B_{c})

と簡単な式で表せる。これを最適にする方法を考えるにあたって、再び、ある量を固定して考えることにしよう。具体的には、走者  a を固定して考えることにする。

 a を固定すると、残りの問題は次のように考えられる。


番号が  a より大きい走者  i = a+1, a+2, \dots, N-1 のうち、 A_{i} + B_{i} が大きい順に  2 人とればよい


残りの問題の難しいところは、 a の値によって、 A_{i} + B_{i} が大きい順の  2 人が入れ替わってしまうところだ。

ひとまず、次の値を求めることにしよう。

  • vmin1[a] i = a+1, a+2, \dots, N-1 に対する  A_{i} + B_{i} の最小値
  • vmin2[a] i = a+1, a+2, \dots, N-1 に対する  A_{i} + B_{i} 2 番目に小さな値 (最小値が複数ある場合は最大値)

これらは、添字 iN-1 から 0 へと逆順に回していくような for 文によって求めることができる。そしてこれらの値が求められていれば、

A[a] + vmin1[a] + vmin2[a]

の最小値が答えになる。

計算量

  •  B を小さい順に並び替える: O(N \log N)
  • A[a] + vmin1[a] + vmin2[a] の最小値を求める: O(N)

よって全体の計算量は  O(N \log N) となる。

コード例

実装上は、vmin1[a]vmin2[a] は配列として持つのではなく、動的に求めることにした。

#include <bits/stdc++.h>
using namespace std;
const long long INF = 1LL << 55;

int main() {
    // 入力
    int N;
    cin >> N;
    vector<long long> A(N), B(N);
    for (int i = 0; i < N; ++i) cin >> A[i] >> B[i];

    // B が小さい順に添字をソートする
    vector<int> ids(N);
    for (int i = 0; i < N; ++i) ids[i] = i;
    sort(ids.begin(), ids.end(), [&](int i, int j) {
        return B[i] < B[j];
    });

    // A[a] を固定して最適化する
    long long res = INF;
    long long vmin1 = INF;
    long long vmin2 = INF;
    for (int a = N-1; a >= 0; --a) {
        // 答えを更新
        res = min(res, A[ids[a]] + vmin1 + vmin2);

        // best, second を更新する
        long long val = A[ids[a]] + B[ids[a]];
        if (val < vmin1) {
            vmin2 = vmin1;  // ベストをナンバー 2 に譲る
            vmin1 = val;  // ベストを更新する
        } else if (val < vmin2) {
            vmin2 = val;
        }
    }
    cout << res << endl;
}

AtCodeer 本を書きました!

こんばんは!!! けんちょんです!

新しく本を出させていただくことになりましたので、報告いたします。

この本は次の Qiita の記事を単行本化したものです。

qiita.com

今度はどんなコンセプトで、どんな内容で、どんなターゲット層を想定した本なのかについて、簡単に紹介します。

1. 本書のコンセプト

今回の本は、


  • AtCoder何も知らない方が入門できる!
  • AtCoder布教したい方が「とりあえずこれ読めばいいよ」と言える!
  • C++Python両言語で入門できる!

ことを目指した AtCoder の入門本です。おそらく、史上最も易しい競プロ本です。

Python で競プロしている方が C++ に乗り換えるキッカケになったり、C++ で競プロしている方が Python に乗り換えるキッカケになったりすることも狙っています。

 

位置付け 内容
1 章・2 章 AtCoder の紹介・チュートリアル
3 章 初級編 文法確認
4 章 計算量
5 章 中級編 ABC C 問題の徹底対策
6 章 上級編 アルゴリズム入門

 

 

これから、より詳しい内容を紹介していきます。

 

2. 初級編 〜 ここからスタート!

今まで競プロ本では、文法解説レベルから解説したものはほとんどありませんでした。

AtCodeer 本では文法の確認からやっていきます。文法を網羅的に解説することまではできませんが、例題を解き進めていくうちに自然に文法を習得できるように構成しました。

また、C++Python の両方で解説したこともポイントです。一方の言語で十分に競プロに習熟している方でも、他方の言語に入門する練習もできるでしょう。

例題は、AtCoder を始める方向けの問題集「AtCoder Beginners Selection」に選んだ問題たちを中心に解説しています。これによって、ABC の A 問題、B 問題を解き切る力が身につくはずです!

 

4. 中級編 〜 典型を徹底マスター!

中級編が本書の大きな特徴です。

ABC の C 問題というのは、文法確認レベルの問題よりは難しく、特定のアルゴリズムが必要になるほど専門的な知識は不要な問題たちです。しかし、愚直な解法は通用しなかったり、独特な発想が必要だったり、数学的考察が必要となったりします。

そのような問題は「こういう問題はこうやって解く」という体系化が困難です。その困難さに本書は真っ向から挑戦しました!!!

たとえば、


  • 全探索の勘所を掴んだり
  • バケット連想配列を有効活用したり
  • ランレングス圧縮などといった地味に実装が難しい問題を徹底解説したり
  • 「周期性」「パリティ」「言い換え」「ペアリング」などの数学的考察を体系化したり

しています。各節の練習問題まで演習すれば、ほとんどの ABC の C 問題は解けるようになるでしょう!

 

5. 上級編 〜 本格的なアルゴリズムの世界へ!

中級編までやり込めば、もう十分に AtCoder のコンテストに自信を持って取り組めるでしょう!

上級編では、いよいよ「〜法」と名前が付いているような本格的なアルゴリズムを学んでいきます。具体的には



を学びます。本書を終えた頃には、今後あらゆるアルゴリズムを学ぶのに十分な思考力が身についているはずです!

 

6. おわりに

今まで Qiita やこのブログで、さまざまな記事を書いてきました。今回の本は、それらの集大成と言えるものです (もちろんこれからも書きます)。僕がこれまで AtCoder の布教活動や解説活動をして来たのは、競プロという世界を知ることで人生が切り開かれて幸せになれる人がたくさんいるはずで、その方々がこの世界を知れるキッカケを作りたいという想いからでした。

最近は AtCoder に入門するための有益な情報がたくさん発信されるようになって来ました。そんな時代だからこそ、これから AtCoder を始めたい方々のための情報を一冊の本にまとめあげることには大きな意義があると考えました。

誰もが、それぞれの人生にとって有益な情報に触れられる世界を目指すキッカケになったならば、とても嬉しいです。

AtCoder ABC 250 E - Prefix Equality (水色, 500 点)

とても色んな解法が考えられる問題ですね。ハッシュで殴るのが最も簡単だとは思います。そのほかにもさまざまな解法が考えられます。

問題概要

2 つのサイズ  N の整数列  a_{0}, a_{1}, \dots, a_{N-1} b_{0}, b_{1}, \dots, b_{N-1} が与えられます。

これらの数列に対して  Q 回のクエリが与えられます。各クエリでは  N 以下の整数  x, y が与えられますので、

  • 数列  a の先頭から  x 個の要素: a_{0}, a_{1}, \dots, a_{x-1}
  • 数列  b の先頭から  y 個の要素: b_{0}, b_{1}, \dots, b_{y-1}

が集合として一致するかどうかを判定してください。

制約

  •  1 \le N, Q \le 2 \times 10^{5}

解法 1:ハッシュで殴る

この問題の難しさは

  1.  i = 0, 1, \dots, N に対して、各数列の先頭から  i 個とってできる集合を求めたいが、それらすべて保存するのはメモリが足りない
  2. 各クエリに対して、集合が一致するかどうかを判定するには  O(N) の時間を要する (std::set の場合は  O(N \log N))

というところにあります。しかしこれらの問題を一度にまとめて解決してしまう方法があります。それは Zobrist Hash などのハッシュを使う方法です。

 x = 0, 1, \dots, N に対して、 a_{0}, a_{1}, \dots, a_{x-1} からなる集合を 1 つの整数値として表現してしまうのです。

そのようなことが可能なハッシュであればなんでもよいのですが、集合をハッシュ値で表すには Zobrist Hash が便利です。その方法はいたって簡単です!


  1. 集合の各要素に対して乱数を割り当てる
  2. 割り当てた乱数の XOR をとる

乱数を割り当てる部分は、いい感じの関数があります。Codeforces ブログで提供されているので、これをパクらせてもらいましょう!!!

実行してみないと値が分からない chrono::steady_clock::now().time_since_epoch().count() を活用しているため、とても強いです。

codeforces.com

総合して、計算量は  O(N \log N + Q) です。

Zobrist Hash についての remark

  1. Zobrist Hash は XOR をとるものであるため、要素の「挿入」と「削除」がともに高速にできます
  2. Zobrist Hash は「要素の種類」のみに対応しているため、「要素の個数」まで知りたい場合は、XOR をとる代わりに「普通の和」をとります (参考:chokudai さんのツイート)
#include <bits/stdc++.h>
using namespace std;

// 整数値 x にハッシュ値を割り当てる関数
struct custom_hash {
    static uint64_t splitmix64(uint64_t x) {
        x += 0x9e3779b97f4a7c15;
        x = (x ^ (x >> 30)) * 0xbf58476d1ce4e5b9;
        x = (x ^ (x >> 27)) * 0x94d049bb133111eb;
        return x ^ (x >> 31);
    }

    size_t operator() (uint64_t x) const {
        static const uint64_t FIXED_RANDOM =    
            chrono::steady_clock::now().time_since_epoch().count();
        return splitmix64(x + FIXED_RANDOM);
    }
} rng;

int main() {
    // Zobrist Hash
    // hashA[i] := 数列 a の先頭から i 個分の集合を表すハッシュ値
    int N;
    cin >> N;

    // N 個の入力を受け取って、Zobrist Hash を返す関数
    auto hashing = [&]() -> vector<uint64_t> {
        vector<uint64_t> hash(N + 1, 0);
        set<long long> S;  // すでにあるかを確認する

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

            // すでに含まれている場合は何もしない
            if (S.count(x)) {
                hash[i + 1] = hash[i];
                continue;
            }
            S.insert(x);
            hash[i + 1] = hash[i] ^ rng(x);
        }
        return hash;
    };

    const auto& hashA = hashing();
    const auto& hashB = hashing();

    // クエリ処理
    int Q;
    cin >> Q;
    while (Q--) {
        int x, y;
        cin >> x >> y;
        if (hashA[x] == hashB[y]) cout << "Yes" << endl;
        else cout << "No" << endl;
    }
}

解法 2:set で頑張る

明快な解説が kyopro_frineds さんによってなされています!

atcoder.jp

解法 3:数列 a を正規化して、種類数と最大値

とても頭の良い解法です。適切な数値変換により、数列  a

 0, 1, 2, 3, 1, 1, 2, 4, 3, 2, 1, 5, \dots

というように、「新しく登場する値は、今まで登場した値の最大値 + 1」という状態に変形することが可能です。

このように変形した状態ならば、A と B の集合一致性を「種類数と最大値の一致」のみで判定可能になります。

atcoder.jp

AtCoder ABC 250 D - 250-like Number (茶色, 400 点)

緑色下位 diff かなと思っていたのですが、これが茶色なのすごいですね!

前提知識

問題概要

素数  p \lt q を用いて  pq^{3} と表される数を「250 に似た数」であると言います。

整数  N が与えられますので、 1 以上  N 以下の「250 に似た数」の個数を求めてください。

制約

  •  1 \le N \le 10^{18}

考えること

まずは全探索に基づく解法を考えてみましょう!! 一般に数学的な見た目の問題では、過度に怖がらずに、落ち着いて全探索解法を考えることで活路を見出せることが多いです!!

 p, q を全探索すればよいのですから、次のように実装できます。

long long res = 0;  // 求める個数
for (long long p = 1; p <= N; ++p) {
    if (p が素数でない) continue;
    for (long long q = p + 1; p * q * q * q <= N; ++q) {
        if (q が素数) ++res;
    }
}

まずはこういう発想ができることがとても大切です。このアルゴリズムを少しずつ改善していきましょう。

 

改善 1:変数を固定して考える

今回の問題では 2 つの変数  p, q が登場します。これらを同時に動かして考えているから、アルゴリズムの効率が悪いのです。そこで重要な考え方は


変数を 1 つ固定して考える


というものです (類題たち)。ものすごく使える考え方ですので、ぜひともマスターしたいところです!!

さて、今回変数を固定するにあたって、戦略は 2 つ考えられます。

  1. 変数  p を固定する
  2. 変数  q を固定する

このうちのどちらをとっても、AC に辿り着けます。ここでは変数  q を固定する方を選択します。なお、変数  p を固定する方法については、公式解説に載っています。

atcoder.jp

変数  q の値を決め打つ前に、変数  q が動く範囲を考えてみましょう。

 pq^{3} \le N

なのですから、最悪でも  q^{3} \le N です。よって、 q \le N^{\frac{1}{3}} です。

 N \le 10^{18} より、 q \le 10^{6} の範囲を調べれば十分だと言えます。

 q を固定して考える解法は、全体としては次のように実装します。

long long res = 0;  // 求める個数
for (long long q = 2; q * q * q <= N; ++q) {
    if (q が素数でない) continue;
    
    // p は p < q と p * q^3 <= N を満たす素数である
    // そのような p の個数は、min(q - 1, N / q / q / q) 以下の素数の個数である
    long long pmax = min(q - 1, N / q / q / q);
    res += (pmax 以下の素数の個数);
}

 

改善 2:エラトステネスのふるいで素数列挙

エラトステネスのふるいを用いると、素数を列挙できます。今回は  p \lt q \le 10^{6} であると分かっているので、 10^{6} 以下の素数を調べれば十分です。

エラトステネスのふるいによって、 10^{6} 以下の素数を列挙して、以下の配列を求めましょう。


prs[i]i 番目の素数


この配列を用いると、今回の問題を解くコードは次のように改良できます。

long long res = 0;  // 求める個数
for (long long q : prs) {
    if (q * q * q > N) break;

    // p は p < q と p * q^3 <= N を満たす素数である
    // そのような p の個数は、min(q - 1, N / q / q / q) 以下の素数の個数である
    long long pmax = min(q - 1, N / q / q / q);
    res += (pmax 以下の素数の個数);
}

 

改善 3:二分探索

最後に、整数 pmax に対して「pmax 以下の素数の個数」を求める方法を考えましょう。

実は素数を列挙した配列 prs さえあれば、二分探索によって容易に求められます。

  1.  x 番目 (0-indexed) の素数pmax より大きい最小の  x を二分探索で求める
  2. このとき、 x は「pmax 以下の素数の個数」を表す

このうちの 1 の部分は、二分探索法で求められます。 計算量は 「 N^{\frac{1}{3}} 以下の素数の個数を  P としたとき、 O(\log P) です。

 10^{6} 以下のすべての素数  q に対して二分探索を実施しても、十分間に合います。

 

コード

以上の工夫をすべて取り入れたコードは次のように書けます。

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

vector<int> Era(int n) {
    vector<int> res;
    vector<bool> isprime(n, true);  // ふるい
    isprime[0] = false; isprime[1] = false;
    for (int i = 2; i < n; ++i) isprime[i] = true;
    for (int i = 2; i < n; ++i) {
        if (isprime[i]) {
            res.push_back(i);
            for (int j = i*2; j < n; j += i) {
                isprime[j] = false;
            }
        }
    }
    return res;
}

int main() {
    long long N;
    cin >> N;

    // エラトステネスのふるい
    vector<int> prs = Era(1000000);

    long long res = 0;
    for (long long q : prs) {
        if (q * q * q > N) break;

        long long pmax = min(q - 1, N / q / q / q);

        // pmax 以下の素数の個数を二分探索で求める
        long long low = -1, high = prs.size();
        while (high - low > 1) {
            long long x = (low + high) / 2;
            if (prs[x] > pmax) high = x;
            else low = x;
        }
        res += high;
    }
    cout << res << endl;
}

AtCoder ABC 250 C - Adjacent Swaps (茶色, 300 点)

実はアルゴ式でもよく似た問題をすでに出していました!

algo-method.com

問題概要

 1, 2, \dots, N がこの順に並んでいます。この数列に対して  Q 回のクエリが投げられました。

各クエリでは、値  v が指定されて、次の操作を実行します。


数列中の整数  v に対し、その右隣の要素が存在するならば、その要素と swap する。存在しないならば左隣の要素と swap する


 Q 回の操作を終えたあとの数列を求めてください。

制約

  •  2 \le N \le 2 \times 10^{5}
  •  1 \le Q \le 2 \times 10^{5}

考察

最初の注意点として、問題文は  1, 2, \dots, N というように 1 始まりとなっていますが、ここでは  0, 1, \dots, N-1 というように 0 始まりで考えます。与えられるクエリ  v も 1 を引いて考えます。

さて、この問題の難しいところは「クエリが与えられたときに、整数値  v がどこにあるのかが分からなくなる」ことです。

その場合に最もよく採られる解決方法は、次のように「要素がどこにあるか」を表すデータ構造を用意することです!!!(→ 類題たち)


pos[v] ← 数列 val において、要素 v が何番目の要素であるか


このデータは、とくに数列 val が順列であるとき逆順列と呼びます。たとえば val  = (1, 2, 0) のとき、逆順列は pos  = (2, 0, 1) です。

  • 0 は 2 番目の要素です
  • 1 は 0 番目の要素です
  • 2 は 1 番目の要素です

このように逆順列も合わせて考えることで、この問題は解けます。なお、連結リストを用いる別解もあるので、それも後述します。

解法 (1):逆順列も管理する

順列を val、逆順列を pos と表すことにしましょう。そうすれば、次のように考えられます。


  1. v の位置 pp = pos[v] によって取得できる
  2. 位置 p の右隣の位置を p2 = p + 1 とする (右端の場合は p2 = p - 1)
  3. swap(val[p], val[p2]) を実行する

ただしこのとき、逆順列の方も更新が必要であることに注意しましょう。次のようにします。


  1. 位置 p2 の要素の値 v2 = val[p2] を取得する
  2. swap(pos[v], pos[v2]) を実行する

これらの作業は  O(1) で実行できますので、クエリ全体に要する計算時間は  O(Q) となります。

最初に入力を受け取ったり、配列 pos を初期化したりする処理も合わせて、全体の計算量は  O(N + Q) となります。

コード

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

int main() {
    // 初期化 (最初は val, pos ともに 0, 1, ..., N-1)
    int N, Q;
    cin >> N >> Q;
    vector<int> val(N), pos(N);
    for (int i = 0; i < N; ++i) val[i] = pos[i] = i;

    // 各クエリ
    while (Q--) {
        // 入力
        int v;
        cin >> v;
        --v;  // すべて 0 始まりで考える

        int p = pos[v];
        int p2 = (p < N - 1 ? p + 1 : p - 1);
        int v2 = val[p2];

        swap(val[p], val[p2]);
        swap(pos[v], pos[v2]);
    }

    // 出力 (1 始まりに直す)
    for (auto v : val) cout << v + 1 << " ";
    cout << endl;
}

別解:連結リスト

技術的な詳しい話については、アルゴ式の一連の問題集を参考にしてください。

algo-method.com

要素をつなぎ変えたり、削除したり (今回は削除は不要) する処理は、連結リストを用いて容易に表現できます (→ 類題たち)。今回は具体的には次の 2 つのデータを用意しましょう。


  • nex[v] ← 要素 v の次の要素は何か (存在しないなら -1)
  • bak[v] ← 要素 v の前の要素は何か (存在しないなら -1)

これらのデータを逐次更新していきます。計算量はやはり  O(N + Q) となります。

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

int main() {
    // 初期化
    int N, Q;
    cin >> N >> Q;
    vector<int> nex(N, -1), pre(N, -1);
    for (int i = 0; i < N; ++i) {
        if (i + 1 < N) nex[i] = i + 1;
        if (i - 1 >= 0) pre[i] = i - 1;
    }

    // 連結リストの出力
    auto print = [&]() -> void {
        // 先頭を探す
        int v = 0;
        for (; v < N; ++v) if (pre[v] == -1) break;
        while (v != -1) {
            cout << v + 1 << " ";
            v = nex[v];
        }
        cout << endl;
    };

    // 各クエリ
    while (Q--) {
        int v;
        cin >> v;
        --v;

        // v1, v2, v3, v4 の順に繋ぐようにする
        int v1, v2, v3, v4;
        if (nex[v] != -1) {
            // 右隣がある場合
            v1 = pre[v], v2 = nex[v], v3 = v, v4 = nex[v2];
        } else {
            // 右隣がない場合
            v4 = nex[v], v3 = pre[v], v2 = v, v1 = pre[v3];
        }

        // 進行方向をつなぎ変える
        if (v1 != -1) nex[v1] = v2;
        nex[v2] = v3;
        nex[v3] = v4;

        // バック方向をつなぎ変える
        if (v4 != -1) pre[v4] = v3;
        pre[v3] = v2;
        pre[v2] = v1;
    }

    // 出力
    print();
}