ゲームライブラリの開発を進めた。CMakeのディレクトリ分けを初めて使ったが、思ったより簡単だった。

---

ABC361に出た。

A: やるだけ

B: 軸ごとに区間交差判定をやればいい

C: 順序に意味は無いのでソートする。連続するN-K個を取ったときの最大最小のみが候補になる。K+1通り全探索すればよい。

D: ありうるパターン数は高々$O(N2^N)$程度なのでBFSで全て探索すればよい。バグり散らかしてAC取れなかった。

E: 木上での戻らなくていい巡回セールスマン問題。少し考察すれば、始点と終点は葉以外ではありえないことが分かる。始点終点が葉で無い場合は戻る経路が無駄に必要になるので、自明に改善の余地が生じる。

始点と終点が決まれば、そこを繋ぐ経路の途中にぶら下がっている木をオイラーツアーで巡回すればよいだろうなということが分かる。この経路の長さは(辺の長さの総和)×2-(始点終点の最短経路長)であることが分かる。辺の長さの総和は変化しようがないので、始点終点の経路長を最大化すればよい。これはDouble Sweepで求まる。

F: (a,b)の組ではなくxを調べろというやつなのであんまり綺麗な方法はパっとは出てこない。bを固定した場合、aの範囲は$N^\frac{1}{b}$程度になる。bが3以上ならaの値は10^6程度なので全探索できる。ということで、とりあえず3≦b≦60程度についてxを全て調べる。b=2については√Nなので最大で10^9程度になり全探索はできない。

そこで、a^2≦Nなるaの範囲を調べる。これは二分探索でよい。そうするとb≧3で作れるxの数とb=2で作れるxの数が手に入るのでこれを足し合わせ、二重カウントしている分を引けばよい。b≧3で作れるxの中から平方数をごり押しで全部見つけて差し引けということになる。これは時間に間に合う。なんか制約から考えたような解法になってしまった。