優先度付き経験再生の実装・実験

要約

　優先度付き経験再生はAlphaZero方式の学習でも効果がありそう。

背景

　以前の記事でも軽く触れたが、優先度付き経験再生という手法がある。

　大雑把に言うとリプレイバッファからのサンプリング確率を一様ランダムではなく優先度で重み付けするものである。番目のサンプルの優先度をとしたとき、このサンプルを確率

$$ P(i) = \frac{p_i^\alpha}{\sum_j p_j^\alpha} $$

でサンプリングする。優先度をTD誤差に応じて適切に設定すればより重要なデータを多く学習することができ、学習速度や性能が向上するとのことである。Actor-Learnerを並列で動かす場合にはかなり性能が良いという報告もある。

　つまりAlphaZero方式の学習でも効果がありそうだと感じたので実装してみた。

　元論文では優先度の付け方として

1. TD誤差の絶対値の大きさによって順位付けし順位の逆数を優先度とする
2. TD誤差の絶対値をそのまま優先度とする

という2つの手法が提案されていたが、ここでは(2)を採用することとする。若干の変更点としてTD誤差の絶対値ではなく損失関数の値を利用する。

実装

　現状はMiacisのperブランチで開発を行っている。十分な安定性が確認できたらいずれmasterブランチにマージする。replay_buffer.cppやsegment_tree.cppが重要な部分となる。

更新・サンプリングの実装

　(2)の手法はSum-Tree(セグメント木)を用いて実装することで、優先度の更新、サンプリングがでできる。学習データを保持する配列に加えて、各データの優先度を保持するセグメント木を別に持つことになる。

　優先度の更新は通常のセグメント木の更新そのものとなる。

void SegmentTree::update(uint64_t x, float v) {
    sum_[x + n_ - 1] = v;
    for (uint64_t i = (x + n_ - 2) / 2; ; i = (i - 1) / 2) {
        sum_[i] = sum_[2 * i + 1] + sum_[2 * i + 2];
        if (i == 0) {
            break;
        }
    }
}

　サンプリングは0から損失の総和までの一様乱数をサンプリングし、値に応じて最下段まで木を降りていくことで実現する。

uint64_t SegmentTree::getIndex(float value, uint64_t k) {
    if (k >= n_ - 1) {
        //最下段まで来ていたらindexを返す
        return k - (n_ - 1);
    }
    return (value <= sum_[2 * k + 1] ? getIndex(value, 2 * k + 1) : getIndex(value - sum_[2 * k + 1], 2 * k + 2));
}

　データは通常の経験再生と同じように古い順に削除する。前回データを入れた位置を保持しておき、バッファをリング状に巡回する。

uint64_t SegmentTree::getIndexToPush(uint64_t k) {
    return (++next_push_index_) %= n_;
}

新データの挿入

　元論文では新しく生成されたデータは格納されている中で最大の優先度と同じ優先度を与えるとしているが、今回は置換表に保存していた情報から仮の損失値を計算し、それをもとにリプレイバッファへ格納する。

//このデータを入れる位置を取得
int64_t change_index = segment_tree_.getIndexToPush();

//そこのデータを入れ替える
data_[change_index] = std::make_tuple(pos.toSFEN(), teacher);

//priorityを計算
float priority = -2 * std::log(nn_output_policy[move.toLabel()] + 1e-10f) 
+ std::pow(nn_output_value - teacher.value, 2.0f);

//segment_treeのpriorityを更新
segment_tree_.update(change_index, std::pow(priority, alpha_));

　仮の損失値を計算する上での注意点として、置換表に保存されているPolicyやValueは局面に対するニューラルネットワークの生の出力とは異なる。たとえばPolicyでは置換表には合法手でマスクしたのちにSoftmax関数をかけたものを保存しているため、全指し手についてSoftmax関数をかける通常の出力より精度が良くなる。よってこの仮損失を2倍した値を利用している。この2倍という値に根拠はなく、ただの勘により定めた。

　また、今実装を見直していて気づいたのだが、Policyの仮損失の計算が、実際に指された指し手のみをOnehotベクトルとして計算するものになっている。教師を分布化する前に実装したものをそのままにしていたのだった。どうせ仮の値なのでそこまで影響を与えないとは思うが、いずれ修正する。

　これもまた実装を見直していて気づいたのだが、Valueを漸進的に更新するように実装を変更したのでValue側は探索を終えて精度がかなり高まったものを利用して損失を計算することになっている。上の件とも含めて、仮損失が良い推定値にはなっていないように思える。

　以下の実験はこの実装で計測してしまったのだが、新しいデータのサンプリング確率が不当に低くなっている可能性がある。

重点サンプリングによる補正

　論文で言及されている通り、一様分布ではない分布からサンプリングをするとバイアスが生じてしまうため、本来は重点サンプリングの理論から更新時に補正を行う。しかし今回はそれを入れなかった。なにかの論文でこの補正は行わなくても精度が落ちなかったというような記述を目にした覚えがあるが、どの論文だったか忘れてしまった。

実験

実験設定

　GTX 1080を2枚搭載したマシンでAlphaZero方式の学習を行った。2枚とも自己対局に使用している場合にデータ生成速度は33 pos / secほどとなる。学習1ステップごとに1秒のスリープを行ったため、ステップあたりのデータ生成速度もほぼ33 pos / stepと考えて良い。バッチサイズは128で学習をしたため、同じデータが何度か学習される設定となっている。そのような設定でこそ優先度に応じたサンプリングをする意味があるのではないかと思われる。

　の4通りについて実験を行った。元論文ではなどとしているが、扱う値がTD誤差と損失値と違うのでとりあえず大きい値で実験を行ってみることとする。のときは結局優先度が全て1で等しくなるので通常の一様ランダムでサンプリングを行う経験再生に一致する。

実験結果

棋譜から計算する検証損失

　floodgate2016年の棋譜から計算した検証損失は次のようになった。

左:Policy損失　右:Value損失

　Value損失ではほとんど差がなかったが、Policy損失ではを大きくした方が良い結果となった。優先度とする損失にはPolicy損失とValue損失を1:1で和をとったものを利用しているので、異なるデータ間で値の大小を比較する上ではPolicy損失の影響が大きいのではないかと思われる。Policy損失とValue損失に係数をかけて比を変えられるようにはしているが、このパラメータもチューニングしなければいけないとなると大変である。

技巧2との検証対局

　各で学習したパラメータを用いて技巧2(深さ制限4)と1手0.25秒でそれぞれ500局の対局を行った。対局時にはRTX 2080ti1枚を搭載したマシンを利用した。

	勝率	レート差
0	34.6%	-100.6
1	32.6%	-126.2
2	57.5%	+52.5
3	54.5%	+31.4

　今回試した中ではとしたときが最も良い結果となった。元論文の結果からするとかなり大きい値に思われるが、TD誤差から優先度をつけている元論文とは異なり、損失で優先度をつけていることが影響しているのかもしれない。たとえばPolicy損失では教師信号が探索回数を正規化した分布になるので、交差エントロピーには定数値として教師信号の自己エントロピーが足されている。Value損失に関しても、報酬の範囲を[0,1]として最終層がsigmoid関数で交差エントロピーを損失とする場合には、教師信号が0.5(引き分け)であれば損失の最小値が0ではない。微分を計算する際には定数値のシフトによる影響はないのだが、今回の手法では問題になり得るのかもしれない。

今後

　今回はを固定して100kステップの学習を行ったが、元論文で提案されている通り、学習を進めるにつれてを小さいくしていくことは自然である。前述した通り優先度の初期値についても実装にミスがいくらかあり、まだ改善の余地はあるのではないかと思われる。

　ここのところステップ数を短くして実験サイクルを多く回せるようにしているが、最終的に行う学習の設定と乖離しているのでは結局2度手間になってしまうかもしれないとも思い始めてきた。そろそろ試すアイデアも少なくなってきたので、ステップ数を大きくして性能が収束しきるまで学習させてみようと思う。

AtCoder Beginner Contest 129

結果

　E問題までの5完。Fを解けている人が少なく、Eまでの早解きゲームになっていたようだ。近のRatedでは6回連続でレートが伸びており、たまたま上手くいっている感じは否めないが気分は良い。

A問題

　ちゃんと問題文を読めているかちょっと不安になりつつの提出だった。

#include"bits/stdc++.h"
using namespace std;
using ll = int64_t;

int main() {
    ll P, Q, R;
    cin >> P >> Q >> R;
    cout << P + Q + R - max({ P, Q, R }) << endl;
}

B問題

　脳を使いたくなかったのでで大丈夫であることを確認した後は問題文に書いてある通りのことを実装した。

#include"bits/stdc++.h"
using namespace std;
using ll = int64_t;

int main() {
    ll N;
    cin >> N;
    vector<ll> W(N);
    for (ll i = 0; i < N; i++) {
        cin >> W[i];
    }

    ll ans = INT_MAX;
    for (ll T = 0; T < N - 1; T++) {
        ll S1 = 0, S2 = 0;
        for (ll i = 0; i < N; i++) {
            if (i <= T) {
                S1 += W[i];
            } else {
                S2 += W[i];
            }
        }
        ans = min(ans, abs(S1 - S2));
    }

    cout << ans << endl;
}

C問題

　最初は2個前までの数字だけを保持して上手くやろうと考えていたけどこんがらがってしまったのでおとなしくdp配列を使うわかりやすい形で実装した。

#include"bits/stdc++.h"
using namespace std;
using ll = int64_t;

int main() {
    ll N, M;
    cin >> N >> M;
    vector<ll> a(M);
    for (ll i = 0; i < M; i++) {
        cin >> a[i];
    }

    vector<bool> ok(N + 1, true);
    for (ll i = 0; i < M; i++) {
        ok[a[i]] = false;
    }

    constexpr ll MOD = 1e9 + 7;
    vector<ll> dp(N + 1, 0);
    dp[0] = 1;
    dp[1] = (ok[1] ? 1 : 0);
    for (ll i = 2; i <= N; i++) {
        if (ok[i]) {
            dp[i] = (dp[i - 1] + dp[i - 2]) % MOD;
        } else {
            dp[i] = 0;
        }
    }

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

D問題

　上下と左右それぞれでどれだけ繋がっているかを事前計算する部分で手間取ってしまった。累積和とって後ろからmaxを取り直していくだけなんだけど、障害物マスをINT_MAXとかで初期化すれば上手いこと場合分けいらなくなるのでは？ とか余計なことを考えたのがまずかった。おとなしく毎回場合分けを書いてAC。もっと簡単に実装できたのにやっているときにはなかなか思い浮かばない。

#include"bits/stdc++.h"
using namespace std;
using ll = int64_t;

int main() {
    ll H, W;
    cin >> H >> W;
    vector<string> S(H);
    for (ll i = 0; i < H; i++) {
        cin >> S[i];
    }

    vector<vector<ll>> row(H, vector<ll>(W, 0));
    vector<vector<ll>> col(H, vector<ll>(W, 0));

    for (ll i = 0; i < H; i++) {
        for (ll j = 0; j < W; j++) {
            row[i][j] = (S[i][j] == '.' ? 1 : 0);
        }
        for (ll j = 1; j < W; j++) {
            row[i][j] = (S[i][j] == '.' ? row[i][j] + row[i][j - 1] : 0);
        }
        for (ll j = W - 2; j >= 0; j--) {
            row[i][j] = (S[i][j] == '.' ? max(row[i][j], row[i][j + 1]) : 0);
        }
    }
    for (ll j = 0; j < W; j++) {
        for (ll i = 0; i < H; i++) {
            col[i][j] = (S[i][j] == '.' ? 1 : 0);
        }
        for (ll i = 1; i < H; i++) {
            col[i][j] = (S[i][j] == '.' ? col[i][j] + col[i - 1][j] : 0);
        }
        for (ll i = H - 2; i >= 0; i--) {
            col[i][j] = (S[i][j] == '.' ? max(col[i][j], col[i + 1][j]) : 0);
        }
    }

    ll ans = 0;
    for (ll i = 0; i < H; i++) {
        for (ll j = 0; j < W; j++) {
            ans = max(ans, row[i][j] + col[i][j]);
        }
    }

    cout << ans - 1 << endl;
}

E問題

　桁DPを書くだけとは思いつつ慣れていないのでこれがまた苦労する。普通のdpでも実装はメモ化再帰に頼りがちではあるけど、桁dpは特にforループで書く方法がわからない。特に困っていないので習得しようという気にもあまりならない。

　解説PDFを読んでみて、dp配列を二つ持たないといけないやつも今回みたいな以上・未満で二つ考えるのと同じことなのだなと思った。そう考えるとdp配列を二つ持たないといけない問題もめちゃくちゃ突飛な発想を求められているわけでもないのか。桁dpならすぐ見えることをちょっと見た目が変わっただけでわからなくなるのは寂しい。

#include"bits/stdc++.h"
using namespace std;
using ll = int64_t;

string L;
constexpr ll MOD = 1e9 + 7;
vector<vector<ll>> memo;

ll solve(ll i, bool small) {
    if (i == L.size()) {
        return 1;
    }

    if (memo[i][small] != -1) {
        return memo[i][small];
    }

    ll result = 0;
    if (small) {
        result = 3 * solve(i + 1, small) % MOD;
    } else {
        if (L[i] == '0') {
            //(0, 0)だけ
            result = solve(i + 1, false);
        } else {
            //(1, 0), (0, 1), (0, 0)
            result = (2 * solve(i + 1, small) % MOD + solve(i + 1, true)) % MOD;
        }
    }

    return memo[i][small] = result;
}

int main() {
    cin >> L;
    memo.resize(L.size(), vector<ll>(2, -1));
    cout << solve(0, false) << endl;
}

F問題

　数列の[i, j)範囲について問題の答えを返す関数solve(ll i, ll j)を作ったとき、solve(0, L) = pow(10, d) * solve(0, L / 2) + solve(L / 2, L) (は[L / 2, L)内にある数の桁数の和)という感じで分解できそうだという方針でやっていたけどサンプル3が合わず撃沈。どれくらい合わないのか確かめるために提出してみたらいくつもWAになったしTLEまでたくさん出たので全然ダメだった。

　解説PDFを読んでなんとかAC。桁が同じものはまとめて計算できそうというところにそもそも気づいていないし、気づいてもそこから行列累乗まで落とし込める気はしない。2段階考察が足りていなかった。

#include"bits/stdc++.h"
using namespace std;
using ll = int64_t;

ll L, A, B, M;

vector<vector<ll>>& operator*=(vector<vector<ll>>& lhs, vector<vector<ll>> rhs) {
    auto result = lhs;
    for (ll i = 0; i < result.size(); i++) {
        for (ll j = 0; j < result[i].size(); j++) {
            result[i][j] = 0;
            for (ll k = 0; k < lhs.size(); k++) {
                (result[i][j] += lhs[i][k] * rhs[k][j] % M) %= M;
            }
        }
    }
    return lhs = result;
}

int main() {
    cin >> L >> A >> B >> M;

    ll ans = 0;
    ll pre = 0;
    ll s = A;
    for (ll d = 1; d <= 18; d++) {
        ll target = 1;
        for (ll j = 0; j < d; j++) {
            target *= 10;
        }
        ll low = pre - 1, eq_high = L;
        while (low != eq_high - 1) {
            ll mid = (low + eq_high) / 2;
            ll s_mid = A + B * mid;
            (s_mid < target ? low = mid : eq_high = mid);
        }

        ll C_d = eq_high - pre;
        pre = eq_high;

        vector<vector<ll>> mat = {
                { target % M,     0, 0 },
                {          1,     1, 0 },
                {          0, B % M, 1 }
        };

        vector<vector<ll>> result = {
                { 1, 0, 0 },
                { 0, 1, 0 },
                { 0, 0, 1 }
        };

        while (C_d) {
            if (C_d % 2 == 1) {
                result *= mat;
            }

            C_d /= 2;
            mat *= mat;
        }

        vector<ll> v = { ans, s, 1 };
        ans = 0;
        s = 0;
        for (ll i = 0; i < 3; i++) {
            (ans += v[i] * result[i][0] % M) %= M;
            (s += v[i] * result[i][1] % M) %= M;
        }
    }

    cout << ans << endl;
}

Sarsa-UCT(λ)の実装・実験

要約

　Sarsa-UCT(λ)のλを調整しても明確な性能向上は見られなかった。

背景

　以前の記事の通りMCTSにおける価値の漸進的更新を実装した。

　これにより単なる平均を求める手法とは異なる手法へ改造することが容易になった。特に以前紹介したSarsa-UCT(λ)は自然な形で導入ができるため、パラメータを調整しつつ性能を実験した。

実装

　バックアップの際、で現在の値とバックアップしていく値の内分を取っていく。これは実質的に表形式のSarsa()に相当する。つまりとするとモンテカルロ法(平均化)と同じことになり、通常のMCTSと一致する。更新ステップ幅alphaの調整も可能だが、今回はとりあえず平均化する場合と同じ値とした。

void backup(std::stack<int32_t>& indices, 
            std::stack<int32_t>& actions) {
    auto leaf = indices.top(); indices.pop();
    auto value = hash_table_[leaf].value;

    //Sarsa-UCT(λ)のλ
    static constexpr float LAMBDA = 0.9;

    while (!actions.empty()) {
        auto index = indices.top();  indices.pop();
        auto action = actions.top(); actions.pop();

        //手番が変わるので符号反転
        value = -value;

        //現在注目しているノード
        UctHashEntry& node = hash_table_[index];

        //探索回数の更新
        node.N[action]++;
        node.sum_N++;

        //値の更新
        auto curr_v = node.value;
        float alpha = 1.0f / (node.sum_N + 1);
        node.value += alpha * (value - curr_v);

        //現在の値との内分を取って次のノードへ
        value = LAMBDA * value + (1.0f - LAMBDA) * curr_v;
    }
}

実験

　について技巧2(深さ制限5, 定跡オフ)と1手0.5秒(RTX 2080tiを使用)で300局対局を行った。

	勝率	相対Eloレート
1	52.0%	+13.9
0.9	56.7%	+46.6
0.75	54.3%	+30.2

　あまりはっきりとした差は出なかった。元論文では探索回数が少ない場合により顕著な差が出るとのことだったので、追加で技巧2(深さ制限4, 定跡オフ)と1手0.25秒(RTX 2080tiを使用)で500局対局を行った。

	勝率	相対Eloレート
1	53.9%	+27.9
0.9	56.0%	+41.6
0.75	50.2%	+1.4

　むしろ差が縮まった。プレイアウトの有無など元論文とは異なる点もあるため同じようにはいかないのかもしれない。

AtCoder Grand Contest 034

結果

　A,Bの2完でレート+1。C問題を解けないようでは厳しい。

A問題

　のうち右にある方を先に移動させたいという気持ちから考えていって方針は早い段階で立ったのだが、実装で悩んでしまった。最終的には多少冗長でも1マスずつ見ていくようにループを書くのが見通しが良かった。こういうのをもっと短い時間ですっきり実装できるようになりたい。

#include"bits/stdc++.h"
using namespace std;
using ll = int64_t;

int main() {
    ll N, A, B, C, D;
    string S;
    cin >> N >> A >> B >> C >> D >> S;
    A--; B--; C--; D--;

    if (C < D) {
        //普通にBから移動
        bool ok_B = true;
        for (ll i = B + 1; i < D; i++) {
            if (S[i] == '#' && S[i + 1] == '#') {
                ok_B = false;
                break;
            }
        }

        bool ok_A = true;
        for (ll i = A + 1; i < C; i++) {
            if (S[i] == '#' && S[i + 1] == '#') {
                ok_A = false;
                break;
            }
        }

        cout << (ok_A && ok_B ? "Yes" : "No") << endl;
    } else {
        bool ok_B = false;
        for (ll i = B; i <= D; i++) {
            //左右が空ならOK
            if (S[i - 1] == '.' && S[i] == '.' && S[i + 1] == '.') {
                ok_B = true;
                break;
            }
        }

        bool ok_A = true;
        for (ll i = A + 1; i < C; i++) {
            if (S[i] == '#' && S[i + 1] == '#') {
                ok_A = false;
                break;
            }
        }

        cout << (ok_A && ok_B ? "Yes" : "No") << endl;
    }
}

B問題

　AAA...AAAABCとなっている場合Aが並んでいる数だけ操作できる。AAA...AAAABCBCとなっている場合、2回目のBCにもその前に並んでいるAがそのまま流れ込んでくる。そんな感じで実装する。

#include"bits/stdc++.h"
using namespace std;
using ll = int64_t;

int main() {
    string s;
    cin >> s;
    
    ll ans = 0, A_num = 0;
    for (ll i = 0; i < (ll)s.size() - 1; i++) {
        if (s[i] == 'A') {
            A_num++;
        } else if (A_num > 0 && s[i] == 'B' && s[i + 1] == 'C') {
            ans += A_num;
            i += 1;
        } else {
            A_num = 0;
        }
    }

    cout << ans << endl;
}

C問題

　解説PDFの問題の言い換えはできていたし、二分探索で操作回数を決めて、「個以上個以下の要素を選ぶ数列が高々1つ」なのでll a = mid / X, b = mid % X;という分解ができるのもなんとなく考えていたが詰めきれなかった。個選んだときの利得でソートして上位個を無条件に選び、残り分をpriority_queueに入れて上から取っていくというような実装をしてみたが半分ほどしかACにならなかった。確かによく考えてみると上位個の中に点までの利得が高いものがあり、個以外の中には点までの利得が良くないが点以上の利得がそこそこなものがあるような場合で、後者を点まで選んで前者から点未満まで選ぶ方が良くなるのか。少し気づきにくいところでもある気がするが、解きたい問題ではあった。もう少し時間があれば可能性があったかもしれないし、それはA,B問題をもっと早く解けていればということでもあって、力をつけていくしかない。解説を読めばすぐ通るコードは書けた。本番で解くとしたら落ち着いて計算量を考え直して、判定部分でが許される→探索できそうというように思考が流れれば良いのだろうか。次こそは。

#include"bits/stdc++.h"
using namespace std;
using ll = int64_t;

int main() {
    ll N, X;
    cin >> N >> X;

    struct Test {
        ll b, l, r;
    };
    vector<Test> tests(N);
    for (ll i = 0; i < N; i++) {
        cin >> tests[i].b >> tests[i].l >> tests[i].r;
    }
    sort(tests.begin(), tests.end(), [&](Test& lhs, Test& rhs) {
        ll lv = (X - lhs.b) * lhs.r + lhs.b * lhs.l;
        ll rv = (X - rhs.b) * rhs.r + rhs.b * rhs.l;
        return lv > rv;
    });
    vector<ll> score(N);
    for (ll i = 0; i < N; i++) {
        score[i] = (X - tests[i].b) * tests[i].r + tests[i].b * tests[i].l;
    }
    vector<ll> score_sum(N + 1, 0);
    for (ll i = 0; i < N; i++) {
        score_sum[i + 1] = score_sum[i] + score[i];
    }

    ll default_sum = 0;
    for (ll i = 0; i < N; i++) {
        default_sum -= tests[i].b * tests[i].l;
    }

    ll ok = X * N, ng = -1;
    while (ok != ng + 1) {
        ll mid = (ok + ng) / 2;

        ll a = mid / X;
        ll b = mid % X;

        bool flag = false;
        for (ll i = 0; i < N; i++) {
            ll curr_sum = default_sum;

            //iを除いた上位a個の和
            curr_sum += (i >= a ? score_sum[a] : score_sum[a + 1] - score[i]);

            //iからb個選ぶ
            curr_sum += tests[i].l * min(tests[i].b, b);
            curr_sum += tests[i].r * (b - min(tests[i].b, b));

            if (curr_sum >= 0) {
                flag = true;
                break;
            }
        }

        (flag ? ok = mid : ng = mid);
    }

    cout << ok << endl;
}

M-SOLUTIONS プロコンオープン

結果

　A→B→D→Cと解いて4完。もっと早く解けるべきだとも思うけれど、これくらいが実力だとも感じる。

　直近4回のRatedでは全てレートが上がっていて計+120、Highest更新中。特に訓練しているわけではないので単なる上ブレっぽくはあるが。

A問題

　えー公式なんて覚えてないし難しいかもと思ったけど、なんとか外角の和が360度になることから計算できた。100点のA問題で紙とペンを使うことになるとは。

#include"bits/stdc++.h"
using namespace std;
using ll = int64_t;

int main() {
    ll N;
    cin >> N;
    cout << 180 * N - 360 << endl;
}

B問題

　最初問題文を読み間違えていて15回分の結果が入力されるのかと思っていた。負けの数を数えた方が簡単だったか。

#include"bits/stdc++.h"
using namespace std;
using ll = int64_t;

int main() {
    string S;
    cin >> S;
    ll win = 0;
    for (char c : S) {
        if (c == 'o') {
            win++;
        }
    }
    win += 15 - S.size();

    cout << (win >= 8 ? "YES" : "NO") << endl;
}

C問題

　B問題の後は順番通りこれを解いていたんだけど順位表を見ていると早い段階からD問題がC問題と同じかそれ以上に解かれていたので先にそっち行った。Dを解いた後に戻ってきて1時間くらいかけてなんとかAC。解けたはいいが、未だにこの問題に対する良い思考の組み立て方がよくわからない……。

　解けた際の思考順としては

1. 1回勝敗が付くまで対戦して高橋くんが勝つ確率およびその時のゲーム数の期待値を立式
2. ゲーム数の期待値はにしか依存しないっぽいと気づく
3. 勝敗で終わる確率と、その時の期待ゲーム数を別々に計算して掛け合わせれば良さそう

という感じだった。式をいじり回しているとなんとかなるタイプの問題ではあったか。直前に目にしたぷよぷよについての

30先で30-20になる確率は、50戦30-20の確率とちょっと違う（最後の試合だけ勝敗が確定している）。

— merom686 (@merom686) 2019年5月31日

というツイートに結構助けられた説もある。

　そもそも期待値をこういうふうにMOD取って計算できるのもあまり腑に落ちていないまま適当にやったら通ったという印象。期待値の線形性がうんぬんかんぬんで上手くいくということなんだろうと思っている。以下の解答はコンテスト後書き直したもの。

#include"bits/stdc++.h"
using namespace std;
using ll = int64_t;

constexpr ll MOD = (ll)1e9 + 7;

ll MODpow(ll n, ll m) {
    ll result = 1;
    while (m) {
        if (m % 2 == 1) {
            result *= n;
            result %= MOD;
        }

        m /= 2;
        n *= n;
        n %= MOD;
    }

    return result;
}

class Combination {
public:
    Combination(ll max_num, ll mod) {
        fact_.resize(max_num + 1, 1);
        inv_fact_.resize(max_num + 1, 1);
        mod_ = mod;
        for (ll i = 2; i <= max_num; i++) {
            fact_[i] = i * fact_[i - 1] % mod_;
            inv_fact_[i] = MODpow(fact_[i], mod_ - 2);
            assert(fact_[i] * inv_fact_[i] % mod_ == 1);
        }
    }
    ll operator()(ll n, ll m) const {
        if (m < 0 || m > n) return 0;
        return fact_[n] * inv_fact_[n - m] % mod_ * inv_fact_[m] % mod_;
    }
private:
    vector<ll> fact_, inv_fact_;
    ll mod_;
};


int main() {
    ll N, A, B, C;
    cin >> N >> A >> B >> C;

    Combination comb(2 * N, MOD);

    //1回どちらかに勝ち負けが付くとしてそれぞれが勝つ確率
    ll probA = A * MODpow(100 - C, MOD - 2) % MOD;
    ll probB = B * MODpow(100 - C, MOD - 2) % MOD;

    //1回勝ち負けが付くまでにかかる期待ゲーム数
    ll one_step = 100 * MODpow(100 - C, MOD - 2) % MOD;

    ll ans = 0;
    for (ll i = 0; i < N; i++) {
        //高橋君がN勝 i敗となる確率
        ll p1 = comb(N - 1 + i, N - 1) * MODpow(probA, N) % MOD * MODpow(probB, i) % MOD;

        //青木君がN勝 i敗となる確率
        ll p2 = comb(N - 1 + i, N - 1) * MODpow(probB, N) % MOD * MODpow(probA, i) % MOD;

        //N + i回の勝ち負けで終わる確率
        ll p = (p1 + p2) % MOD;

        //N + i回勝ち負けが付く場合の期待ゲーム数
        ll exp_game_num = one_step * (N + i) % MOD;

        //答えに足す
        (ans += p * exp_game_num % MOD) %= MOD;
    }

    cout << ans << endl;
}

D問題

　解いている人が多いのでそれほどひねった解法ではないんだろうと思って望んだ。気持ちとして次数が一番大きいノードに一番大きい数を割り当てて、隣接ノードに二番目以降のものを割り当てるということしたくなる。それを実装する。通る。

　解説PDFを見るともっと単純にできたようだ。自分のコードもよく見てみればそういうことになっている(st.empty()が真になるのは最初だけ)のでひどい。考察が甘いから実装が大変になって時間がかかってしまう。

#include"bits/stdc++.h"
using namespace std;
using ll = int64_t;

int main() {
    ll N;
    cin >> N;
    vector<vector<ll>> connect(N);
    for (ll i = 0; i < N - 1; i++) {
        ll a, b;
        cin >> a >> b;
        a--; b--;
        connect[a].push_back(b);
        connect[b].push_back(a);
    }
    vector<ll> c(N);
    for (ll i = 0; i < N; i++) {
        cin >> c[i];
    }
    sort(c.begin(), c.end(), greater<>());

    struct Node {
        ll node, num;
        bool operator<(const Node& rhs) const {
            return num < rhs.num;
        }
    };

    priority_queue<Node> pq;
    for (ll i = 0; i < N; i++) {
        pq.push({ i, (ll)connect[i].size() });
    }

    vector<bool> used(N, false);

    ll score = 0;
    vector<ll> ans(N);

    stack<ll> st;
    for (ll i = 0; i < N; i++) {
        if (st.empty()) {
            while (true) {
                auto t = pq.top();
                pq.pop();

                if (used[t.node]) {
                    continue;
                }
                used[t.node] = true;

                ans[t.node] = c[i];

                for (auto next : connect[t.node]) {
                    st.push(next);
                }

                break;
            }
        } else {
            while (true) {
                auto t = st.top();
                st.pop();

                if (used[t]) {
                    continue;
                }
                used[t] = true;
                for (auto next : connect[t]) {
                    st.push(next);
                }

                ans[t] = c[i];
                score += c[i];
                break;
            }
        }
    }

    cout << score << endl;
    for (ll i = 0; i < N; i++) {
        cout << ans[i] << " \n"[i == N - 1];
    }
}

E問題

　コンテスト中はほとんど読んでもいなかった。今解いてみたがわからず解説を見てAC。解説の方針でも割り算のところとかこれで上手くいくものかパッとは自信持って断言できないし、例外処理も難しくて何度もしくじりWA出した。難しいですね。

#include"bits/stdc++.h"
using namespace std;
using ll = int64_t;

constexpr ll MOD = (ll)1e6 + 3;

ll MODpow(ll n, ll m) {
    ll result = 1;
    while (m) {
        if (m % 2 == 1) {
            result *= n;
            result %= MOD;
        }

        m /= 2;
        n *= n;
        n %= MOD;
    }

    return result;
}

int main() {
    ll Q;
    cin >> Q;
    vector<ll> x(Q), d(Q), n(Q);
    for (ll i = 0; i < Q; i++) {
        cin >> x[i] >> d[i] >> n[i];
    }

    constexpr ll max_num = 1e6 + 2;
    vector<ll> fact, inv_fact;
    fact.resize(max_num + 1, 1);
    inv_fact.resize(max_num + 1, 1);
    for (ll i = 2; i <= max_num; i++) {
        fact[i] = i * fact[i - 1] % MOD;
        inv_fact[i] = MODpow(fact[i], MOD - 2);
        assert(fact[i] * inv_fact[i] % MOD == 1);
    }

    for (ll i = 0; i < Q; i++) {
        if (d[i] == 0) {
            cout << MODpow(x[i], n[i]) << endl;
        } else {
            ll x_var_d = x[i] * MODpow(d[i], MOD - 2) % MOD;
            if (x_var_d == 0 || x_var_d + n[i] - 1 >= MOD) {
                cout << 0 << endl;
            } else {
                ll a = x_var_d + n[i] - 1;
                ll b = x_var_d - 1;
                cout << MODpow(d[i], n[i]) * fact[a] % MOD * inv_fact[b] % MOD << endl;
            }
        }
    }
}

a crowd of rebellionの好きな曲

　音楽について語れるような知識もないのでYoutubeから好きな曲を貼っていくだけの記事です。動画を貼っておきながらあれなんですけど、なんとなく楽曲のイメージを固定化したくないのでMVは一切見ていません。アーティストの顔写真とかもできれば見たくないなぁと気をつけているところもあるので。ライブとかも一切行ったことないし、基本的にApple Musicにあるものしか聴かないという感じの浅い聴き方をしている人間の適当な記事です。

　というわけでa crowd of rebellionの話。個人的にここ1年くらいで一番聴いている時間が長いバンドだと思います。今までこういうジャンル(デスボイスが入るタイプのやつ)はあんまり聴いていなかったんですけどなんかハマってしまいましたね。もとから声高めの男性ボーカルが好きなところはあるのでそこまで違和感のあるハマり方でもないといえばそうなんですが。

　a crowd of rebellionで最初に聴いたアルバムが『Ill』で、曲としてもこれが印象深いです。この曲に限らず歌詞をちゃんと読んだことはないんですが、2番のサビあたりの語感は素敵だと思います。あとは「Break」のところとかも。

　普段はアルバムの楽曲を順番通りそのまま流すことが多く、続けてよく聴く『Sign.』も好きです。当然サビも良いんですけど、そこへの入り「ひとつふたつ」のあたりが好みですかね。

　『Ill』は序盤のこの2曲でテンションが上がりますね。終盤の『Noah』、『THE TESTAMENT』も好きで、特に後者がお気に入りです。歌いだしからして好きなんですが、2番サビの「ねぇ神よ僕を縛ってまで」の歌い方がもろにストライクゾーンといった感じです。

　他のアルバムだと『Gingerol』、『Xanthium』をよく聴きます。というか『Ill』を含めたこの3枚しかほとんど聴いてなくて、それ以前のものはまた少し毛色が違って少し上級者向け？ みたいな印象があります。

　曲としてはそれぞれアルバムの最初と最後に好きなものが多い気がします。アルバムってそういう曲の置き方をするのが一般的だったりするんでしょうか。何か作業しながら聴くことが多い関係で中盤はあまり意識できていないだけという可能性もありそうです。改めてアルバム中盤あたりの曲名を見渡してみても、まだ頭の中で曲名と曲の内容を結び付けられてないものがいくらかあるような……。

　『Gingerol』だと2,3曲目の『HOPE』『Nex:us』、11,12曲目の『リビルド』『karma_葬』が明確に好きと言えるところで、ここでは代表して『Nex:us』を。やはりこの手の曲が好きという傾向があるとは思うんですけどこういうのをなんていうのかよく知りません。

　『Xanthium』だと1曲目『M1917』、12曲目『The Crow』が好きですね。『M1917』の動画は再生数が一番多いということで、一般的にも人気ということなんでしょうか。銃の効果音が一瞬ダサく聴こえる気もするけど強引にいやこれはかっこいいんだと納得させられる感じもあります。「両手結って祈ったって」の部分がフレーズとして好みです。

　音楽に対する語彙・表現力はどのようにしたら蓄えられるのでしょうね。いずれより明瞭な形で言及できればなぁと思いつつ、とりあえず現時点での感想として以上の内容を残しておきたいと思います。

SENetの導入

要約

　SENetの構造を導入することによってネットワークの性能が向上した。計算量はやや多くなるが、全体として棋力は向上した。

背景

　山岡さんのブログで将棋ソフトでもSENetの構造が有用であるとの実験結果が示されていた。

　このような簡単な変更かつ僅かな計算量の増加で精度が高くなるなら導入しない手はない。

実装

　実際のコードは

にある通りだが、主要な部分を抜粋する。多少改編も加えている。

　モデルのクラス変数に各ブロックで用いる全結合層を追加。

std::vector<std::vector<torch::nn::Linear>> fc(BLOCK_NUM, std::vector<torch::nn::Linear>(2, nullptr));
for (int32_t i = 0; i < BLOCK_NUM; i++) {
    fc[i][0] = register_module("fc" + std::to_string(i) + "_0",
 torch::nn::Linear(torch::nn::LinearOptions(CHANNEL_NUM, CHANNEL_NUM / REDUCTION).with_bias(false)));
    fc[i][1] = register_module("fc" + std::to_string(i) + "_1",
 torch::nn::Linear(torch::nn::LinearOptions(CHANNEL_NUM / REDUCTION, CHANNEL_NUM).with_bias(false)));
}

　ブロックでの処理において畳み込み2回の後にグローバルアベレージプーリングや全結合層2回の処理を追加。

for (int32_t i = 0; i < BLOCK_NUM; i++) {
    auto t = x;

    x = conv[i][0]->forward(x);
    x = bn[i][0]->forward(x);
    x = torch::relu(x);

    x = conv[i][1]->forward(x);
    x = bn[i][1]->forward(x);

    auto y = torch::avg_pool2d(x, {9, 9});
    y = y.view({-1, CHANNEL_NUM});
    y = fc[i][0]->forward(y);
    y = torch::relu(y);
    y = fc[i][1]->forward(y);
    y = torch::sigmoid(y);
    y = y.view({-1, CHANNEL_NUM, 1, 1});
    x = x * y;

    x = torch::relu(x + t);
}

実験

学習

　floodgateの2015~2018年の棋譜からR2800以上同士の対局を抽出して約1千万局面を教師データとした教師あり学習を行った。Policyの教師は棋譜で指された指し手、Valueの教師は棋譜の最終結果による-1 or 1である。

　上記実装においてREDUCTION = 8とした。これはもともとCNNのチャネル数が64と小さいため16で割るのは過剰ではないかと考えたためである。

　全結合層についてバイアスあり・なしの2通りを実験した。ベースラインとしてSENet構造を入れてないものと比較した。検証損失の推移を以下に示す。

左:Policy損失　右:Value損失

　どれも38エポックを経過した段階で最も損失和が低くなっており、その時点での値を以下に示す。

モデル	Policy損失	Value損失	学習時間の比
baseline	1.732598	0.409436	1
SENet	1.707092	0.402247	1.138
SENet with bias	1.710603	0.400820	1.149

　バイアスあり・なしのいずれにおいてもベースラインより低い損失となった。ベースラインのモデルが10ブロック・64チャネルという比較的小さなネットワークのためか、SENet構造を入れることによる学習時間の増加は13%~14%と大きめになっている。学習に比べて対局時にはネットワーク以外の処理も含まれるためNPSの低下はこれよりも小さいはずであり、影響は少ないと思われる。

検証対局

　それぞれのモデルを用いて技巧2(深さ1)と1手1秒で200局対局を行った。

モデル	技巧2に対する勝率	Eloレート差
baseline	48.0%	-13.9
SENet	74.8%	+188.5
SENet with bias	65.8%	+113.3

　SENet構造を導入することで探索速度の低下を補ってあまりある程の棋力向上が見られた。全結合層のバイアスはないものの方が高い勝率となったが、ここまで大きな差がつくのは損失の違いがわずかであったことからすると意外な結果である。偶然の影響が大きそうな気はするが、勝率だけでなく損失も悪くないためとりあえずバイアスなしのSENetで強化学習を試してみることとする。結果はいずれにここに追記する。

　以下2019/06/02追記

強化学習

　バイアスなしのSENetを用いてAlphaZero方式の強化学習を試した。

左:Policy損失　右:Value損失

　検証損失はベースラインよりも低い値となった。また技巧2(深さ5)と1手1秒で300局対局させた結果も

モデル	技巧2に対する勝率	Eloレート差
baseline	56.0%	+41.9
SENet	72.0%	+164.1

となりやや性能が上がった。

C_PUCTの調整

要約

　は2.5としたとき一番性能が良かった。

背景

　今までMiacisは探索の選択ステップにおいてScience版AlphaZeroと同様の係数を用いていた。

$$ a_t = \mathrm{argmax}_a \left( Q(s_t, a) + C(s) P(s, a) \frac{\sqrt{N(s)}}{1 + N(s, a)} \right) $$

$$ C(s) = \log\left(\frac{1 + N(s) + c_{base}}{c_{base}}\right) + c_{init} $$

　しかし実際にはの代わりに違う値を用いているのもあり、係数も調整し直した方が良い可能性がある。

　さらに以前の記事

では、初期局面について探索を行うと探索回数が偏っていることがわかった。根拠のない感覚的な話だが、初期局面におけるPolicy,Valueの値の感じからするともう少し探索回数はバラける方が自然に思えたため、係数を現在の値よりも多少大きい値に変更して実験を行った。

実験

実験設定

　係数を変更してAlphaZeroと同様の強化学習を100kステップ行い、学習した際の値と同じのまま技巧(深さ2)と検証対局を行った。

　係数として次の3通りを試した。

• C_s : AlphaZero(Science版)と同様の式
• C_PUCT=2.5 : AlphaZero(Arxiv版)、AlphaGoZeroと同様にを定数として扱い、その値を2.5としたもの
• C_PUCT=5 : 上に同じで値を5としたもの

実験結果

検証損失

　floodgateの棋譜を用いた検証損失は次のようになった。

検証損失 左:Policy損失　右:Value損失

　C_PUCT=2.5と5ではあまり差が見られないが、C_sではPolicyの損失があまり下がっていない。

学習損失

　普段学習損失は重視していないのだが、今回は顕著な差が見られたので学習損失も示す。

学習損失 左:Policy損失　右:Value損失

　C_sにおけるPolicy損失の下がり方が急激過ぎるように見える。また学習損失が下がっている間にはあまり検証損失が下がっておらず、むしろ800kステップあたりで学習損失が上がりつつ検証損失が下がっていることから、良くない指し手に行動が偏ってしまっているのではないかと思われる。

検証対局

　技巧2(深さ2)と1手1秒で300局対局を行った結果は次のようになった。

係数	勝率	Eloレート差
C_s	51.2%	+8.3
C_PUCT=2.5	64.5%	+103.7
C_PUCT=5	56.7%	+46.6

　C_PUCT=2.5が一番勝率が高かった。C_sと比べてEloレートに換算すると約+100ほどの伸びとなっている。

　初期局面の分布を見ると

係数	▲２六歩(Policy)	▲７六歩(Policy)	▲２六歩(探索後)	▲７六歩(探索後)
C_PUCT=2.5	45.2%	48.9%	66.7%	32.9%
C_PUCT=5	47.7%	38.9%	59.1%	25.4%

となっており、ほぼ▲２六歩と▲７六歩で確率の大部分を占める形になっていた。バラけさせる効果が有効に働いていたかどうかはわからず、C_sとの性能差は上手く▲２六歩と▲７六歩を見つけられるかという偶然性による可能性もある。強化学習なのでそれぞれ1回の試行で結論付けるのも怖いところではあるが、一応今後はC_PUCT=2.5でやっていこうと思う。

AtCoder Beginner Contest 128

結果

　E問題までの5完。思ったよりレートが伸びて1級になった。

A問題

　足す部分を分けてしまったが別に1行で済むなぁと思いながら直すのも面倒だったので。

#include"bits/stdc++.h"
using namespace std;
using ll = int64_t;

int main() {
    ll A, P;
    cin >> A >> P;
    P += 3 * A;
    cout << P / 2 << endl;
}

B問題

　restaurantの綴りに自信がなくて型の名前がRになった。構造体を作ってソートするやつって上手いことスニペットにできたりするんだろうか。

#include"bits/stdc++.h"
using namespace std;
using ll = int64_t;

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

    struct R {
        ll P, index;
        string S;
    };
    vector<R> rs(N);
    for (ll i = 0; i < N; i++) {
        cin >> rs[i].S >> rs[i].P;
        rs[i].index = i + 1;
    }

    sort(rs.begin(), rs.end(), [](R& lhs, R& rhs) {
        return lhs.S != rhs.S ? lhs.S < rhs.S : lhs.P > rhs.P;
    });

    for (const R& r : rs) {
        cout << r.index << endl;
    }
}

C問題

　ネストが深くなって脳が混乱した。計算量もちゃんとは考えてないけどC問題ならこれで通るだろうというメタ読みをするなど。

#include"bits/stdc++.h"
using namespace std;
using ll = int64_t;

int main() {
    ll N, M;
    cin >> N >> M;
    vector<ll> k(M), p(M);
    vector<vector<ll>> s(M);
    for (ll i = 0; i < M; i++) {
        cin >> k[i];
        for (ll j = 0; j < k[i]; j++) {
            ll t;
            cin >> t;
            s[i].push_back(t - 1);
        }
    }
    for (ll i = 0; i < M; i++) {
        cin >> p[i];
    }

    ll ans = 0;
    for (ll i = 0; i < (1 << N); i++) {
        bool ok = true;
        for (ll j = 0; j < M; j++) {
            ll num = 0;
            for (ll k : s[j]) {
                if (i & (1 << k)) {
                    num++;
                }
            }
            if (num % 2 != p[j]) {
                ok = false;
                break;
            }
        }

        if (ok) {
            ans++;
        }
    }

    cout << ans << endl;
}

D問題

　ちょっと悩んだけど操作が4種類というのが多いのでいくらか不要になりそうということを考えてみると手持ちのものを詰めていくのは最後にまとめて捨てるのと同義になるし、そうなると左右からどれだけ取るかの全探索で終わり。もう少し上手い実装はありそう。かなり力技っぽい書き方になってしまった。最後マイナスの要素を捨てていくところでこんなにif文まみれにしてしまうなんて。

#include"bits/stdc++.h"
using namespace std;
using ll = int64_t;

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

    ll ans = 0;
    for (ll i = 0; i <= K; i++) {
        for (ll j = 0; j <= K - i; j++) {
            vector<ll> copy = V;
            vector<ll> picked;
            for (ll k = 0; k < i; k++) {
                if (copy.empty()) {
                    break;
                }
                picked.push_back(copy.front());
                copy.erase(copy.begin());
            }
            for (ll k = 0; k < j; k++) {
                if (copy.empty()) {
                    break;
                }
                picked.push_back(copy.back());
                copy.pop_back();
            }

            sort(picked.begin(), picked.end());
            ll tmp = 0;
            ll rem = K - i - j;
            for (ll e : picked) {
                if (e >= 0) {
                    tmp += e;
                } else {
                    if (rem > 0) {
                        rem--;
                    } else {
                        tmp += e;
                    }
                }
            }

            ans = max(ans, tmp);
        }
    }

    cout << ans << endl;
}

E問題

　最初は遅延セグメント木に投げればなんとかなったりしないかと手を抜きたい思考が出ていたけど、ちゃんと考えて解説PDFそのままな感じの思考過程でなんとかなった。

　本番では不要な部分が多い汚いコードを書いてしまったので書き直し（元)。最初は工事だけでソートできなきゃいけないんじゃないかとかいろいろ迷走していたので無用な構造体ばかりになっていた。setも値を引数にとっての削除ができるんだからpriority_queueとmapを使って管理するなんてことをしなくて良かったんだった。種々の制約のおかげでかなり書きやすいし解いてて楽しい問題。

#include"bits/stdc++.h"
using namespace std;
using ll = int64_t;

int main() {
    ll N, Q;
    cin >> N >> Q;

    enum Type {
        STOP_END, STOP_START, WALK_START
    };
    struct Query {
        Type type;
        ll time, pos;
        bool operator<(const Query& rhs) const {
            return (time != rhs.time ? time > rhs.time : type > rhs.type);
        }
    };
    priority_queue<Query> pq;

    for (ll i = 0; i < N; i++) {
        ll S, T, X;
        cin >> S >> T >> X;
        pq.push({ STOP_START, S - X, X });
        pq.push({ STOP_END,   T - X, X });
    }

    for (ll i = 0; i < Q; i++) {
        ll D;
        cin >> D;
        pq.push({ WALK_START, D, -1 });
    }

    set<ll> st;
    while (!pq.empty()) {
        auto top = pq.top();
        pq.pop();

        if (top.type == STOP_START) {
            st.insert(top.pos);
        } else if (top.type == STOP_END) {
            st.erase(top.pos);
        } else {
            cout << (st.empty() ? -1 : *st.begin()) << endl;
        }
    }
}

F問題

　45分くらい残った状態で入れたのでなんとか通したかったが、ダメだった。中央から見て対称な位置を踏むような経路は取れそうとは思っていたけど詰めきれなかった。解説を読んでもよくわからず、他の人のコードを読んでなんとか通るコードは書いたがまた微妙に理解が怪しい。r < Cだったらbreakという処理を入れないとが負の場合を考慮してしまうあたりを今ようやくわかり始めてきた。

　下の実装、実は回のループ内でvector<bool> (N, false)を初期化しているんだけど108msで普通に通る。こういうものの初期化なら問題ないのか。上手くやるには訪問かどうかのフラグvector<ll> (N)を使ってを書き込んでいき、いま訪問したものがと一致していないかどうかを判定すれば良いようだ。

#include"bits/stdc++.h"
using namespace std;
using ll = int64_t;

int main() {
    ll N;
    cin >> N;
    vector<ll> S(N);
    for (ll i = 0; i < N; i++) {
        cin >> S[i];
    }

    auto isOK = [N](ll x) {
        return 0 <= x && x < N;
    };

    ll ans = 0;
    for (ll C = 1; C < N; C++) {
        vector<bool> visit(N, false);
        ll l = 0, r = N - 1;
        ll score = 0;
        while (true) {
            l += C;
            r -= C;
            if (!isOK(l) || !isOK(r) || visit[l] || visit[r] || l == r || r < C) {
                break;
            }
            visit[l] = visit[r] = true;
            score += S[l] + S[r];
            ans = max(ans, score);
        }
    }

    cout << ans << endl;
}

AtCoder Beginner Contest 127

結果

　E問題までの5完で311位。パフォーマンスは1832でレート変動は1752→1760(+8)だった。E問題を解けてそこそこかなと思ったけど、パフォーマンスは思ったより低かった。慣れている人にとってはFが簡単だったらしいという影響もあったのかもしれない。

A問題

　普通にif文で分岐。coutを並べるのがダサく思えるお年頃なので三項演算子を使いたくなってしまうが、3つ以上に分かれるときは混乱しがちなのでこれでいいと思う。

#include"bits/stdc++.h"
using namespace std;
using ll = int64_t;

int main() {
    ll A, B;
    cin >> A >> B;
    if (A <= 5) {
        cout << 0 << endl;
    } else if (A <= 12) {
        cout << B / 2 << endl;
    } else {
        cout << B << endl;
    }
}

B問題

　語ることなし。

#include"bits/stdc++.h"
using namespace std;
using ll = int64_t;

int main() {
    ll r, D, x;
    cin >> r >> D >> x;
    for (ll i = 1; i <= 10; i++) {
        x = r * x - D;
        cout << x << endl;
    }
}

C問題

　パッと見で「左端の最大値と右端の最小値だけ考えれば良い」と判断したけど確信が持てなくて理屈を考えているうちに少し時間がたって、WA出てから考えようということで証明しきれないまま提出。負になる場合にそのまま出力してしまっていたので1WA。すぐ気づいて修正できたけど、ジャッジが詰まっていたりしたらちょっとまずかったかも。

#include"bits/stdc++.h"
using namespace std;
using ll = int64_t;

int main() {
    ll N, M;
    cin >> N >> M;
    vector<ll> L(M), R(M);
    for (ll i = 0; i < M; i++) {
        cin >> L[i] >> R[i];
    }

    ll ans = *min_element(R.begin(), R.end()) - *max_element(L.begin(), L.end()) + 1;
    cout << max(ans, (ll)0) << endl;
}

D問題

　とりあえず問題文を読んだ段階で順番は関係なさそうと思ったので配列も操作列もソートして、あとは小さい方から貪欲に処理していって良さそうという感覚を信じて出して通った。std::pairの使用をすぐ避けてしまう。

#include"bits/stdc++.h"
using namespace std;
using ll = int64_t;

int main() {
    ll N, M;
    cin >> N >> M;
    vector<ll> A(N);
    for (ll i = 0; i < N; i++) {
        cin >> A[i];
    }

    struct Op {
        ll B, C;
    };
    vector<Op> ops(M);
    for (ll i = 0; i < M; i++) {
        cin >> ops[i].B >> ops[i].C;
    }

    sort(A.begin(), A.end());
    sort(ops.begin(), ops.end(), [](Op& lhs, Op& rhs) {
        return lhs.C > rhs.C;
    });

    ll index = 0;
    for (const Op& op : ops) {
        for (ll i = 0; i < op.B; i++) {
            if (A[index] < op.C) {
                A[index++] = op.C;
            } else {
                break;
            }
        }
    }

    cout << accumulate(A.begin(), A.end(), (ll)0) << endl;
}

E問題

　制約を完全にと勘違いしていた。それだとの\という制約もとんでもないことになるんだけど、そこも見間違えていてで解く問題だと思い込んで解いていた。

　まず2駒の配置だけを考えて最終的にそれを倍すれば良いということにはすぐ気づく。なので2駒の配置についてのコストの和をで求める問題だと思った。しかしこれが結構難しい。

　2駒について片方の駒を固定してもう片方の駒を自由に動かすと、固定している方の上下左右について「「公差1の等差数列の和」を公差とする等差数列の和」を考えれば式が立つ(合ってるかは知らない)。

　つまり片方を固定した場合についてはで求まることはわかったが、固定するマスの位置を全探索するとなので制約の勘違いによりダメだと思い込んでいた。

　なんとかして計算量を落とすフェーズに入る。理屈から言えば上の式を展開してなんやかんや公式をぶちこめば総和自体もで求められそうだが上の式を展開するのは地獄なのでやりたくない。こういう場合はたいてい差分計算すればなんとかなると信じて、固定マスを列方向に1ずらしたときを考えていく。

すると直前までいた列までの数字は全て+1になって、それより右は全て-1になることに気づく。つまり今列目にいるとするとが差分になる。差分がに関する1次式になっているので、回ずらしたときの値はに関する2次式になる。それの総和を求めることは二乗の総和を計算する公式をググってで計算可能。

　結局一番下の式(が抜けていてを足す数が1回少ないので正確には)を計算すればよい。駒が左端にいるときの初期値だけは頑張ってで求めれば、それを右にずらしていった結果もこの式でで求まるので、後は初期位置を各行についてで考えれば良い。

　2駒について各位置関係を2回足しているので2で割って、あとは倍して、ようやく答え。結構難しいと思ったんだけど、ただの制約見間違えだったとは……。

#include"bits/stdc++.h"
using namespace std;
using ll = int64_t;

constexpr ll MOD = 1e9 + 7;

ll MODpow(ll n, ll m) {
    ll result = 1;
    while (m) {
        if (m % 2 == 1) {
            result *= n;
            result %= MOD;
        }

        m /= 2;
        n *= n;
        n %= MOD;
    }

    return result;
}

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

    ll ans = 0;
    for (ll i = 0; i < N; i++) {
        ll tmp = 0;
        ll x = 0;
        (x += i * (i + 1) / 2 % MOD) %= MOD;
        (x += (N - i - 1) * (N - i) / 2 % MOD) % MOD;
        ll sum = M * (M - 1) / 2 % MOD;
        ll sum_u = ((sum + M - 1) + (sum + i * (M - 1))) * i / 2 % MOD;
        ll sum_d = (sum + (sum + (N - i - 1) * (M - 1))) * (N - i) / 2 % MOD;
        (x += sum_u) %= MOD;
        (x += sum_d) %= MOD;

        (tmp += M * x % MOD) %= MOD;

        ll pow2 = (M - 1) * M * (2 * M - 1) / 6 % MOD;
        (tmp += N * pow2 % MOD) %= MOD;

        ll sub = (M - 1) * (M - 1) * M / 2 % MOD * N % MOD;
        tmp = (tmp + MOD - sub) % MOD;

        (ans += tmp) %= MOD;
    }
    (ans *= MODpow(2, MOD - 2)) %= MOD;

    for (ll i = 0; i < K - 2; i++) {
        (ans *= N * M - 2 - i) %= MOD;
    }
    for (ll i = 1; i <= K - 2; i++) {
        (ans *= MODpow(i, MOD - 2)) %= MOD;
    }

    cout << ans << endl;
}

F問題

　本番中はE問題で時間と体力を奪われたのもあってあまりまともに考察できなかった。中央値を見ればよいというのにも気づいていなかったし、中央値はpriority_queue2本で管理できるという話も知らなかった。解説PDFを読んで、確かにそんな感じで解けそうということで適当に書いて通した。AtCoderしかやってないとこういう典型？ があんまり身についていない説がある？ よくわからないけどこういう問題が出てくれるならそれはそれで楽しい。

#include"bits/stdc++.h"
using namespace std;
using ll = int64_t;

int main() {
    ll Q;
    cin >> Q;
    
    priority_queue<ll> left_pq;
    priority_queue<ll, vector<ll>, greater<>> right_pq;
    left_pq.push(LLONG_MIN);
    right_pq.push(LLONG_MAX);

    ll sum_b = 0;
    ll min_v = 0;

    for (ll i = 0; i < Q; i++) {
        ll op;
        cin >> op;
        if (op == 1) {
            ll a, b;
            cin >> a >> b;
            sum_b += b;

            if (left_pq.size() == right_pq.size()) {
                if (a < left_pq.top()) {
                    min_v += left_pq.top() - a;
                }
                if (a > right_pq.top()) {
                    min_v += a - right_pq.top();
                }
            } else {
                min_v += abs(left_pq.top() - a);
            }

            if (a >= right_pq.top()) {
                right_pq.push(a);
            } else {
                left_pq.push(a);
            }

            if (right_pq.size() > left_pq.size()) {
                left_pq.push(right_pq.top());
                right_pq.pop();
            } else if (left_pq.size() > right_pq.size() + 1) {
                right_pq.push(left_pq.top());
                left_pq.pop();
            }
        } else {
            cout << left_pq.top() << " " << min_v + sum_b << endl;
        }
    }
}