今日はなぜか朝7時に起きた。やよい軒で朝食を食べたら満腹になって二度寝してしまった。13時ごろ起きて少し問題を考察したあと、14時半に家を出て本郷キャンパスで圏論のゼミに出席した。院試のせいで中断していた圏論ゼミだが、今日から再開。『Category Theory in Context』最後の第6章に入った。今日はKan拡張の導入パートで、いまいちモチベーションが分からなかったところもあったが、どうやら先々の伏線になっているらしい。
ゼミが終わったあと学科同期と駄弁り、図書館でいくつか本を借りたのち帰宅した。家の近くに新しくラーメン屋が開店していることに気がついた。開店記念サービスで500円かつライス無料らしい。ちょうど夕食に悩んでいたこともあって、ものは試しと入ってみた。
まず、うるさい。開店直後で気合が入っているのかもしれないが、狭い店内で5、6人が頻繁に叫ぶとさすがにうっとうしい。そして色々と雑。注文を間違って覚えていたり、料理を出す順番を間違えたりと、何人かの客が迷惑を被っていたのを見た。自分が店に滞在していた短時間でこれだけトラブルがあるのは、部外者としても大丈夫なのかと心配になる。これは完全な憶測だが、店員どうしがやけに親しげなことを見るに、この店はなにかの内輪で運営されていて、「文化祭」的なノリが残ってしまっているのだと思う。まあ開店したばかりだし、良い人たちではあると思うので、この先頑張ってほしい。あと、頼んだライスが一瞬で渡されて、しかもパサパサしてて温かくもなかったんだけど、あれ注文前によそってあったのをそのまま出してるよね？ それヤバくない？
ちなみにラーメン自体の味は可もなく不可もなく、という感じだった。この店で食べるくらいなら本郷の『にし乃』や『ねむ瑠』に行くので、もう二度と入ることはないだろう。
家に帰ってからABC-Fを2問解いた。どちらも数え上げ。
F - Enclosed Points
atcoder.jp
解法と感想（クリックで展開）
簡単。各 について、点の部分集合
であって、点
が
のminimum bounding boxに含まないようなものの個数を求めればよい。これは
である点のなす部分集合、
である点のなす部分集合の数の和から、
である点のなす部分集合の数を引く、ということを4方向についてやればよい。
であるような点の数は、
座標でソートしてこれまでに出現した
座標の値をBITで管理すれば求まる。BITで集合を管理することがかなり多いので、
insert(x)やget_kth_element()などのインターフェースをライブラリに加えてみた。集合に対する操作が直感的になってうれしい（大差ない気もする）。
F - Surrounded Nodes
atcoder.jp
解法と感想（クリックで展開）
これも難しくない。ある頂点 を白に固定したとき、部分集合
であって、
を含む最小の部分木が
を含むようなものの個数を求めればいい。これは、
を根とみたときの
の子の部分木のサイズを
として、
で求まる。すべての頂点について、その頂点を根とみたときの子の部分木のサイズを求める必要があるが、これは全方位木DPっぽくやると
で求まる。
21時からyukicoder contest 314に出た。4完40位。
Aでめちゃくちゃ詰まった。丁寧に場合分けすると、答えが閉じた式で書ける。Bは簡単で、 以外から始まる項は+-ですべて打ち消すので、
から始まる
個のありうる項すべてについて出現回数を足せばいい。Cは面白い。
と置くと、
となる。これが負になればいい。確率ちょうど
のコインを入れてしまうと、そのうち表が出た個数のパリティで全体のパリティが決まってしまうので、他をどう選ぼうとアリスの勝率は
にしかならず、不適。よって、
であるようなコインを奇数個、
であるようなコインを任意個選ぶ場合の数が答え。Dは複雑に見えて一本道の問題。制約が小さいので、
軸正方向に進む回数を全探索する。これを固定すると、それぞれの方向に進む回数が一意に定まる。あとは重複組合せを使って、それぞれの回数を分配すればいい。どうしても1ケースだけ通らず、8ペナも出してしまった。
AとCとDに時間を取られた。考察はほとんどできていても、細かい式変形が間違っていて無駄足になったり、バグらせたりで解くのが遅い（こどふぉが苦手なのもこれが主要因）。どうしたらいいんすかね。前者はサンプルの計算を同時にすれば軽減できそうだが、後者は……？ 真面目に「バグを減らす方法」を模索しないと。
