所用で東京に行った帰りに、久しぶりに秋葉原に行った。緊急事態宣言も出ることだししばらく秋葉原の姿を見ることは出来ないだろう。

秋月電子はいつも通り混んでいた。前は店員が人数制限をしていたような気がするのだが、今日それが見当たらなかったのは単純に制限人数以下だったということか。大分混んでたけどなあ。

特に特別欲しい部品や作りたい工作なども考えていなかったが、アンプなどいくつかの部品を買って帰った。

千石電商の軒先には非接触体温計とアルコールスプレーが売っていた。こういう流行りものに軒先でちょっと乗っておくのは千石らしい。

---

ABC199に参戦。久しぶりのABC出場だった。

DE凶悪過ぎない？危うくABCで3完になるところだった。Dは3^20が通らないのを確認してから大分悩み、結局2つに分けるbit全探索→分けた片方をさらに制約にかからないよう2彩色できるかを2部グラフかどうかで判定して連結成分の数でパターン数を計算する、ということをした。計算量は多分$O(2^n (m +n))$くらいだと思う。普段使わないアルゴリズム入ってるので計算量評価に自信が無い…

Eは全く有効打が分からず時間切れ。制約からエスパーすればどう考えてもbit全探索の類なのだが、順列に対してbitDPをするやつは巡回セールスマンしか知らなかった(というかむしろそれに発想が縛られていた気がする)ので解説の解には辿り着けなかった。悔しい。選んだやつを左に寄せるものとして考えてしまえばいいのに何故たどり着けなかったのか。

「順列 数え上げ」で検索した結果として挿入DPという概念を新たに知ったのは収穫ではあった。今回には役に立たなかったが、多分いつか役立つだろう。

---

今日はいろいろあってかなり頭を消耗したので、サクマ式ドロップスを目いっぱい口の中に放り込んだ。