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

ABC219-E Moat: 見た目に簡単だし実際指針はそう難しくないのだが、細かい部分に手間取った。

まず、各マスが柵の内側か外側かという組み合わせは$2^16$以下なのでこれを全探索することを考える。この方が各辺に柵を張るかどうかを全探索するより明らかに速いし実装も楽。

全ての村は柵の内側でなければならない。これは普通に判定すればよい。

柵の範囲は連結でなければならない。これはUnionFindなどを使えばよい。

自己交差をしてはいけない。これはマスのbit全探索の方式ならば引っかからないかと思ったのだが、チェック模様のような場合にアウトになる。これは実験して初めて気付いた。3×3点それぞれ調べれば良い。

それから、柵の内側とする範囲がドーナツのようになってしまった場合も不正な配置になる。これも実験して初めて気付いた。というかこの問題は問題文の説明がちょっと曖昧な気がする…これは4×4マスを6×6マスに拡張したうえで、UnionFindなどを使って外側の範囲が連結かどうかを調べれば良い。

---

今日は一日OpenXRのサンプルコードを写経しながらドキュメントを読み込んでいた。

• 最初に「インスタンス」を作る必要がある。適宜拡張機能などを指定する。最後は後始末する。この辺Vulkanと大体同じ。
• アプリを動作させるにあたって「システム」を選ぶ必要がある。システムは具体的には「SteamVR」とかそういうやつ。システムは生成消滅するオブジェクトではなく、後始末の必要もない。VulkanのPhysicalDeviceと近い。
• アプリを動作させるには「セッション」を作成して取り扱う必要がある。これは後始末の必要がオブジェクトである。
  • セッションを作成するにはxrCreateSessionを用いる。使用するシステム、使用するグラフィックスAPI(VulkanとかOpenGLとかD3D11,12とか)の情報を指定する必要がある。
  • セッションはいくつかの内部状態を持つ。始めはIDLE状態、そしてREADY,STOPPING,EXITTINGなどに変化する。この変化は「イベント」で伝えられ、xrEventPollで確認できる。
  • READYに変化したらxrBeginSession、STOPPINGに変化したらxrEndSessionを呼ぶ必要がある。Create/Destroyとは別にBegin/Endがあるのがややこしい。
  • EXITTINGおよびLOSS_PENDINGになった場合はアプリを終了する。
• 毎フレームの描画処理としては以下のような形になる。
  • xrWaitFrameで待つ。
  • xrBeginFrameで描画を開始する。
  • 描画処理をやっていく。
  • xrEndFrameで描画を終了し反映する。

毎フレームの描画処理の詳細(スワップチェーンとか)と毎フレームのユーザーアクション状態取得まではたどり着けなかった。また明日。

VulkanとかのグラフィックスAPIの管理にはノータッチなのかなーと勝手に思っていたが、思ったよりがっつり干渉してくる。束縛の激しいタイプらしい。

---

申し訳程度に腹筋をやった。