日報
2023年3月25日 by
2023/3/24(金)

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

ABC288-F: 自力AC。冷静になって式を見たらそう難しくない問題だった。

例えば「2345」の分割を考える。

  • 2×3×4×5
  • 23×4×5
  • 2×34×5
  • 234×5
  • 2×3×45
  • 23×45
  • 2×345
  • 2345

この8通りになる。

上4つは「234」の分割に5をかけたものであることが分かる。つまりX=234のときの答えに最後の桁の数字5をかけたものである。DP[i]:=(前からi文字分を見たときの答え)とすると、DPの遷移は多分こんな感じだろうなという予想がつく。

dp[i + 1] = dp[i] * (x[i] - '0') + /* ... */;

下4つを考える。

  • 2×3×45=2×3×(4×10+5)=(2×3×4)×10+(2×3)×5
  • 23×45=23×(4×10+5)=(23×4)×10+(23)×5
  • 2×345=2×(34×10+5)=(2×34)×10+(2)×5
  • 2345=(234×10+5)=(234)×10+5

このように考えると、X=234のときの答えに10をかけたものにおまけがくっついている感じであることが分かる。このおまけの部分について考える。

dp[i + 1] = dp[i] * (x[i] - '0') + dp[i] * 10 + /* おまけ */;
  • (2×3)×5
  • (23)×5
  • (2)×5
  • 5

いずれも5がかかっているのは良いとしてかっこの中について考えると、これはX=2の時の答えとX=23の時の答えであることが分かる。最後に切れたのが2の後ろの場合、23の後ろの場合、…というそれぞれの場合があってそれに対応している。最後だけ例外。DPの遷移はこんな感じであることが分かった。

dp[i + 1] = dp[i] * (x[i] - '0') + dp[i] * 10;
rep(j, i)
  dp[i + 1] += dp[j] * (x[i] - '0');
dp[i + 1] += x[i] - '0';

これでは$O(N^2)$となってしまいTLEなので、累積和を使って高速化すると$O(N)$になり解ける。

ABC288-E: 解説AC。解説に書いてあるレベルのことは読めばすんなり理解できたのだが、読むまで上手く分析を進められなかった。根本的な言語化能力不足という感じがして厳しい。説明は公式解説通りなので略。

商品iを買うとして、i未満の番号の商品をj個買うならば$C_{i-j}$から$C_{i}$までの好きなところで買える。これには気づいていたのだが、いざDPで良い感じに求める方法を考えるとなると全く分からなかった。「買う集合を固定する」と「その集合を買う方法を考える」という2段階に分けて考えることが出来なかったのが敗因。うまい問題の分割が出来ず頭がぐちゃぐちゃになってしまった。

ある商品をどこで買う～という感じに考えを進めていたのだが、ここからちゃんと進めるとすれば「買える範囲を決定づけるのは何か」→「i未満で買った商品の個数である」→「それを記録すればよい」みたいな感じで考察を進めれば解けていたはず。

「まず集合を固定する」という思考がなかったため、ある商品iを考えるときにi未満の番号の商品を0個買っている場合からi-1個買っている場合までの全てが同時に見えてしまった。多分集合を固定する→集合は何で同一視できるか考える→…みたいな感じで行けると良かったんだと思う。

Vulkanドライバーを自作する方法を調べた。長くてとても読み切れていないが、ここを読めば基本的には全部書いてあるようだ。

https://github.com/KhronosGroup/Vulkan-Loader/blob/main/docs/LoaderDriverInterface.md

Vulkanは複数種のドライバーがあるシステムに対応している。この時の各ドライバーはICD(Installable Client Driver)と呼ばれている。自作したいのはこのICDだ。

Vulkan ICDはjsonファイルとそれにパスが描かれたdllファイルで出来ている。レジストリとか環境変数にjsonファイルのパスが書いてあればそれを通じてVulkan-LoaderがそのICDを読み込むようになっている。

DLLに実装しなければいけない関数がいくつか決まっている。

  • vk_icdGetInstanceProcAddr
  • vk_icdGetPhysicalDeviceProcAddr
  • vk_icdEnumerateAdapterPhysicalDevices
  • vk_icdNegotiateLoaderICDInterfaceVersion

この4つを実装すれば良いようだ。

この辺のことを読んでもあんまり実感が湧かないので手元のPCのVulkanドライバを調べてみた。レジストリを検索してみると確かにVulkanDriverという項目があって、あるシステムフォルダ内のigvk64.jsonというファイルを指している。中身はこんなだった。

{
    "file_format_version" : "1.0.0",
    "ICD": {
        "library_path": ".\\igvk64.dll",
        "api_version": "1.1"
    }
}

igvk64.dllというファイル名があるのでそれを探すと、同階層のフォルダに確かにそのファイルがある。ファイルのプロパティによれば「Vulkan(R) Driver for Intel(R) Graphics Accelerator」とのこと。Intel GraphicsのVulkanドライバらしい。

このDLLをdumpbinにかけて外部公開している関数名を調べてみると、確かに出すべきものが出してある。

     92   5B 007DE330 ctlSwitchMux
     93   5C 007DF780 ctlTemperatureGetProperties
     94   5D 007DF7E0 ctlTemperatureGetState
     95   5E 007DD5D0 ctlWaitForPropertyChange
     96   5F 0053B420 vkGetDeviceProcAddrINTEL
     97   60 0053B400 vk_icdEnumerateAdapterPhysicalDevices
     98   61 0053B3E0 vk_icdGetInstanceProcAddr
     99   62 0053B410 vk_icdGetPhysicalDeviceProcAddr
    100   63 0053B3F0 vk_icdNegotiateLoaderICDInterfaceVersion

ctlなんたらというのはintel Graphicsを細かく制御するための独自のAPIのようだ。こんなものがあるとは知らなかった。

https://intel.github.io/drivers.gpu.control-library/api.html

vkGetDeviceProcAddrINTELはなんだろう…

漫画用のペンというものを興味本位で一回試してみた。

金属のペン先で描く線がどうして太さを変えるんだろうというのが疑問だったのだが、筆圧を強めるとあの先端の切れ込み部分で開くのだな。それで太い線になる。

狙った均一な太さの線を描くのが非常に難しい。そしてちょっとでも迷いがあるとすぐ線が震える。漫勉とかで漫画を描いている人の様子を見るとシュッシュッと小気味良く線を描いていくのが印象に残るが、あれは単にプロだから絵を手早く描いているというのではなくて、ああいう風に素早く描かないと良い線にならないのだろうということが分かった。

専用インクを手に入れ損ねたので墨汁でやった。コピー用紙だと滲んでしまうが、漫画用の原稿用紙だと滲まない。ちゃんと違いがあるんだなあと分かった。

使いこなすのに結構な慣れと修練が必要なのは間違いない。ただ使いこなせたら面白そう。

Categories:

  • アーカイブ