今週の胎界主を読んだ。イノッチ…まぁそりゃ荒れるわな。
- 恋人
- 球体の才能
- 補償金
全部なかった(もしくはなくなった)と。
下に見てた相手に球体で反撃されてるのが哀しすぎる。
今日解いた競プロの問題。
ABC266-G: 自力AC。最近はよわよわな問題をACしてstreak稼ぎをしてばっかりだったのでたまにはまともなdiffの問題を解いておく。
RGという組が重要なので、Rの連続部分の右端に注目すると良さそうだな、と考えられる。するとRをいくつの連続部分に分けるかというのをいったん固定して考えてみると良さそうな気がする。それぞれの連続部分の長さは1以上でさえあればあまり問題にならない。
p個の連続部分があるとして、そのうちk個の右隣はGでなくてはならず、またp-k個の右隣はBまたは何もない状態でなければならない。また、Rの連続部分でない部分、p+1か所の隙間にはGとBが並んでいる。
このような並べ方のパターン数は頑張ると求められる。
まずp個の連続部分に分けるパターン数は$_{p}H_{R-p}$通り。$R$ではなく$R-p$なのはそれぞれ最低でも長さ1を持つため。
ここから先は場合分けが必要になる。一番右のR連続部分の右隣に何もない場合と何かある場合だ。言い換えれば文字列がRで終わる場合とR以外で終わる場合ということになる。
R以外で終わる場合
p個のR連続部分のうちk個は右にGを配置し、p-k個は右にBを配置する。RGにする場所の選び方は$_pC_k$通り。余ったGとBの数はG-k個とB-(p-k)個になる。p+1か所への配分方法は$_{p+1}H_{G+B-p}$通り、並べ方は$_{G+B-p}C_{G-k}$通り。
Rで終わる場合
p個のR連続部分のうちk個は右にGを配置し、p-k-1個は右にBを配置する。一番右の1個は端になるので右に何も置かない。RGにする場所の選び方は$_{p-1}C_k$通り。余ったGとBの数はG-k個とB-(p-1-k)個になる。一番右にはGとBを置けないので、GとBを置く隙間はp+1か所ではなくp箇所になる。配分方法は$_pH_{G+B-(p-1)}$通り、並べ方は$_{G+B-(p-1)}C_{G-k}$通り。
ということで$k\leq p \leq R$について$_{p}H_{R-p} \times (_pC_k \times _{p+1}H_{G+B-p} \times _{G+B-p}C_{G-k} + _{p-1}C_k \times _pH_{G+B-(p-1)} \times _{G+B-(p-1)}C_{G-k})$を足していけばよい。前計算をしておけば二項係数は$O(1)$で求められる。
電光掲示板が一応完成した。表示は固定だが、とにかくプログラムで指定した文字列が右から左へ流れる。そしてモバイルバッテリーでそれなりに持つ。
屋外での視認性も確認した。さすがに直射日光に当てると厳しいが、日陰なら結構見やすい。
あとはオプション的な機能の実装をしていく。
- UART通信で表示される文字列を更新(このままではせっかくFT232を実装した意味がない！)
- スイッチで表示をON/OFF(使わないときはOFFにしたい)
- 明るさを切り替え(省電力化のため)
- バッテリ残量を表示(いつまで持つのか分からないのはアレ)
とりあえず仮完成はしたので反省点を並べたい。電子工作はあまり完成物の数をこなしていないので明確な反省みたいなのをちゃんと溜められてない気がしている。
- 部品の配置に加えて電源ラインをあらかじめ考えておくべきだった。細い隙間に無理やり配線を通した感じになっている。正直こなした数が足りないせいで上手く見積もれてない気はするが。
- LEDマトリクスとバッテリコネクタのせいでねじが一部はめられなくなっている。ねじは通るがナットが回せない場所もある。後でねじ穴を使うつもりがあるなら、部品配置の時点でナットを含めてはまるかどうか確認しておくべきだった。
今日摂取したコンテンツ。
https://research-er.jp/articles/view/114176
こんな現象いったいどうやって見つけてくるんだろう…
なかなか面白かった。トランプみたいなのが当選した理由としてとても分かりやすい。しかし白人の貧困層というのは、人種とかそういうのに関係なく単純に「格差と貧困」みたいな話として取り上げられたりしないんだろうか。まぁ特に分かりやすいカワイソーな理由が無いのに貧困層ということになると記事が書きにくいみたいな話なのか。
Categories: 未分類