無敵時間さんのTシャツが届いた。とてもうれしい。どこに着て行ったら面白いだろうか。

---

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

ARC147-B: 解説AC。途中まではちゃんと考察が進んだのだが。

ソートされているには全ての$i$について$i$と$P_i$の偶奇が一致している必要がある。操作Aを1回行ったとき、偶奇が一致していない箇所の数は2つ増えるか減るか変わらないかのいずれかである。操作Bを行った場合は変わらない。ということで偶奇が一致していない箇所の数/2だけ操作Aを行わなければならないことが分かる。

操作Aで偶奇の一致した箇所を2増やすには、操作Aの対象となる2か所両方について偶奇が不一致でなければならない。ということで操作Bを用いることで適切に不一致な箇所を移動する必要があるのだが、そのためのアルゴリズムが上手く組めなかった。なんかちょっとずつ移動して不一致箇所と出会い次第操作Aを適用するような$O(N)$のアルゴリズムを組んだが、目論見通りに動作するものではなかった。

$O(N^2)$かけて単純に端に全部寄せても$10^5$に収まることを見抜けなかった。これが今回最大の失敗。最悪ケースで$N/2$個を端から端へ移動させるとしても、移動距離は$N/2$で1個あたりの操作回数は$N/4$、全部移動しても$N^2/8$なので$N=400$でも20000回程度で収まる計算になる。

全てについて偶奇が一致したら、あとは$i$が偶数の箇所と奇数の箇所それぞれにおいてバブルソートをすればよい。ここは自力で分かった。

「定数倍が軽い可能性を考える」みたいなところを、メモリや時間以外においても意識した方が良いのかもしれない。

---

部屋のゴミの片づけなどをした。なんか放置されてた箱とか。

---

久しぶりにジョギングした。1.5km。久しぶりなので無理はしない。

---

放置していたTang Nano 9Kをちょっと動かしてみた。とりあえずこのページに従ってLチカが出来た。