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

AISING2019-D: 挙動を想像すると、xの近くから順に青木くんがカードをとっていき、同時に上から順に高橋くんがカードをとっていき、どこかでぶつかる。それ以降は残った小さいカードを交互に上からとっていくことになる。なのでこの「ぶつかる場所」「ぶつかった時点で残っている最大のカード」を求められば良さそうだということになる。

青木くんはxに近いものから順に(距離が同じならば小さいものから)とっていくので、ある整数r≧0をとってきて、$[x-\lfloor r/2 \rfloor, x-\lfloor r/2 \rfloor + r)$の範囲に入っているカードの数を数える。これより大きい範囲$[x-\lfloor r/2 \rfloor + r, \infty)$にあるカードの数と比較し、後者の方が数が小さくなればおかしいので、そうならない最大のrを二分探索で見つければ「ぶつかる場所」が求まる。「ぶつかった時点で残っている最大のカード」も同時に求まる。

あとは交互にとっていくはずなので奇数のところだけ(偶数のところだけ)カウントする累積和をあらかじめ求めておけば計算が出来る。

大まかな方針は大して難しくもない問題なのだが、細かいところの詰めがかなり難しい問題だった。何度もWAが出てうんうんうなっていたのだが、二分探索のrの範囲を最大$10^9$にしていたのが間違いだった。xが1でaの範囲が$10^9$に及ぶ場合、rの範囲は$2\times 10^9$にしなければならない。

---

秋月で安めのFPGAがMachXO2以外にもいくつかあることを認識した。FPGAカテゴリに入ってないのでそりゃ知らんわ。扱いとしてはマイコンボードになっている。FPGAとMCUが両方載っているらしい。

https://akizukidenshi.com/catalog/g/gM-17448/

https://akizukidenshi.com/catalog/g/gM-14786/

---

コメントシステムの開発を続けている。「返信一覧」でそのコメントの返信を、「文脈を読む」でそのコメントに至るまでの返信ツリーを表示する感じの仕様にしたのだが、そのコメントから広がった話題を末端まで一息に辿れないのはやはり少しもどかしさを感じる。デフォルトの表示では最新のコメントを全て表示するのでそこでコメントを見つけられるという想定ではあるのだが。

各コメントについて返信の数、返信先コメントの有無を表示すれば改善するかもしれない。全体像が見えない感が与えるストレスが大きい。あとは「文脈を読む」で返信先を同じくするコメントを表示するとかもアリかも。実装が面倒だが。

返信先コメントの返信一覧に飛べるとかにしても良いな。