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

問題はこちら

atcoder.jp

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

• となる頂点と頂点 の間にコストの辺を追加する。

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

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

解法1 - seg木でdp

が与えられた時に、 までの最小コストは、「」と「に到達する最小コスト + 」の小さい方 である。

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

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

ここでのボトルネックは、「に到達する最小コスト」を計算するところで、ここを毎回線形探索すると間に合わない。そこで、seg木を使うことで高速に区間の最小値を求め、それを用いて までの最小コストを更新すれば、 となり間に合う。（なお、区間クエリ、点更新なので遅延セグ木である必要はない。）

• 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の解法。 今回の問題における辺の張り方の本質は、 から まで、 全ての となるような頂点の組 の距離が等しい という点。なので、 から に辺を張り、その間の点は全てどちらかと同じ点のように扱えると楽である。（ここまでは考えたけどどうやって実現するのかわからなかった。）

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

計算量は で間に合う。

解答

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';
}

関連

• seg木でdpする他の問題 : Codeforces Round #587 (Div. 3) F. Wi-Fi - ARMERIA
• 似たような問題: C - 蛍光灯

AtCoder: ABC142-E Get Everything (500)

問題はこちら

atcoder.jp

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

考え方

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

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

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

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

• 箱 を開けることができる -> bit目のフラグを立てることができる。
• 鍵 が開けることのできる箱の集合 -> 全ての の和集合。
• 箱 が空いている状態 -> bit目のフラグが立っている。

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

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

これは、計算量 で間に合う。

解答

#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

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

• 頂点は、 まである。
• 辺 は、
  • 今の状態を とすると、s と 鍵iが開けられる集合 の和集合 へと遷移する。
  • そのコストは ] である。
• このようなグラフで、頂点 から へと遷移する最短路を求めよ。

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

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

計算量は、頂点数 、辺の数 より、 で間に合う。

#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新書)

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

www.youtube.com

印象に残ったところメモ

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

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

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

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

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

人の目を気にしないこと

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

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

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

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

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

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

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

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

感想

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

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

AtCoder: ABC140-E Second Sum (500)

問題はこちら

atcoder.jp

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

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

考え方

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

atcoder.jp

step1 - 問題の言い換え

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

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

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

よって、上の図のように を定めると、一つの が答えに寄与する回数は

step2 - 実装方法

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

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

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

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

解答

#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

AtCoder: ABC140-D Face Produces Unhappiness (400)

問題はこちら

atcoder.jp

長さ の文字列 が与えられる。L は自分の左に L が来た時、R は自分の右に R が来た時、幸福になるという。以下の操作を 回以下繰り返して、幸福なものを最大いくつにできるか答えよ。

操作: となる を選び、 ] 内にある文字列を左右反転させ、方向も反転させる。

考え方

操作をする系は、その前後で何が変わるかを考えると良い（特に求める答えに関するもの）。今回の場合は、一回操作を行うたびに、その区間の両端の状態が変わる。 （いい加減こういうのに慣れたいですね...）

幸せになる数が増えるのは、LL, RR という並びが存在するときなので、操作をした時に内部の状態変化が答えに与える影響はない。しかし、両端とその隣の状態が変化し、最大でも +2 されることがわかる。

そこで、+2 を貪欲にやる方法を考えてみる。すると、同じものが続いている区間を反転すれば、両端が新しく条件を満たし、答えが +2 されると考えられる。この時点で、順番が反転することは考えなくてよくなり、向きが反転することだけ考えればよくなる。

• LL RR LL R → LL LL LL R
• R LLLL R → R RRRR R

注意するのは、以下のような時で、 +1 しかされない。

• L RRRRR → R RRRRR
• L RRRRR → L LLLLL

しかし、 +1 の操作は一回しか起こり得ないかつ、答えとしてありえる最大値 - 1 から最大値に移行する時に使用すると考えることができる。（つまり一番最後に行う。）

これらより、答えは 「min(もともと連続で続いている個数 + 2 * k, n - 1)」になる。

解答

考察が終わればいたって簡単。

#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;
    string s;
    cin >> s;

    ll ans = 0;
    rep(i, n - 1) {
        if (s[i] == s[i + 1]) ans++;
    }
    ans += 2 * k;
    cout << min(n - 1, ans) << '\n';
    return 0;
}

Submission #7416033 - AtCoder Beginner Contest 140

Codeforces Round #582 (Div. 3) G. Path Queries

問題はこちら

codeforces.com

頂点数 の木が与えられる（木なので辺の数は ）。

以下のような 個のクエリ が投げられるので、それぞれに対する答えを出力せよ。

• 求めるものは以下を満たす頂点 , , のペアの個数。
• 頂点 と を結ぶパスの中で、辺の最大の重みが を超えない。

考え方

以下のみの辺で連結になっている頂点数 が分かれば、その中を結ぶ頂点のペアの個数は だとわかる。よって、重み 以下の辺が出てきたら、その二つの頂点を同じグループに入れればいい。

このようなグループの構成は Union find木 を使えばいいということがわかる。

愚直に全てのクエリに対して順番にやると、毎回 Union find木を1から構成する必要があり、間に合わない。そこで、この問題を思い出す。

、クエリを先に読んでおいて、wが大きい順にクエリを処理する。こうすることで、既に存在する木に新たに条件を満たす辺を加えていくだけでよくなる。

ABC040-D 道路の老朽化対策について (500) - ひらめの日常

今回のポイントとして、 が小さい時に条件を満たすような頂点のペアは、それよりも大きい の時も条件を満たし、同じグループに属するということがある。なので、クエリを小さい順に処理する。こうすることで、上記の引用部分と同様に、すでに存在する木に新たに条件を満たす辺を加えていくだけでよくなる。

また、個数をカウントする方法も工夫が必要で累積和的に管理する。 が新たにグループになる時、今までの が属するそれぞれのグループで作れるペアの個数を引き、新たに作られたグループで作れるペアの個数を足す。

ペア u, v が新たに条件を満たす時。

count -= unionfind.size(u) * (unionfind.size(u) - 1) / 2;
count -= unionfind.size(v) * (unionfind.size(v) - 1) / 2;
unionfind.unite(u, v);
count += unionfind.size(u) * (unionfind.size(v) - 1) / 2;

解答

#include <bits/stdc++.h>

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

class UnionFind {
private:
    vector<ll> size; // グループに属する物の数．
public:
    vector<ll> par; // 親
    vector<ll> rank; // 木の深さ

    explicit UnionFind(unsigned int n) {
        par.resize(n);
        rank.resize(n);
        size.resize(n);
        rep(i, n) {
            par[i] = i;
            rank[i] = 0;
            size[i] = 1;
        }
    }

    // 木の根を求める
    ll find(ll x) {
        if (par[x] == x) {
            return x;
        } else {
            return par[x] = find(par[x]);
        }
    }

    // グループのサイズを求める．
    ll calc_size(ll x) {
        return size[find(x)];
    }

    // xとyの属する集合を併合
    void unite(ll x, ll y) {
        x = find(x);
        y = find(y);
        if (x == y) return;
        if (rank[x] < rank[y]) {
            par[x] = y;
        } else {
            par[y] = x;
            if (rank[x] == rank[y])rank[x]++;
        }
        size[x] = size[y] = size[x] + size[y];
    }

    // xとyが同じ集合に属するか否か
    bool is_same(ll x, ll y) {
        return find(x) == find(y);
    }
};

template<typename T> using minpq = priority_queue<T, vector<T>, greater<T>>;
using P = pair<ll, ll>;
using edge = pair<ll, P>;

int main() {

    ll n, m;
    cin >> n >> m;
    minpq<edge> que;
    rep(i, n - 1) {
        ll u, v, c;
        cin >> u >> v >> c;
        u--, v--;
        que.push(edge(c, P(u, v)));
    }
    vector<P> q(m);
    rep(i, m) {
        cin >> q[i].first;
        q[i].second = i;
    }
    sort(q.begin(), q.end());

    vector<ll> ans(m);
    UnionFind uf(n);
    ll cnt = 0;
    rep(i, m) {
        ll target = q[i].first, idx = q[i].second;

        while (!que.empty() && que.top().first <= target) {
            edge now = que.top();
            ll u = now.second.first, v = now.second.second;
            ll s1 = uf.calc_size(u), s2 = uf.calc_size(v);
            cnt -= s1 * (s1 - 1) / 2;
            cnt -= s2 * (s2 - 1) / 2;
            uf.unite(u, v);
            ll s3 = uf.calc_size(u);
            cnt += s3 * (s3 - 1) / 2;
            que.pop();
        }
        ans[idx] = cnt;
    }
    rep(i, m) cout << ans[i] << ' ';
    return 0;
}

Submission #59803208 - Codeforces

Codeforces Round #582 (Div. 3) D. Equalizing by Division

問題はこちら

codeforces.com

長さ の 配列 が与えられる。一回の操作によって任意の要素一つ、 を2で割って切り捨てることを行う。 （つまり、 ）

個の等しい要素を 中で得るには、何回操作を行えばいいか、その最小値を求めよ。

考え方

全ての を、0になるまで割る2して、各値を得るまでにかかった作業回数を記録しておく。コードの方がわかりやすいと思うのでその部分を抜粋する。

while (a[i] > 0) {
    mp[a[i]].emplace_back(t);
    a[i] /= 2;
    t++;
}

そして、存在している全ての要素に対して以下を行う。

• 要素数が よりも以上の場合は、要素をsortする。
• その後、 番目までの必要回数の和を計算する。

以上を行なって、 個以上作ることのできる要素の最小操作回数を求め、それが答えとなる。

なぜこれで間に合うのか？

最初は、全ての要素に対して、各要素を得るための操作回数をsortするために間に合わないと思っていたがそんなことはなかった。

以下は簡略化のために として話を進める。 まず、全ての要素数は である。（一つの要素は2で割っていくので 個存在し、それが 個あるため。）

次に、その各値に対応する操作回数をsortする部分だが、sortする対象の合計個数も高々 個である。よって、各値に対応する操作回数を全てsortしたとしても計算量は で抑えられ、時間内に間に合う。

基本的に、合計個数 あるものを、それぞれ 個を要素とするグループに分けたときを考える。計算量 以上となる同じ操作hogeを各グループに対して行なった合計の計算量は、合計個数全てに対する計算量で抑えられる。つまり、 。

（hogeの計算量が とかだと、グループに分けない方が計算量が小さいはず。今回は hoge に相当するのが sort なので、 以上の計算量である。）

解答

#include <bits/stdc++.h>

using namespace std;

using ll = long long;
#define rep(i, n) for(ll i = 0; i < (ll)(n); i++)
#define each(i, mp) for(auto& i:mp)

int main() {

    ll n, k;
    cin >> n >> k;
    vector<ll> a(n);
    rep(i, n) cin >> a[i];

    unordered_map<ll, vector<ll>> mp;
    rep(i, n) {
        ll t = 0;
        while (a[i] > 0) {
            mp[a[i]].emplace_back(t);
            a[i] /= 2;
            t++;
        }
    }

    ll ans = 1e18;
    each(e, mp) {
        vector<ll> times = e.second;
        if (times.size() >= k) {
            sort(times.begin(), times.end());
            ll now = accumulate(times.begin(), times.begin() + k, 0LL);
            ans = min(ans, now);
        }
    }
    cout << ans << '\n';
    return 0;
}

Submission #59801874 - Codeforces