日記 2021/09/18

昨日の日記を書いたあと、寝ようとしたら敷布団を干しっぱなしにしていた。ベランダの窓を開けると雨がざんざか降ってて布団がびっしょびしょになっててすべてが嫌になったので、ベランダの庇の下に取り込んで適当に放置した。

仕方ないので掛布団と毛布を床に敷いて寝たら、固い。起きてもなんか疲れが取れていなくて最悪だった。

夕方までの記憶マジでない。なにしてたっけ? 整数論とか近似アルゴリズムとか勉強してた気がする。一般の巡回セールスマン問題には多項式時間近似アルゴリズムが存在しない(ハミルトン閉路問題が解けてしまうため)が、三角方程式を満たす辺長のグラフなら2-近似アルゴリズムが設計できる、というのが面白かった。

ABC-Fを1問解いた。

F - Distributing Integers atcoder.jp

解法と感想(クリックで展開)

全方位木DPをやる問題。しばらく前に理論を勉強したので、何も見ずに実装できるか挑戦してみた。少しバグらせたが、全体としてはスムーズに実装できた。全方位木DPを学んだときは、こんなものが  O(N) で計算できるのかと驚いた記憶があって、かなりお気に入りのアルゴリズム


21時からABC219に出た。54分5完、274位。 Aは面倒だったのでupper_boundで求めた。Bはやるだけ。Cはソートの比較関数を実装する。Dはナップサック問題のアレンジ。個数が  X, Y 以上になるものを  X, Y にまとめる。Eは面倒だった。堀の内部に入れる位置をbit全探索する。堀の内部が連結で、かつ穴がなければOK。穴がないかの判定はすべての0が外周の0から到達できるかをBFSで調べた。自分が実装している最中に、ほとんど解法を教えているようなclarが公開されてかなりびっくりした。聞く側はあのように聞くしかないだろうが、そのまま公開するのはどうなんだろう……? Eを通したあと、順位表を見てFより解かれていたGを考えたが解けなかった。解説を読むと平方分割で解くらしい。平方分割を使う問題は一度も解いたことがないので、これは無理だったと思う。終了後のTLを見ると、どうも典型90問でほとんど同じ解法の問題が既出だったらしい。勉強不足を咎められて反省。典型90問は埋めよう埋めようと思って放置している状態が続いている。

パフォは2088で、レートは1692から1738に上がった。ここ3回ABCで黄パフォを出せていてとてもいい。もう一段実力が伸びれば黄色になれそうな気がしている。明日のARCも温まりたい。

23:35からCodeforces Round #743 Div. 2に出た。A問題のジャッジに一万年くらいかかっていて、案の定30分くらい経ってunratedになった。C問題までは通したので解法を書く。Aは1の位の数を0にしたあと、各桁とswapして減らしていく。Bはよくわからなかったので、 A の先頭を固定してセグ木上の二分探索で  B の先頭を求めた。Cは閉路判定をしたあとDAGの最長パスを求める。番号が小さい頂点から大きい頂点へは遷移する必要がない。Dは後ろから見る貪欲を投げたが落ちてしまった。TLを見るに累積xorを使ってどうにかするらしい。01列で累積xorを考えるのは何回か見たのに自分の典型引き出しに入っていなかったので、以降意識することにする。upsolveは明日。

こどふぉがunratedになったので高校同期と通話しながらコードネームをやった。今日は全体的に荒れてて楽しかった。

f:id:Focus_Sash:20210919031154p:plain
ねしゃ~がヤバかった回

ちなみに想定解は「オブラート」。どっちもどっち。

寝る。

日記 2021/09/17

今日はなぜか朝7時に起きた。やよい軒で朝食を食べたら満腹になって二度寝してしまった。13時ごろ起きて少し問題を考察したあと、14時半に家を出て本郷キャンパス圏論のゼミに出席した。院試のせいで中断していた圏論ゼミだが、今日から再開。『Category Theory in Context』最後の第6章に入った。今日はKan拡張の導入パートで、いまいちモチベーションが分からなかったところもあったが、どうやら先々の伏線になっているらしい。

ゼミが終わったあと学科同期と駄弁り、図書館でいくつか本を借りたのち帰宅した。家の近くに新しくラーメン屋が開店していることに気がついた。開店記念サービスで500円かつライス無料らしい。ちょうど夕食に悩んでいたこともあって、ものは試しと入ってみた。

まず、うるさい。開店直後で気合が入っているのかもしれないが、狭い店内で5、6人が頻繁に叫ぶとさすがにうっとうしい。そして色々と雑。注文を間違って覚えていたり、料理を出す順番を間違えたりと、何人かの客が迷惑を被っていたのを見た。自分が店に滞在していた短時間でこれだけトラブルがあるのは、部外者としても大丈夫なのかと心配になる。これは完全な憶測だが、店員どうしがやけに親しげなことを見るに、この店はなにかの内輪で運営されていて、「文化祭」的なノリが残ってしまっているのだと思う。まあ開店したばかりだし、良い人たちではあると思うので、この先頑張ってほしい。あと、頼んだライスが一瞬で渡されて、しかもパサパサしてて温かくもなかったんだけど、あれ注文前によそってあったのをそのまま出してるよね? それヤバくない?

ちなみにラーメン自体の味は可もなく不可もなく、という感じだった。この店で食べるくらいなら本郷の『にし乃』や『ねむ瑠』に行くので、もう二度と入ることはないだろう。

家に帰ってからABC-Fを2問解いた。どちらも数え上げ。

F - Enclosed Points atcoder.jp

解法と感想(クリックで展開)

簡単。各  i について、点の部分集合  S\subset T であって、点  (x_i, y_i) S のminimum bounding boxに含まないようなものの個数を求めればよい。これは  x_j > x_i である点のなす部分集合、 y_k > y_i である点のなす部分集合の数の和から、  x_l > x_i, y_l > y_i である点のなす部分集合の数を引く、ということを4方向についてやればよい。 x_l > x_i, y_l > y_i であるような点の数は、 x 座標でソートしてこれまでに出現した  y 座標の値をBITで管理すれば求まる。BITで集合を管理することがかなり多いので、insert(x)get_kth_element()などのインターフェースをライブラリに加えてみた。集合に対する操作が直感的になってうれしい(大差ない気もする)。


F - Surrounded Nodes atcoder.jp

解法と感想(クリックで展開)

これも難しくない。ある頂点  v を白に固定したとき、部分集合  S\subset V であって、 S を含む最小の部分木が  v を含むようなものの個数を求めればいい。これは、 v を根とみたときの  v の子の部分木のサイズを  r_1, \ldots, r_k として、 2^{N - 1} - \sum 2^{r_i} + k - 1 で求まる。すべての頂点について、その頂点を根とみたときの子の部分木のサイズを求める必要があるが、これは全方位木DPっぽくやると O(N) で求まる。


21時からyukicoder contest 314に出た。4完40位。 Aでめちゃくちゃ詰まった。丁寧に場合分けすると、答えが閉じた式で書ける。Bは簡単で、 A_1 以外から始まる項は+-ですべて打ち消すので、 A_1 から始まる  N 個のありうる項すべてについて出現回数を足せばいい。Cは面白い。 x_i = \frac{1-p_i}{p_i} と置くと、 P(\mathrm{even}) - P(\mathrm{odd}) = \prod (1 - x_i) となる。これが負になればいい。確率ちょうど  1/2 のコインを入れてしまうと、そのうち表が出た個数のパリティで全体のパリティが決まってしまうので、他をどう選ぼうとアリスの勝率は  1/2 にしかならず、不適。よって、 x_i > 1 であるようなコインを奇数個、 x_i \lt 1 であるようなコインを任意個選ぶ場合の数が答え。Dは複雑に見えて一本道の問題。制約が小さいので、 x 軸正方向に進む回数を全探索する。これを固定すると、それぞれの方向に進む回数が一意に定まる。あとは重複組合せを使って、それぞれの回数を分配すればいい。どうしても1ケースだけ通らず、8ペナも出してしまった。

AとCとDに時間を取られた。考察はほとんどできていても、細かい式変形が間違っていて無駄足になったり、バグらせたりで解くのが遅い(こどふぉが苦手なのもこれが主要因)。どうしたらいいんすかね。前者はサンプルの計算を同時にすれば軽減できそうだが、後者は……? 真面目に「バグを減らす方法」を模索しないと。

日記 2021/09/15

今日マジでなにもしてない気がする。

12時くらいに起きて、なんかいろいろしてた気がするが、寝ぼけていてあまり記憶にない。卒論の指導教員を誰にするかで悩んだり、『しっかり学ぶ数理最適化』をめくったりしていたと思う。

16時ごろバイトに行って、20時半ごろ帰宅した。夕食を食べてすぐに、Educational Codeforces Round 110のバチャをした。

codeforces.com

Aはやるだけ。Bは偶数を前に持ってきて愚直に計算すればいい。Cで沼にはまった。ついおととい尺取り法の実装について考えていたので、それで解くことに固執してしまい、?の処理で悩んでいた。結局、各 s_i について直前に連なる?の数を前計算しておき、 f(i) = s_iで終わる美しい文字列の数 としたDPで解いた。Dはセグ木の実装を思い出して、番号付けを丁寧にやればいい。E以降はあまり見れていないので、後日upsolveする。

こどふぉはAtCoderに比べて実装が面倒な問題が多くて、速度が出ないのが悩み。まあ毎日のようにバチャをしていれば慣れるだろう。

24時に卒論配属の抽選作業があって、無事希望の教員に配属された。かなり解析よりのことをやるので、関数解析の勉強をする必要がありそう。結構わくわくしている。

TDPC-Rを解説ACした。強連結成分分解したあとのDAG上で、2本の(点素とは限らない)パスが通る頂点の重みの和の最大値を求める問題。この「点素とは限らない」の部分をどう処理したらいいか全くわからなかったので、解説を見た。DAGの推移閉包を取ることで、「2本の点素とは限らないパスが通る頂点の重みの和の最大値」を「2本の点素パスが通る頂点の重みの和の最大値」に言い換えることができる。最長パスのDPをプロトタイプに、点素性を保ってDPをする。頂点 iの重みを w_iとする。 f(i, j) = (iで終わるパスとjで終わるパスの重みの和の最大値)として、 f(i, j) = w_i + w_j と初期化し、トポロジカルソート順で  i \lt j であるようなペアについてのみ遷移を行うことにする。 i \lt k \lt j であるような頂点 kに遷移してしまうと、パスの点素性が保証されないので、これは無視することにして、 j \lt k であるような kについてのみ、 f(i, k) f(j, k)を更新していけばいい。グラフすべてが1点につぶれるような場合を同様に扱うために、全頂点へ辺が伸びている超頂点を事前に追加しておくと楽。

atcoder.jp

日記 2021/09/14

日記を書くのは3ヶ月ぶり。ゆるして。

今日は夢見が悪く、珍しく早く目が覚めた。夢の内容は「院試に実は落ちていた」というもの。(なぜか)合格したものと思っていたら、10日前のメールに「不合格」と書いてあったのを見つけて、震える手で親に「実は受かっていなかった」というラインを送った。眠りから覚めたときの安堵は計り知れないものだった。

図書館で借りた本の返却期限の延長を忘れていて、延滞してしまっていたので、本郷まで返却に行った。ついでに工学部6号館の図書館でなにか借りようと思っていたが、学生証の入った財布を忘れてしまったのでいったん家に帰る。二度手間。家で昼食を食べたあと睡魔に襲われたので昼寝をしたところ、またよくわからない夢を見た。夢はギリシャでふと目が覚めるところから始まる。近くには親がいて、どうやら家族で海外旅行に来たらしい。親が誰かと何かを話しているあいだに抜け出して、薄暮ギリシャの町を探索する。道端のレストランに入って食事をすると、そこの看板娘になぜか気に入られて、帰りしなに唇を奪われた。いい夢でした。

15時半ごろに家を出てふたたび本郷に向かい、6号館図書館と書籍部を物色する。図書館ではりきぽんに勧められたMotwaniの"Randomized Algorithms"など、アルゴリズムや数学の本を数冊借りて、書籍部では気になっていた『トルコのもう一つの顔』を買った。この本はひろゆきとのレスバトルで話題になったF爺こと小島剛一氏の手による、多民族・多言語国家トルコの内情の記録である。いかにもミーハーなチョイスとは自覚しているが、面白そうなので買ってしまった。

17時半ごろ本郷を出て帰路を急いでいると、突然友人1から電話がかかってきた。友人2の家で飲まないかと誘われたので、家に荷物を置いてから向かう。この飲みに参加していたため、予定していたECRバチャは中止にした。俺はFAKE。学科民とestisさん、ごめん……。

以前からPCディスプレイを買おう買おうと思っていたが、友人宅に置いてあった27インチディスプレイを見て可及的速やかに買うことを決断した。想像の10倍くらい画面が大きくて、コーディングや文章作成がものすごく捗りそう。いまの住居にはディスプレイを置く机がないので、引っ越したあとにはなるが。

23時ごろ家に帰って、TDPCで解けずにいたP問題からS問題の解答をすべて開けた。どれもかなり難しくて、粘っていても思いつけた気があまりしない。まあ典型を学ぶ場として割り切ることにする。

リハビリなので短め。明日からも続くかは未定。

東京大学 情報理工学系研究科 数理情報学専攻 合格体験記

タイトルにあるように、東京大学情報理工学系研究科の数理情報学専攻の2022年度夏院試に合格しました。この記事には、自分の記録用に、そして来年以降同専攻を受験する人のために、院試の対策期間から合格発表まで、自分がどのような道程を辿ったかを記します。

1行でまとめると

共通数学で大失敗しても受かった。

はじめに

院試の選考過程は大部分がブラックボックスなので、どの要素がどれくらい合否に影響しているかはわかりません。以下に書いてある、各ステップの合否への影響などは、あくまで筆者の推測にすぎません。

この記事を院試対策の参考にする場合の注意点を2つ挙げます。

  • 筆者は内部生であること。
  • 試験の形式が例年と異なること。

まず1点目について。自分は東京大学工学部の計数工学科数理情報工学コースに所属している、いわゆる内部生です。数理情報学専攻に所属する先生がたの授業を受けてきました。そのため、院試に向けて押さえるべき事項はある程度分かっていましたし、授業資料や演習問題へのアクセスもありました。これは、特に口述試験において、外部生に比べて大きなアドバンテージになったと思います。

2点目について。今年の数理情報学専攻の入試は、2020年度以前(コロナ禍以前)とも、2021年度入試とも異なる形式で行われました。来年度以降、はたしてコロナ以前の形式に戻るのか、それとも現在の形式が引き継がれるのか、全くわかりません。

試験形式

今年度の数理情報学専攻の院試は、以下の5ステップで構成されていました。

  1. TOEFL iBT
  2. 書類選考
  3. レポート課題
  4. 共通数学(筆記)
  5. 口述試験

以下で、それぞれのステップについての解説と、自分がどのように対策し、どのような結果が出たかを詳述します。数理情報学専攻のホームページに、過去問や出願の手続き、勉強の指針などが掲載されているので、まずはそちらを参照すると良いと思います。 www.i.u-tokyo.ac.jp

TOEFL iBT

出願に際して、TOEFLスコアを提出することが求められます。コロナ禍以前は、大半の人が団体でTOEFL ITPを受験していましたが、今年は受験者が各々でTOEFL iBTを受験し、スコアを提出する必要がありました。スコアが正しく提出できているか確認できないので不安になりますが、書類に不備があった人には連絡が来たそうなので、おそらく心配しなくても大丈夫です。スコアはほとんど合否に関係ないともっぱらの噂です。

対策

自分は英語が好きで日頃から勉強していたので、リーディング・リスニング・スピーキングについては特に対策を行いませんでした。ライティングは、学科の友人と数日に一度時間を測って過去問を解き、互いに添削しあっていました。TOEFLのライティングは時間制限が厳しいので、この演習でだいぶ慣れることができました。ただ上で述べたように、そもそもTOEFLスコアが合否に関係があるかすら怪しいので、対策の優先順位は低めだと思います。

結果

R30/L29/S22/W28で合計109点でした。我ながらすごいです。

書類選考

出願のさいに提出された書類をもとに選考が行われます。今年は書類選考課題として、志望理由・研究テーマの記述と、数理情報学において重要な事項の説明をする課題が課されました。課題内容の詳細は上記のホームページを参照してください。

対策

言われたとおりに書きました。背伸びして理解の怪しい難しめのことを書いてしまいましたが、そんなことをするメリットはおそらく皆無です。自分がしっかり理解している事項を書いたほうが絶対に良いと思います。

書類選考で落とされている人も数人いるので、きちんと文献を引いて正確なことを書くように努めるべきです。逆に、それが正しくできていればまず落とされないと思います。

結果

無事通過しました。

レポート課題

2020年度以前は専門数学の試験がありましたが、コロナ禍の影響で2021年度はそれがなくなり、代わりにレポート課題が課されました。今年度は専門数学の試験を行おうと思えば行えた(じっさい、数理情報学専攻いがいの情報理工の専攻は行っていた)にもかかわらず、レポート課題が課されたことから、この形式を積極的に選択する理由があるのだと推測しています。2021年度のレポート問題は上記のホームページで公開されています。

対策

言われた通りに、数式・図表を多めに盛り込んだレポートを書きました。書類選考課題同様、書籍・論文を可能な限り参照して、正確に書けば問題ないと思います。自分は読みやすいレポートになるように文章の順番や図表の見せ方に気を使いましたが、それがどれくらい評価されたかはわかりません。レポート課題については、以下のnoteがとても参考になります。残念ながら、自分がこれを発見したのは提出後でした。このノートによれば、レポート課題はかなり配点が重いらしいので、十分時間をかけて納得のいくものを仕上げるべきです。

note.com

結果

そこそこ納得のいく出来のものが書けました。提出したあとから「あそこはこうしておけばよかった」と何度も思ったので、理想的には期限よりだいぶ前に完成させて、ブラッシュアップに時間を割けると良いと思います。

共通数学

情報理工学系研究科全体で行われる数学の筆記試験です。線形代数・解析・確率統計の3分野からそれぞれ大問1つずつ出題されます。昨年はコロナ禍の影響でこの試験も行われませんでしたが、今年は例年通り実行されました。オンライン受験者への配慮から、試験は大問1つずつに分けた形で行いました。これも過去問がホームページで公開されています。

対策

学科同期と週に1回過去問を解いて解説しあうゼミをしました。これがなかったら共通数学なんて対策する気が起きるわけもないので、ありがたかったです。問題の難易度じたいは高くなく、誘導も丁寧なので、冷静にやれば満点が十分狙えます。線形代数・確率統計は高校数学および大学1年生レベルのことがわかっていれば解くのに支障はないと思います。自分の場合、この2つは得意だったので、試験直前は微分方程式複素解析フーリエ解析など解析分野を扱った授業を重点的に復習していました。共通数学は過去問演習をして抜けているところを適宜復習するのが一番コスパが良いと感じます。

結果

大大大失敗でした。 普通にやれば満点を取れると思っていた線形代数で、ひどい勘違いをして大問をまるまる1つ吹っ飛ばしました。試験終了の鐘と同時に勘違いに気がついたときは、「血の気が引く」とはこういうことなんだな、と実感しました。全員が満点を取ってそうな試験で、その3分の1を失う。え、俺落ちるの? どうしよう。しかもあと2つ大問残ってる。顔面蒼白になりながら、なんとか自分を鼓舞して残りの大問2つは完答しました。帰り道で同じようにやらかした友人と落ちた場合の動きについて話し合ったのはいい思い出です(その友人も無事受かっていました)。

口述試験

共通数学の約20日後にオンライン口述試験が行われました。ここでは、『提出されたレポート課題解答や数理情報学の専門知識に関する』質問に回答します。

対策

レポートに引用した論文を全部読もうとしたのですが、そんなことをする時間も能力もありませんでした。高度な内容まで答えられなくとも減点はされないだろう、という言い訳のもと、これまでに受けた授業で、それら論文の前提知識になっているようなことをしっかり復習しました。また、自分のレポート課題を再読して、想定問答集を作って答えられるように勉強しました。終わったあとから考えると、やはり計数工学科の授業内容、およびホームページに記載されている「勉強の参考となる図書」の内容をしっかりと理解するのが一番重要だと思います。

結果

レポート課題に関する質問には7割程度、専門知識に関する質問は9割程度答えられました。前者では、「これは聞かれるだろうな」というようなことが順当に聞かれたのに答えられず、自分の準備不足を呪いました。少なくともレポートに書いた内容については隅から隅まで正しく説明できるように準備しておくべきです。後者については、共通数学の失敗もあってものすごく緊張していたので、冷静になればすぐ答えられるような命題の証明で詰まってしまったのが心残りです。

全体の感想

院試、マジでカス。自分の場合は7月から9月まで、なにをしていても院試への不安が頭の片隅に根を張ってました。選考過程がなにも見えないし、どの要素がどれくらい重いかもわからないし、助けてくれって感じでした。合格発表の直前、自分は髪を切ってもらってたんですが、不安すぎて美容師さんとほとんど話せなくて、「お疲れですか?」とか聞かれてました。今から疲れる予定です。

こんなカスな試験で落とされたらカスなので、無事受かってよかったです。共通数学以降、メンタルが不安定だった自分に「どうせ受かってる」「大問3つ中2つ取れてれば大丈夫だろ」と言ってくれた友人たち、そして通話で愚痴を聞いてくれた某友人に、感謝……。

院試受けるとき、先輩とかに「よっぽどのことがなければ受かるよ」みたいなことを言われると思います。個人的には、いやそれよっぽどのことが起きたら落ちるってことじゃん、ってずっと思ってました。自分のやらかしってよっぽどのことに感じちゃいますよね。周りの人が何言っても、拭えない不安は拭えません。もうそれは仕方ないので、完璧な出来で試験を終えるか、それができなければ合否に怯えて合格発表を待ちましょう。今回自分が発見した不安の紛らわせ方の一つは、それをより大きい不安で塗りつぶすことです。具体的にはホラゲです。合否へのドキドキとゲームへのドキドキが混ざってよくわからなくなるので、やってる間は不安を忘れられました。『Doki Doki Literature Club!』がおすすめです。あとは上にも書きましたが、だれか友人に感情を全部ぶちまけるといいです。少なくともその友人と話してるあいだは気が楽になりました。

質問や、もっと詳細に書いてほしいことがあったら、コメントか筆者のTwitter(@Focus_Sash)までお気軽にどうぞ。これから院試に挑む皆さんの幸運を祈ります。

日記 2021/06/09

11時ごろ目覚める。家に食材がピーマンしかなかったので、近くのスーパーで補給した。13時から演習の授業を受ける。テーマは耐量子暗号、具体的には格子暗号のさわりの話を聞いた。Minkowskiの定理を使った平方剰余の相互法則の証明など、面白い話もあったが、1時間ちょっとでは浅い理解しかできない。一応授業時間は16時までなのだし、もっと長く話してもらいたかった。

演習が終わったので、スーパーへ歩いているときに解けた問題を実装する。

C - 暗闇帰り道 atcoder.jp

解法と感想(クリックで展開)

難しかった。最小値の最大化なので、とりあえず二分探索の判定問題を考える。上下左右に移動できるのに加え、あるマスに至るまでの時間に依存して移動できるマスが変わるので、単純に値を確定していくことができない。「あるマスに早く到着して悪いことはない」という考察から、BFSで解くことができることがわかる。あとは実装するだけなのだが、なんと10WAも出してしまった。ずっと誤差や二分探索の終了条件など、浮動小数点演算に関係するもので落ちているのだと思っていたが、実際は「ゴールに移動できない場合 -1 を出力する」のを忘れていただけだった。浮動小数点の扱いに自信が持てていないため、ミスの原因を特定するのが遅れてしまうことがとても多い。なんとかしたい。


その後、いくつか目についた青diffを解いた。

E - Oversleeping

atcoder.jp

解法と感想(クリックで展開)

これは面白かった。電車と高橋くんは周期的な行動をするので、余りに注目すると、中国剰余定理で解ける形になっていることがわかる。はじめ二分探索のような「アルゴリズム的な」解法を探索してしまい、余りに注目することを思いつくのにかなり時間がかかってしまった。数学ができる人ならすぐ思いつけそう……。


E - Patisserie ABC 2

atcoder.jp

解法と感想(クリックで展開)

実装がものすごく大変だった。 [x^M](x + \cdots + x^n)^3 は疎な多項式 1/(1 - x) の積になるので、累積和で  i,j,k の和が  M になるものの個数を求める。あとは頑張る。多項式・形式的冪級数ライブラリをそろそろ作るべきかもしれないと思っている。ほかの人のコードを見たところ、後半はもっと単純なループで書けたようだ。あとで書き直す。


その後家を出て、池袋のジュンク堂で欲しかった本を購入した。買ったのは

  • 『図書館の大魔術師』5巻×2冊
  • ゆゆ式』10巻
  • 進撃の巨人』34巻
  • 『マツリカ・マハリタ』『マツリカ・マトリョシカ
  • 『なめらかな世界と、その敵』
  • 『本と鍵の季節』

の8冊。『図書館の大魔術師』は本当にすばらしい作品。世界観・絵・キャラ・ワクワク感などがすべてとても高い水準にある。この記事を読んでいる人たちにもぜひ手に取ってもらいたい。

家に帰って食事をしたあと、1問だけ解いた。

B - 花束

atcoder.jp

解法と感想(クリックで展開)

問題じたいはただの線形整数計画問題だが、またしても大量にWAを出してしまった。原因は2つの直線が交わらないケースを完全に失念していたことで、本当にダメ。


青diffのsolvedはこれで225問中101問となった。ついに3桁到達! 6月中に埋めきりたいと思っていたが、少し厳しいかな……。

このあと今日買った本を読みつつ、実験の作業を少しして、寝る。

日記 2021/06/08

およそ10日ぶりの日記である。ここしばらく、大学院入試の出願作業に追われていて、日記を書く心の余裕がなかった。なんとか志望教員を選び、無事に出願を終えることができた。提出から一日経っても「こっちにしておけばよかった」という後悔の念が湧いてこないので、いま考えられる限りでは最善の選択ができたと思う。

さて、今日は朝8時ごろまで演習の課題をやっていた。テーマは機械学習、とくにEMアルゴリズムMCMCで、これまたあまりやる気の起きない分野である。競プロに逃避しつつグダグダと問題を解いていた。やる気が起きないとは言ったものの、「すごい魔法」という程度の認識だった機械学習が、授業や演習を通して、統計学を土台に泥臭くパラメータ推定を頑張る、地に足のついた分野であると実感できた。この例が示すように、応用数学の幅広い分野を基礎から学ぶことができるのは計数工学科の大きな長所であると思っている。

朝ごはんを食べて就寝。14時ごろに起床して授業を受けた。授業を聞きながら青diffの問題を眺めていると、しばらく前に解けなくて放置した問題の解法が一瞬で見えたので実装をした。

E - Second Sum atcoder.jp

解法と感想(クリックで展開)

大きい数字から順に見ていって、すでに数字の入っている場所をsetで管理するだけ。どうして過去の自分はこれが解けなかったんだ? 実装で少し苦労した。解説を見るに、番兵を置いておくとよかったらしい。番兵を置くのは思いつけないことが多いので、意識したい。


途中から授業に集中できなくなってきたので、TopCoderのコーディング環境を整えることにした。ArenaのJava Appletがなぜかダウンロードできなかったり、CLionでなぜかコンパイルが通らなかったり、いろいろと苦労したが、なんとか環境が完成した。今のところSRMに参加する気はないが、SRM Div. 1 Easy Hunting を解こうと思っている。

19時ごろまで暇だったので、少し前に買った『マツリカ・マジョルカ』を読み終えた。マツリカは自分の性癖に刺さるタイプのキャラではなかったが、ストーリーは好き。もう少し主人公の成長後の姿が見たかったという気持ちもあるので、第二巻以降に期待。

郵便受けを見に行くと、Amazonで注文した本が届いていた。ところがいざ開封してみると、新品で注文したにもかかわらず汚れや折れがある。当然すぐに返品手続きをした。Amazonで本を注文するとこういったことが起こりうるとは聞いていたが、いままで自分が被害にあったことはなかったので気にしていなかった。今後は可能な限り店頭で買うことにする。

19時から、学科同期とZoomで話す会に参加した。20時半ごろに解散となったので、夕食を食べたあと、青diffを何問か埋めた。

C - タコヤ木

atcoder.jp

解法と感想(クリックで展開)

 0 以上 M 以下の広義単調増加数列の数」がぱっと出てこなかった。良くない。これがわかればあとはやるだけ。


C - だれじゃ

atcoder.jp

解法と感想(クリックで展開)

やるだけ。setに vectorを持たせたのは初めてかもしれない。


E - Yutori

atcoder.jp

解法と感想(クリックで展開)

初めさっぱりわからなかったが、 C 日以上離れているブロックに分割してみたら、ブロックごとに貪欲でいいことに気がついた。実装がかなり大変だった。実はブロックごとではなく、全体で貪欲をしてしまってよい。解法がわかった瞬間に実装に集中してしまって、その解法を「広げる」方向にまったく意識が向かなかった。反省。


本番で解けなかったABC204-Fをupsolveし、ちょうどいい機会だったので行列ライブラリも作った。あと40分あれば解けたかもしれない。Eで詰まったのが悔やまれる……。

atcoder.jp



青diffのsolvedはこれで225問中96問となった。直近2回のABCで青diffを通すことができていて、青diff埋めの効果を感じている。