日記 9/16–9/30

9/16

応用情報

4.2 節を読んだ。今日情報の授業で気づいたけど、情報の教科書読んでおくだけで割と対策になるんじゃないか？

9/17

応用情報

飛行機の中で 4.3 節を読んだ

9/18

IOI2022 International Study Camp

Study Camp という名の観光
午前中にあった Huawei 社の方々によるスピーチでは社内での AI 関連の研究について説明していただいた。大雨の中撮った映像から、雨を除去した映像を生成する話が面白いと思ったが、前提知識もリスニング力も足りておらず十分に理解できなかったのが残念

応用情報

ノートを丁寧にとるのは諦めた。4.4 節から 4.6 節までを読んだ

9/19

IOI2022 International Study Camp

朝 9 時に外に出て、夜 10 時半に帰ってきた 午前中はいくつかの講義 + Huawei のオフィス見学 午後は NUS キャンパス見学 + Gardens by the Bay 観光 あまりに充実している

9/20

IOI2022 International Study Camp

セントーサ島散策、Vivo City、マーライオンなど 夕食時に NUS に熱烈勧誘を受け気持ちが揺らいだ (海外の大学、奨学金が豊富すぎて…)

競プロ

溜めていた記事を読んだ

木上の等高線集約クエリ (by suisen さん) 重心分解で 1 点更新区間取得 (by noshi91 さん)

↓この記事も途中まで読んだ

マージテクと高さ O(logn) のマージ過程との融合 (by Nachia さん)

マージの方法を定式化して分類したり、重心分解をある種のマージテクと捉えるという考え方は自分にはなかったので勉強になった

9/21

応用情報

4 章を読み終えた。待ち行列理論の話、証明もなしに公式を出されたのでモヤッとした

作問

いい感じの簡単枠が生えた

9/23

競プロ

AHC014 にようやく手をつけた。いつ提出できるだろうか

応用情報

5.3 節を読んだ

その他

LT 会の資料を作った
完全にただの旅行記になってしまった

9/24

応用情報

5 章を読み終えた
明日から電車で過去問道場やろう

その他

明日のあどれの夜ゼミで使うスライドを作った。誤植などは明日確認する
伊計島メンバーでオンライン夜ゼミがあった。LT でシンガポール旅行について話した
今回の夜ゼミは聞き専だった。毎回発見があって面白い

9/25

その他

体育祭 + あどれの夜ゼミ + お仕事 などなどで一日中忙しかった…
幸い、明日は休みなので色々頑張ろう

9/26

組合せゲーム理論

二週間ぶりの勉強会。特定のゲームについて全ての局面が number であることを示す証明手法や、dyadic rational number を効率よく計算する方法、switch が選択肢に含まれるゲームの比較・評価について学んだ

スプラトゥーン 3

S+ 昇格戦勝てない

9/27

競プロ

dyadic rational number を用いて解ける問題をもう一つ見つけたので解いた
a + \frac{b}{2^{64}} という形で持つのが一番良さそうだという感想になった

問題 提出コード

class DyadicRational {
    using Self = DyadicRational;

    // a + b/2^64
    i64 a;
    u64 b;

  public:
    DyadicRational() : a(0), b(0) {}
    DyadicRational(const i64 a) : a(a), b(0) {}
    explicit DyadicRational(const i64 a, const u64 b) : a(a), b(b) {}

    Self operator+(const Self& t) const { return Self(a + t.a + (b + t.b < b), b + t.b); }

    Self operator-() const { return Self(-a - (b > 0), -b); }

    Self left() const {
        if (is_integer())
            return a - 1;
        return *this + -Self(0, b & -b);
    }

    Self right() const {
        if (is_integer())
            return a + 1;
        return *this + Self(0, b & -b);
    }

    std::pair<i64, u64> get() const { return {a, b}; }

    bool is_integer() const { return b == 0; }

    friend bool operator<(const Self& x, const Self& y) {
        return x.a < y.a or (x.a == y.a and x.b < y.b);
    }

    friend bool operator>(const Self& x, const Self& y) {
        return x.a > y.a or (x.a == y.a and x.b > y.b);
    }

    friend Self game(const Self& x, const Self& y) {
        if (!(0 < y))
            return -game(-y, -x);
        if (x < 0)
            return 0;
        if (x.a + 1 < y)
            return x.a + 1;
        if (const int msb = y.is_integer() ? 64 : 63 - countl_zero(x.b ^ y.b);
            (y.b << (64 - msb)) != 0) {
            return Self(x.a, ((x.b >> msb) + 1) << msb);
        } else {
            const int next = msb - countl_zero(~(x.b << (64 - msb))) - 1;
            return Self(x.a, ((x.b >> next) + 1) << next);
        }
    }
};

一年以上使ってきた自動メモ化ライブラリのバグ (今まで何度も使ってきたが遭遇しなかった) を今日突然踏んでびっくりした。std::decay を噛ませていなかったのが原因らしい…

その他

悩んでいた GCC のバグが治った。Xcode のバージョンを下げれば良かったらしい 参考

9/28

競プロ

部内で開く JOI バチャの準備をした
JOIG 春合宿で一番難しいと言われていた問題を解いた。難易度 8 だったが結構難しくて驚いた 問題 提出コード

9/29

競プロ

JOI バチャの解説を作成

応用情報

6.2 節まで読んだ
そろそろヤバくなってきたな

9/30

競プロ

JOI バチャを開催 + 解説を担当した バチャのリンク

ちなみに明日の ABC で Writer をしている (今週はこれで忙しかった)

応用情報

6.6 節まで読んだ
SQL 全くわからん