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

ABC216-G: 解説AC。牛ゲーを勉強した。

牛ゲーは数列の2項の差に関して条件があるときに使えるものだが、今回は「ある区間の1の数」に関して条件があるので、これは累積和に関する問題に言い直す。こうすることで2項の差の問題に言い換えることができる。またもちろん累積和が求まれば元の数列は一意に容易に復元できる。

求める数列Aの値は0か1なのでそこも考える必要があるが、「累積和の2項の差が0以上1以下」と考えればこれは牛ゲーのやり方で処理できる。

次に、牛ゲーは「最大化問題を最短路問題に言い直す」ものだが、今回は1の数を「最小化」したいのでそのままでは使えない。そこで「0の数の最大化」に言い直すことで最大化問題に言い換えることが出来る。

以上を踏まえることで牛ゲーのテクニックが適用できる形に言い換えることが出来た。あとはやるだけ。

これは牛ゲーを知っていたとしても適用可能とは気付けなかった気がするなあ。区間の話を累積和を使うことで2項の差に言い換えるのはだいぶ技巧的に感じる。「2項の差」だけでなく「区間の和」などについても適用できるのは今回学べたとして、他にも牛ゲーに帰着できそうな問題はありそうだ。数列の任意の項同士に不等式による条件が設定できるということは順番がほぼ意味を持たないので、問題文に数列が出てくる必要すらない。グラフだったりするかもしれない。もう、「良く分からない条件がいっぱいある」「何かの最大化/最小化問題である」まで見たら牛ゲーを疑ってよさそうだ。フローかもしれんが。

---

PICO4において自作のVRアプリがスリープ状態を跨ぐと動かなくなってしまうという問題があったのだが、原因を調べた結果簡単に解決した。

原因はALooper_pollAllなどのAndroid専用のイベント処理をやっていなかったことだった。イベント処理ってかなり必須のものだと思うのだが、逆に今までよくこんなのもやらないで動いてたな？