ひらめの日常

プログラミングと読書と

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

はじめに

勝ち続ける意志力 (小学館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

ABC140-D Face Produces Unhappiness (400)

問題はこちら

atcoder.jp

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

操作:  1 \leq l \leq r \leq N となる  l, r を選び、  [l, r] 内にある文字列を左右反転させ、方向も反転させる。

考え方

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

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

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

  • LL RR LL RLL LL LL R
  • R LLLL RR RRRR R

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

  • L RRRRRR RRRRR
  • L RRRRRL 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

頂点数  n の木が与えられる(木なので辺の数は  n - 1)。

以下のような  m 個のクエリ  q _ 1, q _ 2, ..., q _ i が投げられるので、それぞれに対する答えを出力せよ。

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

考え方

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

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

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

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

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

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

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

ペア 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

長さ  n の 配列  a が与えられる。一回の操作によって任意の要素一つ、  a_i を2で割って切り捨てることを行う。 (つまり、  a _ {i} :=\left\lfloor\frac{a _ i}{2}\right\rfloor

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

考え方

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

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

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

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

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

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

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

以下は簡略化のために  O(max(a)) = O(n) として話を進める。 まず、全ての要素数 O(nlog(n)) である。(一つの要素は2で割っていくので  log(n) 個存在し、それが  n 個あるため。)

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

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

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

解答

#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

ABC123-D Cake 123 (400)

問題はこちら

atcoder.jp

美味しさは以下のように表される。

  •  X 種類のケーキ  A _ 1, A _ 2, ..., A _ X
  •  Y 種類のケーキ  B _ 1, B _ 2, ..., B _ Y
  •  Z 種類のケーキ  C _ 1, C _ 2, ..., C _ Z

この時、それぞれのケーキ美味しさの合計として大きい順に  K 個出力しなさい。

 \begin{array}{l}{1 \leq X \leq 1000}, \ {1 \leq Y \leq 1000}, \ {1 \leq Z \leq 1000}, \ {1 \leq K \leq \min (3000, X \times Y \times Z)}\end{array}

考え方

 X \times Y \times Z の全探索をすると  O(10 ^ 9) のループが周り、さらに大きい順に出力するので間に合わない。そこで、計算量を落とすことを考える。

いろんな解法があり、勉強になったので3つほど載せておく。元となる考え方は K が最大で3000 というところに注目するところにある。

解答1 - 解の候補を絞る

 A B の組み合わせを  X \times Y 分だけ全列挙すると、 O(10 ^ 6) となるので、sortしても大丈夫。この配列を  A \times B とおく。

大きい方から  K 個ということは、以下が成り立つ。

  •  A \times B からは最大でも  K 個使われる。
  •  C からは最大でも  K 個使われる。

よって、それぞれの配列の大きい方から  K ずつだけループを回して、大きい順に値を保持し、最後にsortして  K 個分出力すれば良い。計算量はここのsortがボトルネックとなって、  O(K ^ 2 \log(K))

#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++)
#define all(obj) (obj).begin(), (obj).end()

int main() {
    ll x, y, z, k;
    cin >> x >> y >> z >> k;
    vl a(x), b(y), c(z);
    rep(i, x) cin >> a[i];
    rep(i, y) cin >> b[i];
    rep(i, z) cin >> c[i];

    vl ab;
    rep(i, x) rep(j, y) ab.emplace_back(a[i] + b[j]);
    sort(all(ab), greater<>());
    sort(all(c), greater<>());

    vl ans;
    rep(i, min(k, x * y)) rep(j, min(k, z)) ans.emplace_back(ab[i] + c[j]);
    sort(all(ans), greater<>());

    rep(i, k) cout << ans[i] << '\n';

    return 0;
}

Submission #7171632 - AtCoder Beginner Contest 123

解答2 - 貪欲とpriority_queueを使う

 A, B, C をそれぞれ大きい順にsortしておくとする。

最大値は  A _ 0 + B _ 0 + C _ 0 である。この次に大きいのはどれかということを考える。しかし、一意に定まりそうではないので候補を絞ることにする。すると、次の候補は以下の3つであるということがわかる。

  •  A _ 1 + B _ 0 + C _ 0 A のindexを一つだけ進めた。
  •  A _ 0 + B _ 1 + C _ 0 B のindexを一つだけ進めた。
  •  A _ 0 + B _ 0 + C _ 1 C のindexを一つだけ進めた。

なので、現在の最大値をpopした上で、これらを全て priority_queue にpushする。すると、次はtopにあるものが2番目に大きいものとなり、順に大きいものをpopしていくことができる。計算量は、priority_queue からpopする回数が  K 回、上記のように候補を3つpushする回数が  3K 回なので、 O(K log(K)) で間に合う。

ここで実装上の注意点は以下のようになる。

  • priority_queue にそれぞれのindexも含めて管理する。なぜなら、popした後にindexを一つ進める作業が必要になるため、和の値とそれぞれのindexの情報が必要。
  • 一度見たindexの和の値は priority_queue にpushしないように気をつける。例えば  A _ 1 + B _ 0 + C _ 1 は以下の二つのものから到達可能であり、重複して出力してしまう可能性があるからだ。
    •  A _ 1 + B _ 0 + C _ 0 から、 C のindexを増やした時。
    •  A _ 0 + B _ 0 + C _ 1 から、 A のindexを増やした時。

この辺の実装は以下の記事を参考にして実装させていただいた。

drken1215.hatenablog.com

#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++)
#define all(obj) (obj).begin(), (obj).end()

using data = pair<ll, vl>;

int main() {

    ll x, y, z, k;
    cin >> x >> y >> z >> k;
    vl a(x), b(y), c(z);
    rep(i, x) cin >> a[i];
    rep(i, y) cin >> b[i];
    rep(i, z) cin >> c[i];
    sort(all(a), greater<>()), sort(all(b), greater<>()), sort(all(c), greater<>());

    priority_queue<data> ans;
    set<data> used;
    ans.push(data(a[0] + b[0] + c[0], vl({0, 0, 0})));
    while (k-- > 0) {
        auto now = ans.top();
        ans.pop();
        cout << now.first << '\n';
        ll ia = now.second[0], ib = now.second[1], ic = now.second[2];

        data tmp;
        if (ia + 1 < a.size()) {
            tmp = data(a[ia + 1] + b[ib] + c[ic], vl({ia + 1, ib, ic}));
            if (used.find(tmp) == used.end()) {
                used.insert(tmp);
                ans.push(tmp);
            }
        }
        if (ib + 1 < b.size()) {
            tmp = data(a[ia] + b[ib + 1] + c[ic], vl({ia, ib + 1, ic}));
            if (used.find(tmp) == used.end()) {
                used.insert(tmp);
                ans.push(tmp);
            }
        }
        if (ic + 1 < c.size()) {
            tmp = data(a[ia] + b[ib] + c[ic + 1], vl({ia, ib, ic + 1}));
            if (used.find(tmp) == used.end()) {
                used.insert(tmp);
                ans.push(tmp);
            }
        }
    }
    return 0;
}

Submission #7171780 - AtCoder Beginner Contest 123

解答3 - K個以上になる境目の値を二分探索

ここでも  A, B, C をそれぞれ大きい順にsortしておくとする。

 K 個以上になる美味しさの合計の境目を二分探索で探索」し、二分探索内での判定方法として「美味しさの合計が  p 以上であるものが  K 個以上あるかどうか調べる」方法を考える。

まず後者は、以下のように枝刈りをすれば  O(K ^ 2) の計算量で抑えられる。

auto solve = [&](ll p) -> bool {
    ll cnt = 0;
    rep(i, x) { // ここは最大でK回ループがまわる
        rep(j, y) { // ここから下は最大でK回ループがまわる
            rep(l, z) {
                ll val = a[i] + b[j] + c[l];
                if (val < p) break;
                if (++cnt >= k) {
                    return true;
                }
            }
        }
    }
    return false;
};

なぜか???それは、 A, B, C をそれぞれ大きい順にsortしてあるので、以下の操作をすることにより  y, z の二重ループが高々  K 回しか回ることがないからだ。

  • 合計が  p より小さいなら一番ネストの深いループを抜ける。
  • 合計が  p 以上なら、カウントを一つ増やし、 K 以上になったら関数をreturnする。

よって、二分探索内での判定は可能になった。

最後に、境目がわかった後にどうすれば良いのかを考える。この境目を  Border とする。

  • 合計が   Border 以上のものは  K 個以上ある。(が、最大で何個あるかどうかはわからない...!)
  • 合計が  Border + 1 以上のものは  K 個より少ない。

よって、以下のようにして上位  K 個を求めることで間に合う。

  • 合計が  Border + 1 以上のものを全部列挙する。 これは先ほどの二分探索内での判定方法をほとんど同じ。
  • この個数が  K 個よりも少なければ、残りの美味しさは全て  Border であるので、それをpushする。

計算量は、二分探索に  O(log(A _ {max} + B _ {max} + C _ {max})) 、枝刈りに  O(K ^ 2 ) より、  O(K ^ 2 log(A _ {max} + B _ {max} + C _ {max})) で間に合う。

この考え方は公式の解説を参考にした。
https://img.atcoder.jp/abc123/editorial.pdf

#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++)
#define all(obj) (obj).begin(), (obj).end()

int main() {
    ll x, y, z, k;
    cin >> x >> y >> z >> k;
    vl a(x), b(y), c(z);
    rep(i, x) cin >> a[i];
    rep(i, y) cin >> b[i];
    rep(i, z) cin >> c[i];

    sort(all(a), greater<>()), sort(all(b), greater<>()), sort(all(c), greater<>());

    auto solve = [&](ll p) -> bool {
        ll cnt = 0;
        rep(i, x) { // ここは最大でK回ループがまわる
            rep(j, y) { // ここから下は最大でK回ループがまわる
                rep(l, z) {
                    ll val = a[i] + b[j] + c[l];
                    if (val < p) break;
                    if (++cnt >= k) {
                        return true;
                    }
                }
            }
        }
        return false;
    };

    ll s = -1, e = a[0] + b[0] + c[0] + 1;
    while (e - s > 1) {
        ll mid = (s + e) / 2;
        if (solve(mid)) s = mid;
        else e = mid;
    }
    vl ans;
    rep(i, x) {
        rep(j, y) {
            rep(l, z) {
                ll val = a[i] + b[j] + c[l];
                if (val < s + 1) break;
                ans.emplace_back(val);
            }
        }
    }
    while (ans.size() < k) ans.emplace_back(s);
    sort(all(ans), greater<>());
    for (auto val: ans) cout << val << '\n';
    return 0;
}

Submission #7171934 - AtCoder Beginner Contest 123

ABC136-E Max GCD (500)

問題はこちら

atcoder.jp

 A_1, A_2, ..., A_N から  i \neq j となる  A_i, A_j を選び、 A_i = A _ i + 1, A_j = A _ j - 1 とする。この時、 K 以下の操作回数で  A の最大公約数として考えられるもののうち、最大のものを求めよ。

考え方

step1 - 解の候補

まず、 A_i に+1して、 A_j に-1するという操作は、 A_i の値を一つ  A_j に移動する操作と考えることができる。

次に大事なのは、答えの候補は  A の和の約数 となること。これはなぜかを考えてみる。今、答えとなる最大の最大公約数を  x とする。

  • 約数であるという性質から、 A _ 1 \% x = A _ 2 \% x =...= A _ N \% x = 0
  • modの性質から、 (A _ 1 + A _ 2 + ... + A _ N ) \% x = 0
  • 今回の操作は片方に+1, もう片方に-1するだけなので、総和は操作終了後にも変わらない。
  • 以上より、答えの候補は  A の和の約数となる。

なので、ある最大公約数  x K 回以下の操作によって達成されるかをすべて確かめ、達成されるものの中で最大のものが答えとなる。

step2 - 達成可能かを確認する

 x で割ったあまりが小さい方(=  A_i)から、大きい方(=  A_j)へと渡すのが操作方法が少なくて良い方法だとわかる。 A _ i \% x = a _ i ,  A _ j \% x = a _ j ,  a _ i \lt a _ j とおく。(簡単にするため、二つの数字でやり取りすることで割り切れる場合を考えてみる。)

  •  a_i から  a_j へ渡して  x で割り切れるようにする時。操作回数は  max(a _ i, x - a _ j)
  •  a_j から  a_i へ渡して  x で割り切れるようにする時。操作回数は  max(a _ j, x - a _ i)
  •  a _ i \lt a _ j より、  max(a _ i, x - a _ j) \lt max(a _ j, x - a _ i)

よって、 x で割った余りを小さい順でsortして、インデックス i より小さい側を渡す側。インデックス i 以上を渡される側として、必要な操作回数が K 以下であれば満たすと判定すれば良い。

解答

#include <bits/stdc++.h>

using namespace std;

using ll = long long;

#define rep(i, n) for(ll i = 0; i < (ll)(n); i++)
#define repr(i, n) for(ll i = ll(n - 1); i >= 0; i--)
#define each(i, mp) for(auto& i:mp)
#define all(obj) (obj).begin(), (obj).end()

/* ------------- ANSWER ------------- */
/* ---------------------------------- */
// 約数列挙
vector<ll> divisor(ll n) {
    vector<ll> res;
    for (ll i = 1; i * i <= n; ++i) {
        if (n % i == 0) {
            res.emplace_back(i);
            if (i != n / i) res.emplace_back(n / i);
        }
    }
    return res;
}

int main() {

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

    vector<ll> divs = divisor(accumulate(all(a), 0LL));

    ll ans = 0;
    each(e, divs) {
        vector<ll> mods(n);
        rep(i, n) mods[i] = a[i] % e;
        sort(all(mods));

        vector<ll> minus(n + 1);
        rep(i, n) minus[i + 1] = minus[i] + mods[i];

        vector<ll> plus(n + 1);
        repr(i, n) plus[i] = plus[i + 1] + e - mods[i];

        for (ll i = 0; i <= n; ++i) {
            if (max(plus[i], minus[i]) <= k) ans = max(ans, e);
        }
    }
    cout << ans << '\n';
    return 0;
}

Submission #7148617 - AtCoder Beginner Contest 136