ここ最近午前の活動がマンネリ化してきているので、午前にやっていた活動を午後に持って行ってみた。午前はC++の勉強、電子工作、創作の企画練りをした。なかなか良かったと思う。

---

ずっと勉強から逃げてきたC++のconceptを理解した。思ったより単純だった。

個人的な思い込みとして何か「でかい複雑な機能が1つ追加された」と思っていたのだが、どちらかというと「小さい機能が3つ追加された」という形に近かった。

• concept(型→bool値 なる関数)
• requires式(bool値を返すただの定数式)
• requires節(bool型の定数式の値によってテンプレート引数を制約する機能)

実態はこの3つの機能が別々に実装されたという形になっている。当初の目的である「テンプレート引数の制限」はrequires節によって行われるものであり、conceptとrequires式は極端に言うとただの補助でしかない。実はconceptやrequires式を使わずとも、requires節と従来のテンプレートテクニックによる定数式(std::integralなど)だけでやっていくこともできたりする。

そして、conceptとrequires式は必ずしもrequires節のために使わなければいけない訳ではない。結局ただのbool値を返す定数式でしかないので、どんなところでも利用しようと思えば利用できる。

requires式は「式の妥当性評価」という、これまでのC++ならばSFINAEなどで頑張るしかなかったことを簡単に表現できるようになっているので普通にrequires節以外でも使いどころはあるかもしれない。

---

今日解いた競プロの問題。

ABC216-F 自力AC。AとBという異なる数列から同じインデックスのやつをとってくるという面倒くさそうなのにひるんだが、ぐっとにらんだら$A_i$でソートして「最大値の順序をインデックスに対応付ける」という発想が降ってきたので実装したらACした。良問。

最初はdp[数列のi番目まで調べた結果][max Ai][選んだbiの和] := 条件を満たすiまでのパターン数の和

という愚直なDPを書いてそれを高速化できないかと思っていたのだが、3次元である時点でどう高速化しようが負けなので頑張ったら上記の発想が降ってきた。どういうソートの仕方なら答えに影響しないのかちゃんと考えるのは重要。

ABC221-E 自力AC。$1\leq i \leq k$なる$i$について$A_1 \leq A_i$かと最初誤読してしまったのだが、サンプルが合わないので即座に直してACした。

ABC222-E 自力AC。ちょっと特性を考察したら「ある辺が何回通られるか」を計算すればいいことが分かったのでどうにかした。LCAの算出とか5穣年くらいぶりにやったのでなれなかった。

キーエンスプロコン2021-C 自力AC。最初ちょっと迷ったのだが、がんばってDPするとどうにかなる。

DP後の値を2/3にする必要があったのがちょっと面白かった。

---

今日摂取したコンテンツ。

https://twicomi.com/manga/e3_noguchi/913693963118190594