久しぶりにABCに出た。

A: 計算誤差が怖いので文字列で受け取って整数化

B: 素直に先頭から見て適宜挿入していけばいい。

C: mapなどで種類数を普通に見ていけばよい。

D: 解けず。多分どうにかすると$x$か$y$か$x-y$あたりがNの3乗根くらいで押さえられるんだろうなという予測は立ったので数学的こじつけを探していたのだが、見つけられなかった。こじつけ力が足らんかった。$(x-y)^2=x^2-2xy+y^2<x^2+xy+y^2$なので$N=x^3-y^3=(x-y)(x^2+xy+y^2)<(x-y)^3$で押さえられるらしい。どうせ未知数はあと1つで大した次数でもないので後はどうにかなる。

E: 長さKのパスを切り出すとしたら葉からなので、適当な頂点を根として葉から見ていく。一本道でK個に達したならそこで区切ればよい。問題は複数の子がぶら下がっているノードの場合。ちょうど2つならそれぞれ+自分でK個にできるかどうかを確認して区切る。3個以上なら無条件で不可。

F: 一方の区切りをずらしながらもう一方の区切りの最適値を探す。ここで単調性があるなら尺取りなどが選択肢に入るがなさそうなので頭のいい方法を考える。

列の中で同じ種類のものを線で結ぶことを考える。そしてこの線と区間の区切り線がいくつの点で交わるかを考える。線が交わっているということは区切りの両側に同じ種類のものがあるということになるので、その種類は2回数えられる。そうでないものは1回しか数えられない。ということで、全体の種類数をp、2回数えられる種類数をqとするとp+qとして数えられる。セグ木を使えば区間最大値がO(logN)で求められるが、見る範囲が順次変わっていく都合上更新も必要なので遅延セグ木を使う。

なんか前に見た典型が今ようやく役立った。

---

最近ショッピングサイトの余ったポイントで数学書をどさどさ買い込んでいて、今は「形式論理と計算可能性」を読み進めている。等式論理のあたりを今呼んでいる。結構面白い。

最初の方、集合に関する基礎的な話は大体知っていた。ただ、そこから色々なものを集合で基礎づけるのが面白かった。関数とか、二項関係とか、順序とか。あと直積は知っていたが直和は知らなかった。あとはたまに見るけどちゃんと知らなかったものを知れたのが良かった。集合論の文脈で偶に見る累乗っぽい記法(関数空間)とか、証明木とか。束論は前にちょっと触ったが、これはどう嬉しいのか今回もあまりぴんとは来なかった。

形式論理は最初の方はかったるかったが、それからかなり面白かった。証明可能性とかについて考えるメタ数学を初歩からやってくれたので、まさに自分の知りたいことがここにあったという感じだ。あと構文論・意味論というよく分かんないで放置していた概念もここで理解出来て良かった。構文論によって証明できるものは意味論的に実際正しい(健全性)、意味論的に正しいものは構文論的に証明できる(完全性)という腑分けが分かりやすかった。一般化は好きなので普遍代数みたいな話題もエキサイティングに感じた。

公理が意味論的に正しいことは公理だから所与のものですよ、というものなんだろうか？まず意味論的に公理が正しいと仮定して～みたいな話運びだったが、最初に持ってきた公理が与えた意味論的解釈の上でちゃんと正しいかどうか確かめるみたいなことはちょっとやっておきたい気がする。ただもうちょっとちゃんと読まないと。