2024-02-26

CODE FESTIVAL2015チーム対抗早解きリレー J - 石山ゲーム

概要

解説を書きます。

実験

$1 \leq X, Y \leq N$ を満たす全ての状態 $(X, Y)$ について、その状態から始めて勝てるかどうかを $O(N ^ 3)$ 時間で計算できます。このままでは実行制限時間に間に合いませんが、結果から予測して AC を得ることができそうです。

解法

$X \leq Y$ としてゲームの状態を $(X, Y)$ で表します。

求めたいのは状態 $(X, Y)$ が先手勝ち状態と後手勝ち状態のどちらであるか、です。

$X = 1$ の場合

取ることができる石の個数は $1$ 個です。

$(1, 1)$ のとき、どのように操作しても石の個数が $0$ の山ができるので後手勝ち状態です。

$(1, 2)$ のとき、後手勝ち状態 $(1, 1)$ に遷移するので先手勝ち状態です。

$(1, 3)$ のとき、先手勝ち状態 $(1, 2)$ に遷移するので後手勝ち状態です。

$(1, Y)$ の状態は $(1, Y-1)$ の状態によって決まるので、帰納的に

$(1, Y)$ $(Y \bmod{2} = 0)$ のとき先手勝ち状態
$(1, Y)$ $(Y \bmod{2} = 1)$ のとき後手勝ち状態

となります。

$X = 2$ の場合

まず $Y \bmod{2} = 1$ の場合、後手勝ち状態 $(1, Y)$ に遷移できるので先手勝ち状態です。

次に $Y \bmod{2} = 0$ の場合です。

$(2, 2)$ のとき、先手勝ち状態 $(1, 2)$ に遷移する他ないので後手勝ち状態です。

$(2, 4)$ のとき、後手勝ち状態 $(2, 2)$ に遷移できるので先手勝ち状態です。

$(2, 6)$ のとき、遷移先 $(1, 6), (2, 5), (2, 6)$ は全て先手勝ち状態なので、これは後手勝ち状態です。

帰納的に

$(2, Y)$ $(Y \bmod{2} = 1)$ のとき先手勝ち状態 ( $(1, Y)$ に遷移する )
$(2, Y)$ $(Y \bmod{4} = 0)$ のとき先手勝ち状態 ( $(2, Y-2)$ に遷移する )
$(2, Y)$ $(Y \bmod{4} = 2)$ のとき後手勝ち状態

となります。

$X = 3$ の場合

まず $Y \bmod{2} = 1$ の場合、後手勝ち状態 $(1, Y)$ に遷移できるので先手勝ち状態です。

次に $Y \bmod{4} = 2$ の場合、後手勝ち状態 $(2, Y)$ に遷移できるので先手勝ち状態です。

最後に $Y \bmod{4} = 0$ の場合です。

$(3, 4)$ のとき、後手勝ち状態 $(1, 3)$ に遷移できるので、これは先手勝ち状態です。

$Y \bmod{4} = 0$ かつ $Y \geq 8$ のとき、遷移先は $(1, Y), (2, Y), (3, Y-1), (3, Y-2), (3, Y-3)$ がありますが、いずれも先手勝ち状態なので、このとき後手勝ち状態です。 ( $Y \geq 8$ より $Y-1, Y-2, Y-3 \geq 3$ が効いています。)

まとめると

$(3, Y)$ $(Y \bmod{2} = 1)$ のとき先手勝ち状態 ( $(1, Y)$ に遷移する )
$(3, Y)$ $(Y \bmod{4} = 2)$ のとき先手勝ち状態 ( $(2, Y)$ に遷移する )
のとき
- $Y = 4$ のとき先手勝ち状態 ( $(1, 3)$ に遷移する )
- $Y \neq 4$ のとき後手勝ち状態

$X = 4$ の場合

まず $Y \bmod{2} = 1$ ならば後手勝ち状態 $(1, Y)$ に遷移できるので先手勝ち状態です。

次に $Y \bmod{4} = 2$ ならば後手勝ち状態 $(2, Y)$ に遷移できるので先手勝ち状態です。

最後に $Y \bmod{4} = 0$ の場合です。 $(4, 4)$ のとき、遷移先 $(1, 4), (2, 4), (3, 4)$ は全て先手勝ち状態なので、これは後手勝ち状態です。 $Y \bmod{4} = 0$ かつ $Y \geq 8$ のとき、後手勝ち状態 $(3, Y)$ に遷移できるので先手勝ち状態です。

まとめると

$(3, Y)$ $(Y \bmod{2} = 1)$ のとき先手勝ち状態 ( $(1, Y)$ に遷移する )
$(3, Y)$ $(Y \bmod{4} = 2)$ のとき先手勝ち状態 ( $(2, Y)$ に遷移する )
のとき
- $Y = 4$ のとき後手勝ち状態
- $Y \neq 4$ のとき先手勝ち状態 ( $(3, Y)$ に遷移する )

$X \geq 5$ の場合

$Y \bmod{2} = 1$ ならば後手勝ち状態 $(1, Y)$ に遷移できるので先手勝ち状態です。

$Y \bmod{4} = 2$ ならば後手勝ち状態 $(2, Y)$ に遷移できるので先手勝ち状態です。

$Y \bmod{4} = 0$ ならば、 $Y \geq 5$ より後手勝ち状態 $(3, Y)$ に遷移できるので先手勝ち状態です。

よって全ての $Y$ について先手勝ち状態です。

終わりに

$(X, Y)$ から $(1, Y), (2, Y), \dots, (X-1, Y)$ に遷移できることから、先手は $X$ が小さい時に負ける盤面を押し付けることができています。 $X \geq 5$ の場合には勝ち状態で埋め尽くされてしまうんですね。

シンプルな問題設定、かつ、サッと実験のコードを書けば法則がわかるので、早解きリレーならではの良い問題だと思いました。

2023-12-03

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 束についての包除原理は成り立ちます (参考: 分配束（をなす集合を始域とする写像の終域上の演算）における包除原理 - 獅子座じゃない人のブログ ) 。

2023-11-25

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 が適用できる可能性があります。これは次の可能性からです。

を直接求めることが難しい
- 最適値を求める際に、これまでに何個使ったかを覚えておく必要があります
- 例えば $n$ 個の要素について $\mathrm{dp} _ {i, j} := i$ 番目まで見て $j$ 個使ったときの最適値、とすると $\Omega (n ^ 2)$ 時間です
を求めることが易しい
- 添字に持つ必要があった個数の情報が、 $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日記

2023-03-05

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

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

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

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

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

早期卒業制度とは

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

卒業要件に関わる科目を 110 単位以上取得する
2年次終了時の GPA が 4.15 以上である
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年秋に卒業研究に代わる講義を履修します。

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

終わりに

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

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

2023-01-02

ICPC 2022 Asia Yokohama Regional 参加記

チーム Tsubaki

メンバー
- KY2001 AtCoder
- M4c4r0n AtCoder
- Rogi AtCoder
コーチ
- NOSS AtCoder

先輩方が引退し、今年度新しく結成したチーム。水〜青の実力で、来年度は全員院へ進むという、似た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完以上できる力を付けること、順位表に頼りすぎないこと。あとは、個人的にフローとお友達になりたい。

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