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

ABC290-F: なんとか自力AC。

Xを固定して考えたときに直径が最大となる木を考える。

まず次数が1の頂点はどう変えようもないのでとっておく。次数が2以上なら自由に繋いで行ける。直径最大を考えると、次数2以上の頂点を一直線に繋げるのが最も良いことが分かる。残りの辺を次数1の頂点で塞げばよい。

最大直径Lと頂点数Nを固定したとき、それを満たすようなXのパターン数を考える。

木の辺数はN-1であり、各辺は2か所の頂点と繋がることから、次数Xの総和は2N-2であることが分かる。また最大直径Lの両端は次数1、間は全て次数2以上の頂点であり、またそこ以外に次数2以上の頂点は無いことから、次数2以上の頂点数はL-1であることが分かる。残りの頂点N-L+1個は全て次数1の頂点である。

Xの総和から動かせない分の数を引いた(2N-2)-2(L-1)-(N-L+1)=N-L-1を次数2以上の頂点に配分するパターン数は$_{N-L-1}H_{L-1}$となる。また次数2以上の頂点L-1個を選ぶパターン数は$_NC_{L-1}$個であり、この積がXのパターン数である。

あとは直径×Xのパターン数を1≦L≦N-1について全て足せば求まるには求まるが、これでは$O(N)$となってしまうため工夫が要る。

検索しまくった結果「パスカルの法則の一般形」という式が出てきたのでこれで変形すると$N_{2N-4}C_{N-3}+_{2N-3}C_{N-2}$という式になる。これで前計算$O(\max N)$のクエリ$O(1)$で求まる。

パスカルの法則の一般形

絶対もっと簡単にこの答えにたどり着く方法あっただろ～～と思って解説を読んだら主客転倒で寄与を考えていくことで同じような式にまっすぐに辿り着いていた。かしこい。

---

昨日に引き続きNvidiaのVulkanドライバーのdllも覗いてみた。

         15    F 01361980 DrvSetPixelFormat
         16   10 01361BD0 DrvShareLists
         17   11 01361F10 DrvSwapBuffers
         18   12 01361F20 DrvSwapLayerBuffers
         19   13 01362220 DrvValidateVersion
         21   14 017522E0 vkCreateInstance
         22   15 01752AF0 vkEnumerateInstanceExtensionProperties
         23   16 01752B20 vkEnumerateInstanceLayerProperties
         24   17 017532A0 vkGetInstanceProcAddr
         25   18 01356890 vkGetProcAddressNV
         26   19 01855EB0 vk_icdEnumerateAdapterPhysicalDevices
         27   1A 01855ED0 vk_icdGetInstanceProcAddr
         28   1B 01855F20 vk_icdGetPhysicalDeviceProcAddr
         29   1C 01855FB0 vk_icdNegotiateLoaderICDInterfaceVersion
         30   1D 0170CE40 vk_optimusGetDeviceProcAddr
         31   1E 0170CE90 vk_optimusGetInstanceProcAddr

Drv～というのは良く分からない。調べたらGallium3Dというライブラリのドキュメントが出てきた。

https://dri.freedesktop.org/doxygen/gallium/stw__icd_8h.html

vk_icd系統の関数はいいとして、vk_optimus系統の関数はどうやらNvidia独自のVulkanレイヤーVK_LAYER_NV_optimusの実装のようだ。jsonファイルにレイヤーの定義が書いてあった。

igvk64のときと違い、vkCreateInstanceなどが実装されている。どうしてこうなっているのか分からない。そしてvkGetProcAddressNVが実装されている。igvk64でvkGetProcAddressINTELが実装されていたのと似ている。

---

ABC295に出た。

A: やるだけ

B: ボンバーマン仕様と誤読した　うんち

C: ソートしてランレングス圧縮して各値の1/2の切り捨ての総和

D: 区間内の各種類の数字の数が偶数ならばOK、愚直にカウントするとO(N^2)になってしまうので累積和で高速化する。各種類の数字の出現数の累積和をとり、全ての種類の数字について2か所の差がmod 2で0ならばOKなので、0～9の各種類の数字の累積出現数の偶奇を10bitで表して各ビットパタンの出現数を数える。

DPテーブルを更新しつつ答えを足していく感じのコードを書いたが、単純に出現数を数えて最後にnC2を足していった方が楽だと思われる。

E: 自信がないのであきらめた。

F: Sがどこの桁でカウントされるかを考えると良い。問題文のようにS=22を考えると、xxx22でカウントされる場合、xx22xでカウントされる場合、x22xxでカウントされる場合などがありうる。Rを超えるまで数値化したSを10倍していけばよい。Sの1文字目が0の時だけ注意。

文字列Sを作る桁より上の桁と下の桁に分けて考える。Sの下の桁数をkとすると、$A=10^{|S|+k}$として$Ap+S+q$と表せる。ここでpとqを縛る制約を考える。

• $L\leq Ap+S+q\leq R$
• $q< 10^k$
• Sの1文字目が0のとき、$p\geq 1$

このようなp,qの組を頑張って数える。細かい処理は面倒だが、基本的にはLとRの条件から上下限を考えてやればよろしい。これは丁寧に実装すれば$O(1)$で求まるので、1ケース当たり$O(\log R)$で解ける。

G: 解けず。とりあえずSCCやUFを準備してはみたものの、効果的な方針が時間内には出なかった。終わってしばらく経ってからどの頂点も入次数が1でしかも自明にDAGであることに気が付いた。この性質は使えそう。