AtCoder Grand Contest 031

結果

 A,B問題を解いて634位。パフォーマンスは1708でレート変化は1796→1787(-9)だった。C問題を通せるようになるにはもう少し成長が必要そう。

A問題

 3分4秒でAC。ある文字がn回出てきたらそれらのうちどれかから1回取るか全く取らないかでn + 1通りありえるんだなというのがすぐ見通せてそんなに時間はかからなかった。とりあえず200早解きができれば大失敗ということはないかなと少し安心した。

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

int main() {
    ll N;
    string S;
    constexpr ll MOD = 1e9 + 7;
    cin >> N >> S;
    vector<ll> num(26, 1);
    for (char c : S) {
        num[c - 'a']++;
    }
    ll ans = 1;
    for (ll i = 0; i < 26; i++) {
        (ans *= num[i]) %= MOD;
    }

    cout << (ans + MOD - 1) % MOD << endl;
}

B問題

コンテスト中の思考

 問題文を読んで、700点問題だし簡単ではないんだろうけどたっぷり時間があれば解けそうという印象を持つ。

 まず最初は同じ色が連続していればそこはまとめて1個にしてしまっても同じということを考える。配列の長さが変わると厄介なのでこれが便利な性質かどうかは微妙そう。終わりの状態から逆の操作を考えれば見通しよくなったりしないかと試してみたがあまり上手くいかない。

 ここでちゃんと入力例2,3についてどの5通りがあるのか列挙してみる。やっていると、ある色で挟まれている区間が重なっていないならそれらは独立に色を変えるか変えないかの2通りが選べそうだと気づく。問題なのは重なっていたり、入れ子になっている場合で、これを処理できればなんとかなりそう。

 結局ある色2個のペアについて操作を行う/行わないの2通りを考えていけば良さそう。いかにもDPっぽいと思い、左端から考えていくと、操作を行う場合は右端の次から独立にまた考え始めれば良く、操作を行わない場合は左端の次からまた考え始めれば良いとなって、あれこんなに簡単なのかと怪しみながら実装へ移った。ちゃんと定式化すると

dp_i := i番目以降で可能な色の列の数

として、i番目と同じ色ものが次にあるのはj番目だった場合

dp_i = dp_{j} + dp_{i + 1}

となるということ。第一項が操作を行う場合で、第二項が行わない場合。これ以降同じ色がなかった場合は操作を行えない第二項だけで計算する。

 こういう先の値を今の値の計算に使うという気持ちだったので実装はメモ化再帰に。同じ色が連続した場合とかで何度かバグらせつつなんとかAC。returnのところでメモに代入し忘れていて1TLE出したのはもったいなかった。

反省

 そこそこ速く処理できたと思ったわりに約50分かかっているのでもう少し速く解ければ。入力例を手で解きにいくのが遅すぎるので、一番最初にやってしまうくらいで良いと思う。

 解説を読むと少し方針が違っていた。色が切り替わる境界はもともとの配列と同じ色じゃないといけないというのはさっぱり気づいていなかった。forループのDPとメモ化再帰は見る順番が逆になるイメージで、どちらかというとメモ化再帰的な見方の方が感覚に合うんだけど「DPに帰着できました解けます」みたいな安心感はないかもしれないなぁと思ったりもする。どっちもできるようになるべきだが。

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

constexpr ll MOD = 1e9 + 7;
vector<ll> pos[200001];
ll N;
vector<ll> C;
vector<ll> memo;

ll solve(ll left) {
    if (left >= N) {
        return 1;
    }

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

    ll next = *upper_bound(pos[C[left]].begin(), pos[C[left]].end(), left);

    ll ans;

    if (next == left + 1) {
        ans = solve(next);
    } else if (next >= N) {
        ans = solve(left + 1);
    } else {
        ans = (solve(next) + solve(left + 1)) % MOD;
    }

    return memo[left] = ans;
}

int main() {
    cin >> N;
    C.resize(N);
    memo.resize(N, -1);
    for (ll i = 0; i < N; i++) {
        cin >> C[i];
        pos[C[i]].push_back(i);
    }
    for (ll i = 1; i <= 200000; i++) {
        pos[i].push_back(N);
    }

    cout << solve(0) << endl;
}

C問題

 2時間弱をこの問題に費やしたわけだけどさっぱり解法は見えず。各操作がどこか1つビットが立っている整数とXORを取る操作になるので桁ごとに考えていくのかなという感じで考えていたがダメ。N = 3で全探索したところABも2進数表記でちょうど1桁だけ異なれば大丈夫そうと思ってやってたけど、立っているビットの数の偶奇が問題なのはわからなかった。

 この性質に気づくために何が必要だったかというと、やはりもっと具体例を触ってみるべきだった気がする。N = 3, A = 0, B = 7とかそういうのでもっと操作してみるべきだったか。あとは再帰で書けそうという雰囲気は少しでも嗅ぎ取りたかったか。冪乗系の問題を困難は分割せよ的な方針で解けるようになるとAGCには強くなれそう。

 答えを見る場合、この問題についてはまず解説PDFよりも解説放送を先に見た方がイメージが作りやすかった。そのあと具体的に実装するときに解説PDFを読みなりなんなりしたほうが良さそう。自分はmerom686氏のコンテスト中の提出を参考に実装してAC。思考の道筋をコメントに書いていかないと全然理解できなかった。いやぁこれを本番中に通せるのは天才が過ぎる。すごいなぁ。

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

ll popcount(ll x) {
    ll result = 0;
    for (ll i = 0; i < 64; i++) {
        if (x & (1LL << i)) {
            result++;
        }
    }
    return result;
}

//sとtは下位nビットの中で立っているbitの数の偶奇が異なることを前提
vector<ll> solve(ll s, ll t, ll n) {
    if (n == 1) {
        return { s, t };
    }

    vector<ll> result;

    //最上位ビットを考える
    ll l = (1LL << (n - 1));
    if ((s & l) == (t & l)) {
        //最上位ビットが同じ
        //例)
        //s:1000
        //t:1010
        //このときn-1ビット以下でs→tを考えると,sの次には
        //n-1ビット以下のどこか1箇所がsと異なる
        //ものcが得られる(s→c→...→t)
        //ここでそのcのnビット目を反転したものをc'として
        //sのnビット目を反転したs'との比較を考えると
        //やはりn-1ビット以下のどこか1箇所が異なるので
        //s'→c'という遷移が構築可能である
        //全体として
        //s→s'→...→c'→c→...→t
        //という遷移を考えれば良い
        
        //まずs→tを構築
        auto v1 = solve(s, t, n - 1);
        
        //2番目のものの最上位ビット反転へのパスを構築(c = v1[1])
        auto v2 = solve(s ^ l, v1[1] ^ l, n - 1);
        
        //初手はs
        result.push_back(s);
        
        //s'→c'
        result.insert(result.end(), v2.begin(), v2.end());
        
        //c→t
        result.insert(result.end(), v1.begin() + 1, v1.end());
    } else {
        //最上位ビットが異なる
        //例)
        //s:1000
        //t:0110
        //このとき間に挟むのは最下位ビットを反転した
        //c :1001
        //とこれの最上位ビットを反転したものを
        //c':0001
        //としてs→c→c'→tという遷移を考えれば良い
        ll c = s ^ 1;
        auto v1 = solve(s, c, n - 1);
        auto v2 = solve(c ^ l, t, n - 1);
        result.insert(result.end(), v1.begin(), v1.end());
        result.insert(result.end(), v2.begin(), v2.end());
    }
    return result;
}

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

    if (popcount(A) % 2 == popcount(B) % 2) {
        cout << "NO" << endl;
        return 0;
    }

    cout << "YES" << endl;
    auto ans = solve(A, B, N);
    for (ll i = 0; i < ans.size(); i++) {
        cout << ans[i] << " \n"[i == ans.size() - 1];
    }
}

AtCoder Beginner Contest 121

結果

 25分24秒で全完。148位だった。人々D問題解くの速すぎでしょ。

A問題

 えーA問題でこんなに難しいものを出すのっていう感じの感想を毎回抱いている気がするしA問題を舐めすぎなのか? いやでも今回のはさすがにちょっと難しめでしょ。タイムとしてはいつもより10秒も多くかかってないようなそんな話だけど。

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

int main() {
    ll H, W, h, w;
    cin >> H >> W >> h >> w;
    cout << (H - h) * (W - w) << endl;
}

B問題

 考える要素が一切なくてやるだけ感満載。入力受け取るタイミングで答えも計算みたいなことはあまりやらないようにしていて、冗長でも受け取る時はそれだけやって答えはまた後で計算するという感じ。別にこのレベルの問題ならなにをやっても大丈夫だとは思うけど。

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

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

    ll ans = 0;
    for (ll i = 0; i < N; i++) {
        ll s = C;
        for (ll j = 0; j < M; j++) {
            s += A[i][j] * B[j];
        }

        if (s > 0) {
            ans++;
        }
    }

    cout << ans << endl;
}

C問題

 2要素あるうちの片方でソートすることができますかというC問題でありがちな感じの問題。僕は頭が悪いのでstd::pair<ll, ll>でソート順番を巧妙に使ってどうのこうのするというのが苦手で、構造体を定義して比較関数をラムダで書いてということをやらないと頭が爆発してしまう。いややろうと思えば別にできるだろうけど、悩む時間も含めてどっちが速くACできるのかは微妙なところか。

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

struct Store {
    ll A, B;
};

int main() {
    ll N, M;
    cin >> N >> M;
    vector<Store> stores(N);
    for (ll i = 0; i < N; i++) {
        cin >> stores[i].A >> stores[i].B;
    }
    sort(stores.begin(), stores.end(), [](Store& lhs, Store &rhs) {
        return lhs.A < rhs.A;
    });

    ll ans = 0;
    for (const Store& s : stores) {
        if (M <= s.B) {
            //買い切って終わり
            ans += s.A * M;
            break;
        } else {
            ans += s.A * s.B;
            M -= s.B;
        }
    }

    cout << ans << endl;
}

D問題

 問題文のシンプルさとか順位表での異常な速解き人間の存在とかを見るに有名な話なんだろうけど知らないので自力で。

 排他的論理和は二回同じものかけると元に戻るのでf(A,B) = f(A,B) \oplus f(1, A-1) \oplus f(1, A - 1)だからf(A, B) = f(1, B) \oplus f(1, A - 1)という性質は使うんだろうなと考える。関数gg(x) = f(1, x)として置いて以降はgがわかれば勝ちということに。

 パッとはgの性質はわからないので1から順番に考えていく。あと排他的論理の問題は桁ごとに考えるのがある種の定跡だったというのをこのあたりで思い出したりする。1から15あたりまで2進数に直して眺めてみたところ、2進数で一番右の桁は101010101...となるし、右から2つ目の桁は01100110011...、3つ目の桁は0001111000011110000...となるので法則性が見えてくる。

 まず右からi桁目は2^{i-1} - 1個目までは0が続いてそこから1が2^{i-1}個,0が2^{i-1}個のループが続くのだなぁとちゃんと式を立てて、あとは数えて2で割った余りを見ればその桁が1になるかどうかがわかりますね勝ち。

 焦って考えているので、実装において最初の部分ずらして周期分を考えてあとは余り分を考えてとかなり段階を分けて細かく考えている。そもそも最初に関数g考えればいいんだなという時点でll g(ll x) {}まで書いてからウンウン考え出すし。出す直前で奇麗に書き直すか悩むけど、数秒で順位は変わるのでそのまま出してしまう。WAが出ても「リファクタリングすればなんとかなるかも」という心の余裕ができる点も良い。

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

ll g(ll x) {
    //各桁に着目
    ll ans = 0;
    for (ll i = 0; i < 60; i++) {
        ll d = (1LL << i) - 1;
        ll t = x - d;
        if (t < 0) {
            break;
        }

        ll loop_width = (1LL << (i + 1));
        ll num = t / loop_width * loop_width / 2;
        num += min(t % loop_width, loop_width / 2);
        num %= 2;
        ans |= (num << i);
    }
    return ans;
}

ll f(ll A, ll B) {
    return g(A - 1) ^ g(B);
}

int main() {
    ll A, B;
    cin >> A >> B;
    cout << f(A, B) << endl;
}

自分用 Ubuntu18.04を入れた後やることリスト

  • 時間経過でスリープ状態になるのをオフにする
  • ソフトウェアの更新をする

  • ディレクトリ名を英語にする(参考リンク)

LANG=C xdg-user-dirs-gtk-update
gsettings set org.gnome.desktop.interface clock-show-date true
  • セキュアブートをオフにする(これいるのか?)
sudo mokutil --disable-validation
sudo apt install vim-gnome -y
sudo vim /etc/modprobe.d/blacklist-nouveau.conf

以下の2行を追加

blacklist nouveau
options nouveau modeset=0

sudo update-initramfs -u
  • Nvidia-Driverをインストール
sudo add-apt-repository ppa:graphics-drivers/ppa
sudo apt update
sudo apt install nvidia-driver-410 -y

再起動

sudo gpasswd -a $USER docker

AtCoder Beginner Contest 120

結果

 22分59秒(1WA)で全完。140位だった。WAなければ100位以内という前回と同じパターンか。

A問題

 はい。

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

int main() {
    ll A, B, C;
    cin >> A >> B >> C;
    cout << min(B / A, C) << endl;
}

B問題

 どうあがいても全探索で殴ればいいいつものB問題。最初小さい方から数えてK番目を出力するコードを書いてしまっていた。初期化もmin(A, B)で良いのに無駄にmax(A, B)から探し始めてしまった。

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

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

    ll num = 0;
    for (ll i = max(A, B); ; i--) {
        if (A % i == 0 && B % i == 0) {
            if (++num == K) {
                cout << i << endl;
                return 0;
            }
        }
    }
}

C問題

 最初「赤赤」または「青青」が消せるのかと誤読していた。どちらにしてもスタックに詰みながら貪欲に考えていけばなんかできそうと証明のないままに提出してAC。

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

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

    ll ans = 0;
    stack<char> st;
    for (char c : S) {
        if (st.empty() || st.top() == c) {
            st.push(c);
        } else {
            st.pop();
            ans += 2;
        }
    }

    cout << ans << endl;
}

D問題

 パッと見で後ろから考えるやつだろうなぁと思うし、サイズが求められるUnionFindを使えばそれでいけそうと考える。ライブラリで持ってるUnionFindはサイズが求められないやつだったので少し改良して提出。そこそこWAが出る。同じときは答えを減らしてはいけないんだった。修正して投げてAC。典型感が強い。

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

class UnionFind {
public:
    UnionFind(ll n) {
        par_.resize(n, -1);
    }

    //根を求める
    ll find(ll x) {
        return (par_[x] < 0 ? x : par_[x] = find(par_[x]));
    }

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

    //xが属する集合のサイズを取得
    ll size(ll x) {
        return -par_[find(x)];
    }

    //xとyが同じ集合に属するか否かを判定
    bool same(ll x, ll y) {
        return (find(x) == find(y));
    }
private:
    vector<ll> par_;
};

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

    UnionFind uf(N);
    vector<ll> ans(M);
    ans[M - 1] = N * (N - 1) / 2;
    for (ll i = M - 1; i > 0; i--) {
        if (uf.same(A[i], B[i])) {
            ans[i - 1] = ans[i];
            continue;
        }
        ll size1 = uf.size(A[i]);
        ll size2 = uf.size(B[i]);
        ans[i - 1] = ans[i] - size1 * size2;
        uf.unite(A[i], B[i]);
    }

    for (auto a : ans) {
        cout << a << endl;
    }
}

AtCoder Beginner Contest 119

結果

 38分47秒(1WA)で全完、109位だった。WAを出さなければ100位以内だったが、残念。

A問題

 6文字目と7文字目を見て判定。A問題のわりには一瞬思考が必要。

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

int main() {
    string S;
    cin >> S;
    if (S[5] == '1' || S[6] >= '5') {
        cout << "TBD" << endl;
    } else {
        cout << "Heisei" << endl;
    }
}

B問題

 C++にはlong doubleというものがあるらしいのでそれを使ってみたらフォーマット指定のミスなのかWAが出た。doubleに書き換えたら通った。UnratedなABCでこういうことを試してみるやつ。別にdoubleの精度が悪くて落ちた経験もないけど……。

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

int main() {
    ll N;
    cin >> N;
    double ans = 0.0;
    for (ll i = 0; i < N; i++) {
        double x;
        string u;
        cin >> x >> u;
        if (u == "JPY") {
            ans += x;
        } else {
            ans += x * 380000;
        }
    }

    printf("%.10f\n", ans);
}

C問題

 300点問題のわりには難しかった。賢い方法が思い浮かばず、N \le 8と制約がやけに小さかったので各竹が使用されないかA, B, Cのどれかに使用されるという4つの場合を持つとして全探索してO(4^N)解を実装した。結合のコストを考えていなかったり、使用されないところへ割り当てるときにも結合コストを足してしまったりとバグをたくさん産みながらなんとかAC。うーん、何か良い方法があったかな。

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

bool next(vector<ll>& v) {
    for (ll i = v.size() - 1; i >= 0; i--) {
        if (v[i] != 3) {
            v[i]++;
            for (ll j = i + 1; j < v.size(); j++) {
                v[j] = 0;
            }
            return true;
        }
    }
    return false;
}

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

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

    ll ans = LLONG_MAX;
    vector<ll> use(N, 0);
    do {
        vector<ll> len(4, 0);
        ll tmp = 0;
        for (ll i = 0; i < N; i++) {
            if (use[i] > 0 && len[use[i]]) {
                tmp += 10;
            }
            len[use[i]] += l[i];
        }

        bool empty = false;
        for (ll i = 1; i <= 3; i++) {
            if (len[i] == 0) {
                empty = true;
            }
        }
        if (empty) {
            continue;
        }

        tmp += abs(A - len[1]) + abs(B - len[2]) + abs(C - len[3]);
        ans = min(ans, tmp);
    } while (next(use));

    cout << ans << endl;
}

D問題

 まぁこんなの寺を先に回るルートか神社を先に回るルートかの2通りを考えればいいだけだよねという感じ。2分探索を何度も使うことになって頭が混乱しがちなので最初に全ての寺について最寄りの神社までの距離、全ての神社について最寄りの寺までの距離を計算しておくことで多少は見通し良くなったか。それでもif文が多くてダサいコードを書いてしまったが。三項演算子で奇麗に書くべきでしたね。

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

int main() {
    ll A, B, Q;
    cin >> A >> B >> Q;
    vector<ll> s(A), t(B), x(Q);
    for (ll i = 0; i < A; i++) {
        cin >> s[i];
    }
    for (ll i = 0; i < B; i++) {
        cin >> t[i];
    }
    for (ll i = 0; i < Q; i++) {
        cin >> x[i];
    }

    vector<ll> s_to_min(A), t_to_min(B);
    for (ll i = 0; i < A; i++) {
        ll j = lower_bound(t.begin(), t.end(), s[i]) - t.begin();
        if (j == 0) {
            s_to_min[i] = abs(t[j] - s[i]);
        } else if (j == t.size()) {
            s_to_min[i] = abs(t[j - 1] - s[i]);
        } else {
            s_to_min[i] = min(abs(t[j] - s[i]), abs(t[j - 1] - s[i]));
        }
    }
    for (ll i = 0; i < B; i++) {
        ll j = lower_bound(s.begin(), s.end(), t[i]) - s.begin();
        if (j == 0) {
            t_to_min[i] = abs(s[j] - t[i]);
        } else if (j == s.size()) {
            t_to_min[i] = abs(s[j - 1] - t[i]);
        } else {
            t_to_min[i] = min(abs(s[j] - t[i]), abs(s[j - 1] - t[i]));
        }
    }

    for (ll i = 0; i < Q; i++) {
        ll ans = LLONG_MAX;

        //寺→神社
        ll j = lower_bound(s.begin(), s.end(), x[i]) - s.begin();
        if (j == 0) {
            ans = min(ans, abs(x[i] - s[j]) + s_to_min[j]);
        } else if (j == s.size()) {
            ans = min(ans, abs(x[i] - s[j - 1]) + s_to_min[j - 1]);
        } else {
            ans = min(ans, abs(x[i] - s[j]) + s_to_min[j]);
            ans = min(ans, abs(x[i] - s[j - 1]) + s_to_min[j - 1]);
        }

        //神社→寺
        j = lower_bound(t.begin(), t.end(), x[i]) - t.begin();
        if (j == 0) {
            ans = min(ans, abs(x[i] - t[j]) + t_to_min[j]);
        } else if (j == t.size()) {
            ans = min(ans, abs(x[i] - t[j - 1]) + t_to_min[j - 1]);
        } else {
            ans = min(ans, abs(x[i] - t[j]) + t_to_min[j]);
            ans = min(ans, abs(x[i] - t[j - 1]) + t_to_min[j - 1]);
        }
        cout << ans << endl;
    }
}

AtCoder Beginner Contest 118

結果

 41分50秒(0WA)で全完、82位だった。全部解き切るまで順位表を一切見ていなくて、D問題には結構時間がかかったのでダメかなーと思ったら結構良かった。0WAというのも気持ちいいね。

A問題

 一瞬どっちがどっちの約数かみたいので混乱するなど。if文書き始めたけど結局三項演算子に書き換えるのもあって1分以上かかってしまった。

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

int main() {
    ll A, B;
    cin >> A >> B;
    cout << (B % A == 0 ? A + B : B - A) << endl;
}

B問題

 各食べ物ごとに好きと言っている人の数を数えてNに一致しているものの数をカウントすればいい。200点問題でこういう2重にカウントしなきゃいけないのって難しめでは? これを書いている途中で思い立って調べたけど、こういうときはstd::countなるものを使った方が良さそうだなぁ(参考URL)

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

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

    ll ans = 0;
    for (ll e : d) {
        if (e == N) {
            ans++;
        }
    }

    cout << ans << endl;
}

C問題

 なんか差を取ってるっぽいし勘で最大公約数だろうなという感じ。最大公約数を求めるプログラム自体も勘で書いておっかなびっくり提出してみたら通ってくれた。今はVidual Studioでやっているので使えないんだけど、gccだと確かgcdって組み込みであるんですよね。ちゃんと証明したりコーナーケースを考えたりしていないのでこの問題はWA出てもおかしくなかった。

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

ll gcd(ll a, ll b) {
    return (b == 0 ? a : gcd(b, a % b));
}

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

    ll ans = A[0];
    for (ll i = 1; i < N; i++) {
        ans = gcd(ans, A[i]);
    }
    cout << ans << endl;
}

D問題

 難しかった。前回のABCでもD問題で盛大に詰まった挙句嘘解法で通すなんてことをしてしまったので今回は400点だからと言って舐めずにちゃんと考察するぞという気持ちで立ち向かう。「ちょうどN本」にならないといけないというのが厄介で、なかなか桁を決め打つことができなさそう。前回もDPだったしこれもDPじゃねという発想になる。

 dp_{i, j} := i以上の数字を考えてちょうどj本マッチを使うときの最大値

 を埋めていけばなんとかなりそう。答えは64bit整数で収まらないそうなのでstd::stringで管理。文字列の長さで比較して大きくなれば採用、文字列の長さが同じでも辞書順で大きくなっていれば採用として更新。数字iを一個作るのに必要なマッチ棒がnum_i本だとして、dp_{i, j}の更新は(i + 1, j - num_i)からだけじゃなくて、同じ数字を連続して採用することもできるので(i, j - num_i)からも遷移してこなければならない。このあたりサンプルがきっちり指摘してくれる内容だったので良かった。サンプル弱かったらかなり厳しかったと思う。

 初期化も少し複雑。空文字列でマッチ棒をちょうど1本使うということができないので、空文字列から遷移するときは元がちょうど0本である(j = 0である)という条件分けをしなきゃいけない。こんな場当たり的な場合分けしないといけないの本当か? と疑いつつとりあえず出したら通った。いやー難しい。多分もっとエレガントな実装があると思う。そもそもDPじゃない解法すらありかねないしなぁ。

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

const ll num[] = { 2, 5, 5, 4, 5, 6, 3, 7, 6 };

int main() {
    ll N, M;
    cin >> N >> M;
    vector<bool> can_use(9, false);
    for (ll i = 0; i < M; i++) {
        ll A;
        cin >> A;
        can_use[A - 1] = true;
    }

    vector<vector<string>> dp(10, vector<string>(N + 1));
    for (ll i = 8; i >= 0; i--) {
        for (ll j = 0; j <= N; j++) {
            //追加なし
            if (dp[i + 1][j].size() > dp[i][j].size() || (dp[i + 1][j].size() == dp[i][j].size() && dp[i + 1][j] > dp[i][j])) {
                dp[i][j] = dp[i + 1][j];
            }

            if (!can_use[i] || j - num[i] < 0) {
                continue;
            }

            //一個前から追加
            if (j - num[i] == 0 || dp[i + 1][j - num[i]].size()) {
                string tmp1 = dp[i + 1][j - num[i]] + to_string(i + 1);
                if (tmp1.size() > dp[i][j].size() || (tmp1.size() == dp[i][j].size() && tmp1 > dp[i][j])) {
                    dp[i][j] = tmp1;
                }
            }

            //同じ数字内で追加
            if (j - num[i] == 0 || dp[i][j - num[i]].size()) {
                string tmp2 = dp[i][j - num[i]] + to_string(i + 1);
                if (tmp2.size() > dp[i][j].size() || (tmp2.size() == dp[i][j].size() && tmp2 > dp[i][j])) {
                    dp[i][j] = tmp2;
                }
            }
        }
    }

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

「みんなのプロコン」2019 予選

全体

 A,B,Cの3完で472位。Cをそこそこ早めに解けて一安心し、さあ残った時間でD問題だと感じだったけど歯が立たず。まぁこんなもんですね。

A問題

 100点にしては一瞬考えないといけない問題。というか確信はないままだいたいこんな感じでしょで通した。

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

int main() {
    ll N, K;
    cin >> N >> K;
    cout << (K <= (N + 1) / 2 ? "YES" : "NO") << endl;
}

B問題

 一筆書きできる(準オイラーグラフというらしい)ものは次数が奇数であるものがちょうど2つだったよなぁという性質を思い出してそれを書く。これも完全に証明できてないままとりあえず提出して通ったという感じで、感覚的にはA,Bのどちらかで1WAくらい食らっててもおかしくない。

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

int main() {
    vector<ll> num(4);
    for (ll i = 0; i < 3; i++) {
        ll a, b;
        cin >> a >> b;
        num[a - 1]++;
        num[b - 1]++;
    }

    ll odd = 0;
    for (ll i = 0; i < 4; i++) {
        if (num[i] % 2 == 1) {
            odd++;
        }
    }

    cout << (odd == 2 ? "YES" : "NO") << endl;
}

C問題

 A \lt Bのとき、2回の操作を使ってA枚からB枚に増やせるという話。基本的にはこの交換を繰り返して、最後1回残ったら1枚増やしをする。A \ge Bの場合や最初にA枚まで増やす過程で操作回数がKに達する場合を弾いて、これで大丈夫かなと思ったらサンプル2が合わない。ちょっと考えてそれらで弾かれない場合でも1枚増やしを連打する方が良い場合もあると気づいて、じゃあ連打して得られる 1 + Kと最大の方を答えとすればいいなとしてAC。場合分けをせずこの最大値を取る操作だけで答えを作ろうと悩んでいた時間が無意味だった。場合分けは見落としを生みやすいからあまり入れたくもないが、無理やり消しに行っても良いことはないか。

 解説を読んだらB - A \le 2での場合分けなのか。それはそうだ。頭が悪すぎた。

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

int main() {
    ll K, A, B;
    cin >> K >> A >> B;
    if (A >= B) {
        cout << 1 + K << endl;
        return 0;
    }

    //A枚まで増やす
    if (K <= A - 1) {
        //そこまでで終わってしまう
        cout << 1 + K << endl;
        return 0;
    }

    ll remain = K - (A - 1);
    ll half = remain / 2;
    ll ans = max(1 + K, A + half * (B - A) + (remain % 2));
    cout << ans << endl;
}

D問題

 かなり時間あったのに解けず。このDP見える人間多すぎない? 魔境だなぁ。

 コンテスト中に考えていたこと。まず0をまたぐことはできないから0で分断される各塊について考える。それぞれのコストを計算して、一番小さいところを選んで実行するというイメージ。

 各塊について、基本的には左の1区間から見ていき、その区間を往復して十分回数達したら次の1区間へ移動する。目標回数が奇数ならこれで処理できる。偶数のときは1回余計に多く(あるいは少なく)なるのでコストが1増える。しかし偶数だけで構築されているとまとめて処理することができる。たとえば目標回数が4 4 4だった場合、全部まとめて2往復すればピッタリ達成できる。偶数が連続しているとまとめられる? 奇数が連続していてもまとめられそう。つまり重要なのは偶奇の切り替え回数。

 パターンを考えてみる。O:奇数、E:偶数だとして、偶数同士、奇数同士はまとめるのでOOやEEと連続することはない。まとめた結果長さが2になってOEやEOになるとコスト0で取れる。長さ3だとEOEはコスト0で取れ、OEOにはコスト1かかる。ということを先々までやっていくとなんか法則性があるっぽい? エスパーしたものを書いて出す。半分くらいWA。方針がダメそうなWAの出方だ。考えてみるとEEEをまとめてEにしたとき、コストの増え方は1ではなく3になる。まとめられないじゃん。時間切れ。

 解説を読むと、つまりEOEだけを考えるので良いということか。というか移動の仕方がそうなっていると。目標回数ではなく移動方法に着目してもっと性質を考えないとだめだった。うーん、なるほど。しかしこれをひねり出すのはなかなか難しそうだ。

libtorchをビルドする方法

 libtorchの公開されているバイナリは互換性の維持のため(?)、他のライブラリもリンクしようとするとABIのバージョンがどうたらでエラーになってしまうらしい(どういうことなのだかよくわからない)。実際に手元でやってみてもそうなったため、古いコンパイラを使って開発を行うか、開発で使うコンパイラでlibtorchを自前でビルドするかのどちらかにする必要があるようだ。今回は自前でビルドすることにした。

 結論から言えばlibtorchをビルドするときはpytorchのリポジトリ内にあるtools/build_libtorch.pyを使えば終わり。以下は細かいやったこと。

 環境はdockerを用いて作ることにする。dockerhubにあるpytorchのイメージは使ってみたが、cmakeのバージョンが古かったりどういうディレクトリ構造になっているのかよくわからなかったのでnvidia/cuda:10.0-cudnn7-devel-ubuntu18.04 から導入し始める。

 dockerやnvidia_docker2とかはすでに入っているものとして、コンテナを起動。

docker run --runtime=nvidia -it nvidia/cuda:10.0-cudnn7-devel-ubuntu18.04 bash

 gitやcmake(および導入自体には関係ないが気分としてsudo)を入れる。

apt update
apt install sudo
sudo apt install git -y
sudo apt install cmake -y

 pytorchをgithubからサブモジュールも含めてダウンロードする

git clone --recursive https://github.com/pytorch/pytorch

 ビルド時に使うことになるのでpythonおよびdistutils、pyyamlを入れておく。とりあえずビルドしてみてエラーが出たらメッセージを読んで足りないと言われたものを入れるということを繰り返していけばなんとかなる。

sudo apt install python3
sudo apt install python3-distutils
sudo apt install python3-pip
pip3 install pyyaml

 メインの部分はpytorch/toolsに移動してbuild_libtorch.pyを実行するだけ。本当にただこれだけ。無駄にCMakeLists.txtを覗いて中のフラグどれ立てればいいのか……とか考える必要はなかった。

cd pytorch/tools
python3 build_libtorch.py

 そこそこ時間はかかるがちゃんと複数コア使って並列ビルドをやってくれる。

 使うときはどうもpytorchのディレクトリへのパスを通せば良いっぽい? よくわかっていない。CMakeLitst.txt内で

set(APPEND CMAKE_PREFIX_PATH /path/to/pytorch)
find_package(Torch REQUIRE)

 みたいに書けばなんかコンパイルできた。実行するときにライブラリが見つからないとか言われるのでpytorch/torch/libを.bashrcに書いたり、CLion使っていると特定ユーザーだけでなくシステム全体にパスを通さないといけないようなのでここに書いてあるように/etc/ld.so.confへpytorch/torch/libを追加してsudo ldconfigとすれば良い。

虚構キャラクターに向き合うこと

 先日の記事で、プレイヤーの選択を伴うゲームのうちいくらかは「虚構世界・キャラクターに対して真剣に向き合っているか?」という問いを発するものなのではないかと書いた。つまり我々が現実世界においては行わないようなことを虚構に対しては簡単にしてしまうことは、何かしら虚構を軽んじる態度の現れなのではないかという指摘だ。読者の「所詮虚構だし」といったニヒルな態度を突き崩していくための仕掛けとして用いられることがあると認識している。

 これは確かに重要なテーマであり、物語を単なる虚構と切り捨てていった先に大きな感動があるとは思えない。やはり読者は虚構世界をそれなりに重く受け止め、虚構世界なりに存在する流れ・秩序といったものを感じ取ることが、より面白い読解に繋がるだろう。そのことを指摘することはそれ自体に大きな意味があると感じられる。

 しかし、ここで誤解を避けるために強調したいことがある。虚構世界に対して真剣に向きあうこととは、決して虚構世界は現実世界と同じように確固たるものとして存在し、虚構キャラクターはまるで現実世界の人間と同じように存在しているのだと主張するのではないということだ。これは大きな違いである。我々は虚構のことを、まるで現実のようなものとして考えなければ重大なものとして扱えないのだろうか。そんなことはないだろう、というのが筆者の思うところである。

 虚構キャラクターが我々とは様式が全く異なった存在だったとして、それ自体が重要性を損なうことは全くないと考える。さらに言えば、そのような存在に対してとも愛を結ぶことができると考える。それはたとえば人間と動物では能力や世界の認識そのものが大きく違うにもかかわらず愛を結ぶことが―少なくとも何かしらの形で―できることと同じである。

 強引な理屈かもしれない。論理などなく、ただそうあって欲しいという願望でしかない。しかし、虚構の良いところはある意味で現実と違うところであり、なおかつ価値としての重大さは現実と同等かそれ以上にあるという二重性にあるのだと思っている。

 この「虚構キャラクターを虚構的な存在として扱ったまま愛を結ぶことができるか?」というテーマに挑んだ作品は、筆者の少ない作品鑑賞体験の中でもいくらか見られるものである。それはたとえばDoki Doki Literature Club!であり、One Shotであり、異セカイ系である。いずれも虚構における愛について、真剣に扱った作品だ。興味が惹かれればぜひ手に取ってみて欲しい。

 冒頭で述べたような指摘というのは、しばしばバッドエンドの形を伴って現れる。プレイヤーの軽々しい選択に対してお灸をすえるような形になる。もちろんそれも楽しい体験だろうが、やはり私は愛の、幸福な物語が好きだ。我々は弱く、迷いやすい存在であるから、時に厳しい結末が必要になるのかもしれないが、現実と虚構の間に多くの愛が実ることを祈って本稿を締めさせていただく。

AtCoder Beginner Contest 117

全体

 55分(1WA)で全完の222位。D問題が解けなさ過ぎて気持ちは冷えていたし身体は熱くなっていた。400点問題がまさか解けない……!? みたいなプレッシャーのかかり方ほんと厳しい。

A問題

 doubleを表示するときはprintfを使ってしまうね。

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

int main() {
    double T, X;
    cin >> T >> X;
    printf("%.10f\n", T / X);
}

B問題

 accumulateとかmax_elementとかを使いたがる。

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

int main() {
    ll N;
    cin >> N;
    vector<ll> L(N);
    for (ll i = 0; i < N; i++) {
        cin >> L[i];
    }
    ll sum = accumulate(L.begin(), L.end(), (ll)0);
    ll max = *max_element(L.begin(), L.end());
    cout << (max < (sum - max) ? "Yes" : "No") << endl;
}

C問題

 最初はN個の駒を全部端から置いていっていいのかなと思ったけど、中央に密集していて両端二つだけめちゃくちゃ離れているときにどっち端から置いていってもダメだということを考えて、じゃあ隣との差が大きいところから置いておくんだということになり、差分を取ってそれの小さい方からM-N個の和が答えということで出す、通る。今気づいたけどこういうところこそaccumulateの使いどころなんじゃないか。なんにしてもここまでは順調だったのに……。

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

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

    if (N >= M) {
        cout << 0 << endl;
        return 0;
    }

    sort(X.begin(), X.end());
    vector<ll> diff;
    for (ll i = 1; i < M; i++) {
        diff.push_back(X[i] - X[i - 1]);
    }
    sort(diff.begin(), diff.end());
    ll ans = 0;
    for (ll i = 0; i < M - N; i++) {
        ans += diff[i];
    }
    cout << ans << endl;
}

D問題

 本日の問題児。全然解けなくてめちゃくちゃ焦った。最初は両辺X排他的論理和を取れば右辺のXが全部消えるんじゃねとか考えていたけどそんなことはない。よくわからないので実験してみるがあまり法則性も見つからない。困った困ったと悩んでいると「排他的論理和は桁ごとに見る」という定跡を思い出す。そうやって考えていくとA_iを各桁で串刺しして見て、0が多い桁はXを1にしたいし、1が多い桁はその逆ということに気づく。ここまでで30分くらいかかった。

 実装でも時間がかかる。2進数にするには文字列にすればいいとかいう謎の勘違いをしたり、Xの範囲制限をすっかり忘れていたり、繰り上がりを2進数として実装しようとして悩んだり、ひどかった。最近あまり競技プログラミングをやっていないもので、実装はすぐに腕が落ちる。実装した後もなんか1WAが出てしまい、よくわからないけど方針は合っている気がしたのでリファクタリングしてコードを奇麗にしたら通った。ビットシフトのどこかだと思う。ビットシフトはバグを生みがち。

 ここで恐ろしい話。

 僕のも16が出るので嘘です。そうか、ちゃんとbitDPをやる方がまともだったかもしれないんですね。うーん、なぜbitDPの発想が出てこないのか。ガタガタだなぁ。まぁこういうこともあると切り替えていきましょう。

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

ll N, K;
vector<ll> A;

int main() {
    cin >> N >> K;
    A.resize(N);
    for (ll i = 0; i < N; i++) {
        cin >> A[i];
    }

    ll ans = 0;
    bool under = false;
    for (ll i = 63; i >= 0; i--) {
        ll num1 = 0;
        for (ll j = 0; j < N; j++) {
            num1 += (A[j] & (1LL << i)) != 0;
        }

        if (!under && ((K & (1LL << i)) == 0)) {
            //0しか選べない
        } else {
            if (num1 >= N - num1) {
                //0を選んだ方が良い
                under = true;
            } else {
                //1を選んだ方が良い
                num1 = N - num1;
            }
        }
        ans += num1 * (1LL << i);
    }
    cout << ans << endl;
}