こんちゅう

エッセイ・小説・ブログ・楽譜置き場。 不定期更新。

京都大学情報学研究科先端数理科学専攻推薦入試について

京都大学情報学研究科先端数理科学専攻推薦選抜を受けたのでその備忘録を書きます．進路選びの参考になればと思いますが，自明なこと（つまり，募集要項を読めば分かること）以上の本質的な情報は載っていません．

以下公式の募集要項

http://www.i.kyoto-u.ac.jp/admission/application.html

志望理由

情報学研究科の他専攻の院試日程がTHE IDOLM@STER 765PRO ALLSTARSの15周年ライブ*1と 被っていたので先端数理科学専攻にしました．

その上で，先端数理科学専攻にのみ推薦入試制度が設けられており，学部の成績が比較的良かった*2ので推薦入試を受けることにしました．推薦で仮に落ちても一般入試を（追加料金無しで）受けることが出来ます．ただし，推薦で受かった場合は情報学研究科の他専攻を受けることはできません．

先端数理科学専攻で行われている研究・教育内容

知りません*3．先端数理科学専攻の公式サイトか，情報学研究科の募集要項掲載ページにある志望区分案内を見てください．ただし，志望区分案内のpdfは少しだけ古いです．

院試までの流れ

私は京都大学工学部数理工学コースに所属しているので，B4で先端数理科学専攻の研究室に配属となりました．それが決まったのが４月の中頃ですが，その時点で指導教員の方に（もし先端数理を受けるなら）推薦選抜を受けたい旨を伝えていました．

その後，推薦選抜を受けるにあたり（在学中の大学の）教員の推薦書が必要なので，５月の中頃あたりに指導教員のかたに書いていただきました．

今年の募集受付は６月のはじめあたりでした．本番は６月の終わりで，内容は書類審査と口頭試問のみとなります．

院試当日の口頭試問について

口頭試問内容はどうやら人によって（あるいは教員によって）かなり異なる雰囲気なので，その辺りは志望する研究室の教員，または研究室のメンバーに注意深く聞いてみてください．

推薦選抜のメリット

他専攻の院試が８月の初めで一ヶ月ほど遅いので，他の人が院試勉強で忙しい中，声優のオンラインイベントに参加したり*4，映画館に映画を見に行ったり*5，ねんどろいどを組み立てて遊ぶ*6ことができます．

推薦選抜のデメリット

特に思いつきません．

さいごに

推薦選抜があるからという理由で本専攻を志望するのは間違っているとは思いますが，たまたまやりたい研究分野が重なっていた場合に，推薦選抜は大きな選択肢のひとつになるとは思います．

検索結果

ウェブ検索結

*1:2020年7月，アイドルマスターシリーズはアーケード版から数えてなんと15周年を迎えました．私は今までアイドルとプロデューサーが紡いできたその歴史の重さに圧倒されるとともに，これからのアイドルマスターシリーズ，そしてアイマスガールズと呼ばれる女性声優の方たちのさらなる活躍に胸膨らむばかりです．ちなみに15周年ライブはコロナの影響で中止となりました．死．

*2:GPAが4くらいです．GPAの上限が4の大学出身の方にGPA４超えてると言ったらウケるらしいです．

*3:先端数理に限らないとは思いますが，同じ専攻でも研究室ごとにやってることが全く違う（もっと言えば教員ごとに全然違う）ので，ほかの人が何をやってるかはさっぱり知りません．

*4:コロナ禍で仕事が減っている女性声優にほぼダイレクトにお金を送りつけましょう．

*5:千と千尋の神隠しともののけ姫を見に行きました．どちらもとても良かったですが，個人的には千と千尋の神隠しのほうが好きです．サントラも買いました．

*6:https://www.goodsmile.info/ja/product/8721.html

AtCoder ABC 153

解けなかった問題を覚書程度に記す。

ABC153 F

atcoder.jp

水色問題は解けなあかんでしょ......つらい。

けっきょくソートを除いてO(N)で解かなければならない。一番左から貪欲に爆破すればいいのだけれど，その地点での残り体力をいかにして求めるか。例えば爆破したときにそのダメージをqueに入れておいて，毎地点においてqueのfrontと比較して，爆破範囲を過ぎていたら取り除けばいい。するとqueを参照する回数は合計でO(N)で済む。

試験も終わったし，また精進したい。レートが上がらんのよ。

AtCoder ABC 142

詰まった問題を覚書程度に記す。

ABC142 D

atcoder.jp

公約数のうち素数の数を調べればいい。これはO(\sqrt{N})でできる。ただしN=gcd(A,B)。
AとBの公約数は最大公約数の約数である。Nを素因数分解していけばよい。調べるのは\sqrt{N}までで良くて，\sqrt{N}を超えるような素因数は多くても１個しかない。

はじめ「最大公約数以下の素数をを列挙すればいいのかな～～～」と考えていたらそれだとO(NloglogN)かかって解けないことに（TLE出してから）気づいた。こうして期せずして（？）充実した素数ライブラリを作成することができたのだ。はあ。

ABC142 E

atcoder.jp
「ハァ～最小重みマッチングかあ知らんなあ解説読んで実装しよ」とeditorialを見たら一番上に「動的計画法」って書いてあったから一目散に閉じた。

結局bitDPを使えば解ける。Nが非常に小さいことから気づきたいなあ。そもそもABCにネットワークフローは出ないのかしら。いずれ勉強しないとなあ。

ABC142 F

atcoder.jp
実装も考察も何一つ追いつかなかった。完敗。

解き方1

editorialのやりかた。いくつか図を書けばわかるが，一つ閉路をもってきたときに，そこにもし余分な辺が入ってあったとすれば，その余分な辺はショートカットになっている。つまり，その余分な辺を使えばより最適な閉路が手に入る。これを繰り返せばいい。

解き方2

辺をひとつ固定して，startをその辺の終点，goalを始点とする。そこからダイクストラ法を用いて，startからgoalまでの最短路が答えとなる。もちろんstartからgoalまでたどり着けなかったら固定する辺を変える。

最近けっこうABCの問題を解いているのだけれど，時間内にA~Fまで解けるようになる気がしない。どうすればいいのかなあ。

AtCoder ABC 143

解けなかった問題を覚書程度に記す。

ABC143 D

atcoder.jp

解けたけど時間かかった。
a,bを固定してb\le c < a+bなるcの個数を調べればいい。その調べ方について累積和で実装したのだが，二分探索でupper_boundとlower_boundを使えば一瞬だった。実際みんな一瞬で解いてた。

ABC143 E

atcoder.jp

解けたけど（ｒｙ
ワーシャルフロイドを２回使えばいい。INFの値をlong longに対応していなくて詰まった。

ABC143 F

atcoder.jp

解けた.....ならよかったんだけどなあ。難しくない？

考え方としてはたぶん典型的なんだと思う。つまり，
・K枚のカードを選ぶときの，操作を行える最大の回数g(K)
と，
・X回の操作を行うときの，選べる最大のカード数f(X)
は問題として等価であることを見抜かないといけない。K,Xの座標軸を用意するとより直感的。この言い換え力がほしい。

さて，X回の操作を行うときの，選べる最大のカード数を調べたい。例えばおかしの詰め合わせをX個作ることを考える。ただしこのお菓子の詰め合わせには，同じおかしを２個以上いれてはいけない。各おかしiはC_i個あるとする。このような設定のもと，おかしの詰め合わせには最大何個のおかしを入れることができるか？
各おかしiを，X個まであるだけ徴収する。そのあとお菓子の詰め合わせを作り始める。まずはおかし1をX個の袋にひとつずつ入れていく。おかし1がなくなったら次はおかし2をひとつずつ入れていく。それを繰り返す。各おかしはX個以下なのだから，おかしが同じ袋に入ることはない。よって，
f(X)=\sum_{i=1}^N min(C_i,X) / X
となる。
あとは\sum_{i=1}^N min(C_i,X)を効率的に求められればいい。editionalのように式を変形してもいいし，C_iを昇順にソートしておいて，C_iとXの大小の境界をずらしていけば計算できる。

他にもいろんな解法があるみたい。もっと考察すればよかったかも。

AtCoder ABC 144

解けなかった問題を覚書程度に記す。

ABC144E

atcoder.jp

解けたけどめっちゃ時間かかった。
A_iを昇順，F_iを降順でソートすればいいのは直感的。あとはスコアを２分探索すればいい。
２分探索について，lhsとrhsの更新とか細かいところでちょっと詰まった。気を付けないといけない（より一般的なライブラリを作ればいいのかもしれないけれど，まあ注意すればいいだけの話かなあ）。

ABC144F

atcoder.jp

難しい...けれど解説を見れば超簡単。これは頑張って考察したかったなあ。
ルートを消さないときの期待値は大きい部屋から逆にdpすればいい。ルートを消すとき，期待値が最小になるように消すのだから，頂点iから出るルートのなかで一番コストのかかるものを除けばいい。あとはそれを1~N-1について確かめる。O(NM)。

AtCoder ABC 150

解けなかった問題を覚書程度に記す。
atcoder.jp

ABC150F

難しくない？？（ずっと言ってる）

結局XOR演算について正しく理解しているかという話になる。基本的な性質はググれば出てくるが，
a\oplus b=b\oplus a
(a\oplus b)\oplus c=a\oplus (b\oplus c)
a\oplus a=0, a\oplus 0=a
a\oplus c = b\oplus c \Leftrightarrow a=b
a\oplus c \neq b\oplus c \Leftrightarrow a\neq b
くらいだろうか。証明は真理値表より。

a_{k}\oplus x, a_{k+1}\oplus x,\cdots ,a_{k-1}\oplus xとb_0,b_1,\cdots ,b_Nが全て一致すれば言いわけだが，もしこれがとあるkについて成立していれば，すべてのiに対して，a_{k+i}\oplus x \oplus a_{k+i+1} \oplus x=b_i\oplus b_{i+1}が成立している。これは先ほど述べた性質よりa_{k+i}\oplus a_{k+i+1}と一致しているため，このようなkをKMP法を用いて探せばいい。逆を考えることでxを特定できる。
KMP法についてはググったら出てくる。が，結構理解する&実装するのに時間がかかった。でももうライブラリも整備したし，次は大丈夫。なはず。

このままだとeditorialそのままなので何か書く。例えばa_i=0,1，b_i=1,2，x=0,1であり，XORがただの足し算であるような状況を考える。
A:0,0,1,0,0,1,0,1
B:2,1,1,2,1,2,1,1
このとき，条件を満たすようなk,xを探すのにO(N^2)かける人はいない。Aはただシフトして同じものを足しているだけなので，例えばそれらの差分は変わらない。差分を用いてBと効率的に比較できる。
ところでこの状況は一般的である。つまり，2を0と置き換え，a_iをbitごとに別の数列として改めておくと，問題の状況と完全に一致する。

AtCoder ABC 149

解けなかった問題を覚書程度に記す。

ABC149E

atcoder.jp

こういう問題をすっと解きたい。

ナイーブにやるとすると A_i+A_jを上からとればいい。しかしこれは数列の長さがO(N^2)でありソートにも時間がかかるのでできない。困った。

ここで，このN^2個の数列の特別な構造を用いる。例えばあらかじめ数列Aをソートしておけば，A_iを固定した時のA_i+A_jは単調増加の数列となる。つまりその中では2分探索などの強力なツールをO(logN)で実行できる。完全にランダムなN^2この数列のときには，前処理に結局O(N^2logN)かかるので使えない。今回はO(NlogN)で済んでいる。これがミソ。

幸福度がD以上となるようなA_i+A_jのペアの個数を探す。これはA_iを固定した数列に対して二分探索を実行すれば求まるので，O(NlogN)で済む。あとはDについて二分探索することで，幸福度が全てD以上であるようなペアがM個以上あるような，Dの下限を求めることができる。
そのようなDが求まれば，あとは各A_iを固定した時の数列に対し，D以上のものの和を求める。これはS_n=A_1+\cdots +A_nで表される累積和を用いればO(NlogN)で求まる。ただし足しすぎ（Ｍ個以上足してしまう）に注意。

なお，幸福度がD以上となるようなA_i+A_jのペアの個数を探すところで，しゃくとり法も使える。数列Aをあらかじめ昇順ソートした後，テーブルの横軸がA_1,A_2,\cdots A_N，縦軸がA_N, \cdots ,A_1となるように配置すれば結構綺麗な形になる。つまり，各A_iを固定した行について幸福度がD以上となる最小のA_jは，下に行くにつれ単調に右にずれていく。

ABC149F

atcoder.jp

難しくない？？？？？？？？？？？？？？？？？？？？（逆ギレ）
競プロという（一般的に見て）マイナーコンテンツの，年の瀬の，unratedのコンテストの時間内に，こんな難しい問題を解く人が100人以上いるなんて，日本の未来は明るいですよ。ほんとうに。いやほんと。

解き方1

editorialの解き方。まず期待値の線形性からこんな鮮やかに分割できるところがすばらしい。Sの穴あき度の期待値は，Sの頂点数の期待値から，Sに含まれる黒丸の期待値を引いたもの。Sは全ての黒丸を含むように構成しているのだから，後者については\frac{N}{2}となる。問題は前者。
Sの頂点数の期待値について，これまた各辺にバラして考えて，（各辺がSに含まれる期待値の合計)+1となる。ただし空グラフの分は除く。
各辺がSに含まれる期待値は，その辺により木がx_e個とN-x_e個の木に分解されるとして，
(1-(\frac{1}{2})^{x_e})(1-(\frac{1}{2})^{N-x_e})
となる。あとはこれを枝について和を取る。まとめると，
（こたえ）=\sum_e (1-(\frac{1}{2})^{x_e})(1-(\frac{1}{2})^{N-x_e})+1-\frac{1}{2^N}-\frac{N}{2} \\ =\frac{1}{2^N}(N2^{N-1}+(N-2)-\sum_e (2^{x_e}+2^{N-x_e}))

となる。この分母をx，分子をyとおき，x=pM+x', y=qM+y'とする。すると求めるzは，
(pM+x')z \equiv (qM+y') (mod M)
なので，けっきょくxとyはMで割った余りを用意しておけば十分。
z=yx^{-1}であり，x^{-1}=x^{M-2}なので（モジュラ逆数），これでやっと答えが出る。最後の方はこういう問題では当然なのかな。

解き方2

たぶん頂点ごとに見る方がはるかに見通しが立ちやすい（し方針も立てやすい）と思う。解説はいろんなサイトがしているからここには書かないけれど（じゃあeditorial丸写しもするな）。単なる木の再帰を全方位DPっていうみたい。言葉尻が強い。