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)$ という性質は使うんだろうなと考える。関数 $g$ を $g(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;
}