LCS のワードサイズ高速化

概要

[1] で紹介されている LCS のワードサイズ高速化について、自分の理解を記します。 特に新しい主張はないです。

内容は [2] を大きく参考にしています。

dp 配列とその差分

\mathrm{dp} _ {i, j} を二つの文字列 S _ {1 .. i}, T _ {1 .. j} の LCS の長さ、と定義します。 次が成り立ちます。

\begin{align*} \mathrm{dp}_{i, j} = \begin{cases} 0 & (i = 0 \ \mathrm{or}\ j = 0) \\ \mathrm{dp}_{i-1, j-1} + 1 & (S_i = T_j) \\ \max( \mathrm{dp}_{i-1, j}, \mathrm{dp}_{i, j-1} ) & (\mathrm{Otherwise}) \end{cases} \end{align*}

j についての差分 D _ {i, j} := \mathrm{dp} _ {i, j} - \mathrm{dp} _ {i, j-1} を考えます。 D _ {i, j} \in \lbrace 0, 1 \rbrace なので D は bit 列として表現できます。

遷移の観察

D _ {i-1} から D _ {i} への遷移を考えます。

便宜上、 D _ {i-1} の末尾に 1 を、 D _ {i} の末尾に 0 を追加しています。

また、 D _ {i-1, j} = 1 なる添字列 j _ 0 \lt j _ 1 \lt j _ 2 \lt \dots \lt j _ k (= |T|+1) について、 \lbrack 1, j _ 0 \rbrack, \lbrack j _ 0 + 1, j _ 1 \rbrack, \lbrack j _ 1 + 1, j _ 2 \rbrack, \dots に分割して、二重線で囲んでいます。

各区間について、 1 の位置の変化に注目しましょう。 同じ場所にあるか、左側に移動していることがわかります。 移動しているのは

  • D _ {i-1, j} = 1 の場所
  • S _ {i} = T _ {j} の場所

のうち、最も左にある場所です。

自然な解釈

この 1 の移動は D の意味を考えるとより自然かもしれません。 D _ {i, j ^ { * } } = 1 なる添字 j ^ { * } を一つ取ります。 このとき \sum _ {j \leq j ^ { * } } D _ {i, j} は \mathrm{dp} _ {i, j ^ *} (つまり S _ {1 .. i} と T _ {1 .. j ^ { * } } の LCS の長さ) に等しいです。

これは逆に LCS の長さが 初めて x になるような添字 j の列を D が管理していると考えることができます。 文字 \alpha が追加されると、各添字は (前の添字を追い越さないように) 左側に進んでいきます。 番兵として D の末尾に 1 を追加しましたが、これが左側に移動することが、全体の LCS の長さが 1 だけ長くなることに対応しています。

ビット演算

各区間における最も左の 1 の場所に 1 を立てたいです。

ここから先は整数に対する演算を考えるので、左右を反転して考えることにします。

  • D : 現在の配列。各区間の左端には 1 が立っている。
  • m : 新しく追加する文字と一致するところに 1 が立っている
  • 各区間においてD|mの最も右の 1 の場所に 1 があるようにしたい

2 種類の計算式を説明します。

D = (D | m) ^ ((D | m) & ((D | m) - (D << 1 | 1))) [2]

  1. 右隣の区間の左端には 1 が立っているので、(D << 1 | 1)で各区間の右端に 1 がある状態になります（最も右の区間だけ 1 を追加する必要がある）。

  2. (D | m) - x で (D | m) の最下位ビットが 0 に、それ以下のビットが 1 になったものが手に入ります。

  3. (D | m) & x で (D | m) の最下位ビットだけが 0 になります。

  4. (D | m) ^ x で (D | m) の最下位ビットだけが 1 になります。

                       D                       --- 1000000
                           m                   --- 0110100
                       D | m                   --- 1110100
                                 D << 1 | 1    --- 0000001
                      (D | m) - (D << 1 | 1)   --- 1110011
           (D | m) & ((D | m) - (D << 1 | 1))  --- 1110000
(D | m) ^ ((D | m) & ((D | m) - (D << 1 | 1))) --- 0000100

D = (D | m) & (D - (m & ~D)) [1]

[1] では [2] で紹介されたビット演算を式変形によって簡略化しました。 この演算を直接理解することもできます。

一つの区間で考えます。m が 0 のときは D はそのままです。

m が 0 でないとき、

  1. m & ~D は m の中で D に含まれない 1 が立ちます。

  2. D - (m & ~D) は、m を右から見ていって、最下位ビットから〜次に 1 が立つ場所の手前まで 1 が連続します。

  3. (D | m) & (D - (m & ~D)) は m の最下位ビットだけが残ります。

 D                       --- 100000
     m                   --- 111010
 D | m                   --- 111010
                m & ~D   --- 011010
           D - (m & ~D)  --- 000110
(D | m) & (D - (m & ~D)) --- 000010

終わりに

実装例

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

struct simple_bitset {
    int n;
    vector<unsigned long long> data;
    simple_bitset(int n_) : n((n_ + 64 - 1) / 64), data(n, 0) {} 

    using bs = simple_bitset;
    void set_one(const int i) {
        data[i / 64] |= 1ULL << (i % 64);
    }
    bs& operator&=(const bs& r) {
        for(int i = 0; i < n; i++) data[i] &= r.data[i];
        return *this;
    }
    bs& operator|=(const bs& r) {
        for(int i = 0; i < n; i++) data[i] |= r.data[i];
        return *this;
    }
    bs& operator-=(const bs& r) {
        for(int i = 0, c = 0, nc = 0; i < n; i++) {
            nc = data[i] < r.data[i] || (data[i] == r.data[i] && c);
            data[i] -= r.data[i] + c;
            c = nc;
        }
        return *this;
    }
    bs operator&(const bs& r) const { return bs(*this) &= r; }
    bs operator|(const bs& r) const { return bs(*this) |= r; }
    bs operator-(const bs& r) const { return bs(*this) -= r; }
    bs operator~() const {
        bs x = *this;
        for(int i = 0; i < n; i++) x.data[i] = ~x.data[i];
        return x;
    }
    int count() const {
        int cnt = 0;
        for(int i = 0; i < n; i++) cnt += __builtin_popcountll(data[i]);
        return cnt;
    }
};

int lcs(const string& s, const string& t) {
    const int n = s.size(), m = t.size();
    vector M(26, simple_bitset(m));
    for(int j = 0; j < m; j++) M[t[j] - 'a'].set_one(j);

    simple_bitset D(m);
    for(int i = 0; i < n; i++) {
        const simple_bitset& Ms = M[s[i] - 'a'];
        D = (D | Ms) & (D - (Ms & ~D));
    }
    return D.count();
}

int main() {
    string s, t; cin >> s >> t;
    cout << lcs(s, t) << endl;
}

「暫定 LCS の添字列を更新していく」方針で LCS を眺めるのは初めてで新鮮でした。

[1] では本記事で紹介したワードサイズ高速化に加えて、空間計算量の削減を行なっています。 また、verify 場所も記載されています。 ぜひ参考にしてみてください。

参考文献

[1] LCS を時間 O(|S| |T| / w)、空間 O(|S| + |T|) で復元までやる rian.hatenablog.jp

[2] 비트 연산을 활용하여 두 문자열의 LCS 빠르게 구하기

元 URL: http://www.secmem.org/blog/2019/09/12/lcs-with-bitset/

Wayback Machine より: web.archive.org

AOJ 2638 Hyperrectangle を FPS で考える

概要

onlinejudge.u-aizu.ac.jp

FPS で考えます。

(包除原理による解説は例えば次を参照ください)

drken1215.hatenablog.com

なぜ FPS か？

各 x _ i の制約と、総和の制約を見て、FPS を直感しました。

実際、 x _ i を 0 以上 l _ i 以下の 整数 とすると、 x_1 + \dots + x_d \leq s を満たす列 (x _ i) の個数は次のように書けます。

\begin{align*} [x ^ s] \frac{1}{1 - x} \prod _ {i = 1} ^ d \frac{1 - x^{l_i + 1}}{1 - x} \end{align*}

x_1 + \dots + x_d = s を満たす列 (x _ i) を考えた後で、 累積和を取れば良いです。

この式で x_1 + \dots + x_d \leq s を満たす格子点の個数は求められました。

体積を近似する

問題は x_i が 実数 であることです。FPS は離散値を扱いやすいので、 点の間隔を小さくしていって、体積を近似することを考えます。

k 個に分割するとして、 \varepsilon = k^{-1} とおきます。各軸の選択は次のようになります。

\begin{align*} &\phantom{=} \sum_{e=0}^{l_i - 1} \left(x^e + x^{e + \varepsilon} + x^{e + 2\varepsilon} + \dots + x^{e + 1 - \varepsilon} \right) \\ &= \left(1 + x^{\varepsilon} + x^{2\varepsilon} + \dots + x^{1 - \varepsilon} \right) \sum_{e=0}^{l_i - 1} x^e \\ &= \frac{1 - x}{1 - x^\varepsilon} \cdot \frac{1 - x^{l_i}}{1 - x} = \frac{1 - x^{l_i}}{1 - x^\varepsilon} \end{align*}

指数部分に非整数があるので FPS から外れていますが、 k 倍に引き伸ばせば正当になると思っています。

k 個に分割したときの近似体積 V_k は次のように書けます。 累積和をとるときに x^{i + n\varepsilon} も考慮する必要があることに注意します。

\begin{align*} V_k &= \varepsilon^d \times [x^s] \frac{1}{1 - x^{\varepsilon}} \prod_{i=1}^{d} \frac{1 - x^{l_i}}{1 - x^\varepsilon} \\ &= \varepsilon^d \times [x^s] \left(\frac{1}{1 - x^{\varepsilon}}\right)^{d+1} \prod_{i=1}^{d} \left(1 - x^{l_i}\right) \end{align*}

f(x) = \prod_{i=1}^{d} (1 - x^{l_i}) とします。負の二項定理から

\begin{align*} V_k = \varepsilon^d \sum_{i + j = s} \binom{i / \varepsilon + d}{d} \times f_j = \frac{1}{d!} \sum_{i+j = s} \frac{(i / \varepsilon + d)!}{(i / \varepsilon)!} \times \varepsilon^d \times f_j \end{align*}

ここで

\begin{align*} \frac{(i/\varepsilon + d)!}{(i/\varepsilon)!} \times \varepsilon^d &= \left(\frac{i}{\varepsilon} + d\right)\left(\frac{i}{\varepsilon} + d - 1\right) \dotsm \left(\frac{i}{\varepsilon} + 1\right) \times \varepsilon^d \\ &= (i + d\varepsilon) (i + (d-1) \varepsilon) \dotsm (i + \varepsilon) \longrightarrow i^d \ (\varepsilon \to 0) \end{align*}

よって求める値は次のようになります。

\begin{align*} d! V = \sum_{i+j=s} i^d \times f_j \end{align*}

計算量

L = \sum_{i=1}^{d} l_i とします。 f は d 個の疎な多項式の積です。 愚直な計算は O(dL) です (今回はこれが間に合う制約で、実装も軽い)。exp-log テクで O(L \log L) になります。

実装例

ABC331 G - Collect Them All

概要

atcoder.jp

一直線でシンプルだと感じた解法について書きます。

(修正 2023/12/06) *1

解法

  • A _ i := ノートに i が 1 個以上書かれている事象
  • E(A) := 事象 A が起こるまでの操作回数の期待値

とします。 求める答えは E \left ( \bigcap \limits _ {i} A _ i \right ) です。

包除原理

包除原理を用いて次のように式変形できます。

\begin{align*} E \left( \bigcap _ {i \in [M]} A_i \right) &= \sum _ {S \subseteq [M] ,\, S \neq \emptyset } (-1)^{|S| - 1} E \left( \bigcup _ {i \in S} A_i \right) \\ &= \sum _ {S \subseteq [M] ,\, S \neq \emptyset } (-1)^{|S| - 1} \frac{1}{ \frac{ \sum_{i \in S} C_i }{N} } \\ &= (-N) \sum _ {S \subseteq [M] ,\, S \neq \emptyset } \frac{(-1)^{|S|}}{ \sum_{i \in S} C_i } \\ &= (-N) \sum _ {k = 1} ^ {N} \sum _ { \sum \limits _ {i \in S} C _ i = k } \frac{(-1)^{|S|}}{k} \\ &= (-N) \sum _ {k = 1} ^ {N} \frac{1}{k} \sum _ { \sum \limits _ {i \in S} C _ i = k } (-1)^{|S|} \\ &= (-N) \sum _ {k = 1} ^ {N} \frac{1}{k} \left \lbrack [x^k] \prod _ {i \in [M]} \left(1 - x^{C_i}\right) \right \rbrack \end{align*}

二つ目の等号の変形が肝です。 E \left( \bigcup \limits _ {i \in S} A_i \right) は S 内のいずれかが書かれるまでの操作回数の期待値ですから、 \frac{ \sum _ {i \in S} C _ i} {N} の逆数に等しいです。

k 回目の操作の寄与を考える (公式解説 1) ことをしないのでシンプルだと感じました。

exp-log テク

次数の総和が N である多項式の総積は O\left(N \left ( \log N \right) ^ 2 \right ) 時間で計算できるので問題が解けました。 今回は多項式が f _ i (x) = 1 - x ^ { C_i } と特殊な形をしているので、FPS の exp-log テクを使って (理論的に) 高速化できます。

\begin{align*} \prod _ {i \in [M]} \left(1 - x^{C_i}\right) &= \exp \left \lbrack \sum _ { i \in [M] } \log \left( 1 - x^{C_i} \right) \right \rbrack \\ &= \exp \left \lbrack \sum _ {j = 1} ^ {N} \# \lbrace i \mid C_i = j \rbrace \log \left( 1 - x^j \right) \right \rbrack \end{align*}

ここで \log の定義から次のように書けます。

\begin{align*} \log(1 - x^j) = - \sum _ {i=1} ^ {\infty} \frac{ \left( x^j \right)^i } {i } = - \sum _ {i = 1} ^ {\infty} \frac{x^{ij}}{i} \end{align*}

\# \lbrace i \mid C_i = j \rbrace は O(N) 時間でテーブルを作っておきます。 \log の部分は ij \leq N を見ればよいので、 \exp の中身は \sum _ {j = 1} ^ {N} \left \lfloor \frac{N}{j} \right \rfloor = O(N\log N) 時間で計算できます。 \exp も O(N \log N) 時間で計算できるので、全体で O(N \log N) 時間です。

実装例

*1:「 X _ i := ノートに i が 1 個以上書かれている状態になるまでの操作回数の期待値とし、答えは \max \limits _ i X _ i である」としていましたが、これは誤りです。 なお、min-max 束についての包除原理は成り立ちます (参考: 分配束（をなす集合を始域とする写像の終域上の演算）における包除原理 - 獅子座じゃない人のブログ ) 。

Aliens DP の整理

陽には与えられない、下に凸な関数 f \colon \mathbb{Z} \to \mathbb{R} があるとします。 任意の p \in \mathbb{R} に対して g(p) = \min \limits _ {x \in \mathbb{Z}} \lbrack f(x) - px \rbrack が O(T) 時間で計算できるとき、 任意の x ^ {\mathrm{target}} \in \mathbb{Z} に対して f(x ^ { \mathrm{target} } ) が O(T \log P) 時間で計算できます。 ただし、傾き f(x+1) - f(x) が bound されていて、 P = \max \limits _ {x \in \mathbb{Z}} \lbrack f(x+1) - f(x) \rbrack - \min \limits _ {x \in \mathbb{Z}} \lbrack f(x+1) - f(x) \rbrack とします。

アルゴリズム

x ^ {\mathrm{target} } \in \mathop{ \mathrm{arg\,min} } \limits _ {x} \lbrack f(x) - p x \rbrack を満たす p を見つけます。

方針として二分探索と三分探索の 2 つが考えられます。

(傾き) 二分探索

簡単のために \mathop{ \mathrm{arg\,min} } \limits _ {x} \lbrack f(x) - px \rbrack は 1 元集合とします。 g(p) = \min \limits _ {x} \lbrack f(x) - px \rbrack を求める操作は、 y = f(x) と傾き p の直線が接するときの接点の y 座標を求める操作に対応しています。 f が下に凸ですから、 p \mapsto \mathop{ \mathrm{arg\,min} } \limits _ {x} \lbrack f(x) - px \rbrack は広義単調増加です。したがって二分探索ができます。

x^* _ p = \mathop{ \mathrm{arg\,min} } \limits _ {x} \lbrack f(x) - px \rbrack を求めます。 まず g(p) を計算します。次に、十分小さい \varepsilon \in \mathbb{R} について g(p + \varepsilon) を計算します。このとき

\begin{align*} \mathop{ \mathrm{arg\,min} } \limits _ {x} \lbrack f(x) - px \rbrack = \mathop{ \mathrm{arg\,min} } \limits _ {x} \lbrack f(x) - (p + \varepsilon ) x \rbrack = x ^ * _ p \end{align*}

が成り立ちます。したがって

g(p) - g(p + \varepsilon ) = \lbrack f(x ^ * _ p) - p x ^ * _ p \rbrack - \lbrack f(x ^ * _ p) - (p + \varepsilon ) x ^ * _ p \rbrack = \varepsilon x ^ * _ p

より x ^ * _ p を求めることができます。あとは x ^ * _ p と x ^ { \mathrm{target} } の大小で分岐すれば良いです。 g(p) を計算する際に、同時に x ^ * _ p が計算できるならばこの部分は簡略化できます。

三分探索

任意の p について次が成り立ちます。

\min \limits _ {x} \lbrack f(x) - px \rbrack \leq f( x ^ {\mathrm{target}} ) - p x ^ {\mathrm{target}}

移項して p について \max をとると

f(x ^ { \mathrm{target} }) = \max \limits _ {p } \left \lbrack \min \limits _ {x } \lbrack f(x) - px \rbrack + p x ^ {\mathrm{target}} \right \rbrack

が成り立ちます。 p \mapsto g(p) + p x ^ {\mathrm{target}} は上に凸ですから、三分探索ができます。

なお次のように式変形すると、制約 x = x ^ { \mathrm{target} } のラグランジュ緩和とのつながりがわかりやすくなります。ラグランジュ緩和と Aliens DP の対応については [1] に示されています。

f(x ^ { \mathrm{target} }) = \max \limits _ {p } \left \lbrack \min \limits _ {x } \lbrack f(x) + p \left(x ^ { \mathrm{target} } - x \right) \rbrack \right \rbrack

整数値の場合

f(x) - px の値が等しくなる tie-breaking について注意を払う必要があります。

対処法については [2] が非常に参考になります。

ペナルティ回数の管理は、 g(p) の計算と同時に x ^ * _ p を求めることを指しています。三分探索については同様です。傾き二分探索については \varepsilon = 0.5 に注目します。

f(x ^ { \mathrm{target} }) が与えられる場合

はじめ考えたのは x ^ { \mathrm{target} } が与えられたとき f(x ^ { \mathrm{target} }) を求める問題です。

逆に f(x ^ { \mathrm{target} } ) が与えられたとき x ^ { \mathrm{target} } を求める問題も考えられます。

本記事の手法を用いて二分探索することもできますが、[2] で紹介されているように適切に f を平行移動した後 - g(p) / p について三分探索することで \log を一つ落とすことができます。

アルゴリズムの適用

[3] は Aliens DP の名前の由来となった問題です。 この問題のように f(x) := x 個使ったときの何らかの最適値、という関数について Aliens DP が適用できる可能性があります。これは次の可能性からです。

  • f(x) を直接求めることが難しい
    • 最適値を求める際に、これまでに何個使ったかを覚えておく必要があります
    • 例えば n 個の要素について \mathrm{dp} _ {i, j} := i 番目まで見て j 個使ったときの最適値、とすると \Omega (n ^ 2) 時間です
  • g(p) を求めることが易しい
    • 添字に持つ必要があった個数の情報が、 p を用いて DP の値に取り込まれます
    • 個数の情報を持たない場合、 o(n ^ 2) 時間で計算できる可能性があります

[4] に Aliens 以外の問題への適用例がいくつか示されています。

参考文献

[1] Monge グラフ上の $d$-辺最短路長を計算するアルゴリズム, Kyopro Encyclopedia of Algorithms (ア辞典)

[2] Aliens DP における二分探索の色々 - noshi91のメモ

[3] 宇宙人 (Aliens), 情報オリンピック日本委員会 (PDF)

[4] Alien DP についてのメモ - hitoare日記

横浜国立大学を早期卒業する

横浜国立大学 理工学部 数物・電子情報系学科 情報工学EP を早期卒業 (3年で卒業) します。

早期卒業制度は利用者が少ないです (理工学部の令和4年度卒業者の中では1人) 。また 1年早く卒業できる横浜国立大学の早期卒業制度！是非活用を の他に参考になるサイトがありませんでした。

そこで早期卒業するためにどの時期に何をしたのか振り返ります。 さらに早期卒業制度を利用するメリットやデメリット、飛び級との違いについて記します。

この制度に興味を持ってもらえたり、利用する人の力になれたりしましたら幸いです。

早期卒業制度とは

3年次に4年次開講の科目 (特に卒業研究) を履修でき、卒業に必要な条件を満足すれば入学後4年未満であっても卒業できる制度です。条件は次の3つです。

  1. 卒業要件に関わる科目を 110 単位以上取得する
  2. 2年次終了時の GPA が 4.15 以上である
  3. 2年次までの必修単位を全て取っている

条件は変わる可能性があるので、利用する場合は自分で調べてください。

制度利用の振り返り

以下では情報工学EPの条件に基づいて説明していきます。

1・2年次

早期卒業できるかどうかは2年次までの成績にかかっています。

条件1 : 110 単位の取得

履修登録単位数の上限解放が毎学期できたと仮定して、2年次までに取得できる卒業要件に関わる科目の単位数は 24 (1春) + 26 (1秋) + 26 (2春) + 26 (2秋) + 10 (履修上限除外科目) = 112 単位 です。2単位の余裕はありますが、ほとんど毎学期フル単が求められます。

条件2 : 4.15 以上の GPA

横浜国立大学の GPA は、評価に与えられる Grade Point が特殊で、次のようになっています。

評価 不可 可 良 優 秀
評価点 [0, 60) [60, 70) [70, 80) [80, 90) [90, 100]
Grade Point 0.0 2.0 3.0 4.0 4.5

GPA は次のように計算されます。

\displaystyle \mathrm{GPA} = \frac{ \sum \mathrm{GP} \times 単位数 }{ 履修登録単位数 }

GPA を 4.15 以上にするためには、優だけでなく、秀を取る必要があります。 仮に 110 単位を取得し、評価が秀の単位が x 個、優の単位が (110 - x) 個だとします。このとき、条件を満たすには x \geq 33 が必要で、講義全体の \frac{33}{110} = \frac{3}{10} で秀の評価を取る必要があります。

優の評価は絶対評価だが、秀の評価は相対的に決まるといった講義もあり、秀の評価を取ることは簡単ではありません。大きなレポートや試験に加え、日頃の小テストについても気を抜かずこなしていくことをおすすめします。

条件3: 必修単位を全て取る

2単位の余裕の中に、必修単位を入れてはいけません。

2年次12月末

条件を満たす見通しがあって、早期卒業したい場合、教務委員の方にその旨を連絡します。連絡の目的は次の2つです。

  • 条件を本当に満たせるかの確認
  • 2・3月に行われる卒研配属のメンバーへの追加

2年次 2・3月

卒研配属を決めるため、研究室紹介と、配属希望調査があります。教務委員の方からの連絡に注意して、手続きを進めます。

卒研配属は、1年間卒業研究を行う研究室を決めるので重要です。実は3年次の履修科目に「情報工学特別演習」という各研究室の研究内容を知り、演習で体験できる講義があるのですが、受講する前に配属希望を出すので、研究室については前もって調べておく必要があります。研究室紹介が配属希望調査前にありますが、それ以前から興味のある研究室にはコンタクトを取るなどして、研究室とのマッチングを考えておくといいと思います。

3年次 4月

卒業に必要な3年次の科目に加え、卒業研究を履修登録します。早期卒業はイレギュラーで、システム上ではうまくいかない可能性もあるので (私がそうだった) 、学務に連絡するなどして履修登録を忘れないようにしてください。

大学院への進学を考えている場合、英語試験の受験・スコアの取得が試験に間に合うのがこの時期で最後です。スコアの取得は結果を閲覧できるようになってからも時間が必要なことが多いので、早めの準備をおすすめします。なお、早期卒業の条件を満たしていたためか、特別選抜を受けることができました。

講義と研究の両立は大変でした。

早期卒業のメリット・デメリット

メリット

  • なんかかっこいい
  • 社会で早く活躍できる
  • 学費を抑えて経済的余裕ができる
  • 講義の内容に習熟する
  • 努力したエピソードになる

デメリット

  • 高い評価を得るためだけに時間を使ってしまう
  • 講義と卒業研究の両立が大変

飛び級との違い

飛び級は3年で大学を辞め、大学院に進学することのできる制度です。3年秋に卒業研究に代わる講義を履修します。

早期卒業は飛び級より条件が厳しい代わりに、飛び級では取得できない学士を取得することができます。また卒業研究の経験を積むことができるので、大学院に進む際に有利になると思います。

終わりに

横浜国立大学における早期卒業制度と利用の流れについて説明しました。

早期卒業は学業に力を入れたい方に向けた、わかりやすい一つの目標になれると思います。大変ではありますが、達成感がありますし、ぜひ挑戦してみて欲しいと思います。

ICPC 2022 Asia Yokohama Regional 参加記

チーム Tsubaki

先輩方が引退し、今年度新しく結成したチーム。水〜青の実力で、来年度は全員院へ進むという、似た3人でできている。 チーム名は横浜市の市民の木に因んで付けました。

前日

初めてのオンサイトICPCでやや緊張。オープニング映像はカッコ良かったし、競プロerの実在が確認できて高揚感。

リハーサルでは4問を解いて環境に慣れた。エディタは馴染みのある VSCodium を選択。拡張機能が使える CLion が良かったかもしれない。 印刷が $ print.sh FILENAME でできたのが便利でした。

終了後はそれぞれの家に帰って寝ました。

コンテスト

初動はKY2001さんがAと環境構築、M4c4r0nさんがB、私がC以降を読むことに。

A (AC)

貪欲にとっていけば良い。少しバグっていたみたいだが、他にコーディングする問題もなくそのままデバッグ。その後すぐAC。

B (AC)

インタラクティブ問題。各桁で二分探索して決めていけば良さそうと考察を伝え、実装を任せた。WAが出るが、区間の初期値を修正してAC。半開区間で持つといいですね。

C

フローっぽさを感じとり、最小費用流を考えるグラフを作りたい。が、他にACしたチームもなく諦める。S・T・Uが外周にある条件を見落としていた。

D (AC)

回転に加え、平行移動はコインの対応を4通り試せば十分。AC数が少なく不安になるも実装開始。デバッグ用に領域を小さくしていたのを忘れていて2WA。申し訳ない。

G (AC)

削除する辺を決めたとき、追加する辺はおのずと決まる。削除する辺の両端が、入口と出口のどちらに対応するかや、そもそも削除できるかはLCAで判定した。YNUCPC ICPC Library のダブリングによる実装を写経。サンプルが優しかった印象。解説の距離による判定は勉強になった。

E

BITを使ってDPの更新を高速化する。3人で考察を共有後、2人に実装を任せ、私は他の問題の考察に移る。しかし、実装が大変で、最後までACすることができなかった。私も含めてデバッグしていれば、と悔やまれる。

F

4分割は間に合わない。2分割が2種類が存在すれば良いことに気づけず、コンテスト終了。その他の問題についてもあまり考察できず。

結果

ABDGの4完で、24位。4完内では真ん中のスピードだった。

感想と今後

常にワクワク感があり、楽しかったです。モチベーションも上がりました。大会の開催に関わっていただいた皆さん、ありがとうございました。また、チームメンバーの皆さん、組んでくださってありがとうございました。

E, F (H, Jあたりを含めて) を解いて6完以上できる力を付けること、順位表に頼りすぎないこと。あとは、個人的にフローとお友達になりたい。

来年も参加したいと思っています。よろしくお願いします。