ジョギングした。4.2km。なんか脚の付け根が痛む。準備体操とか整理体操とかいつも億劫がって全然やらないのだが、そのツケだったりするのだろうか。

---

ARC164に出た。

A: 3進法に直して桁の総和を取ればありうるKの最小値になる。Kがこれより小さいならアウト。あとは各3^mを3^(m-1)*3に分解するたびに項の数が-1+3=+2増えるので、最初に計算した最小値とKの偶奇が一致していればOK。K≦Nは保証されているので判定の必要はない。

式の単純な間違いで無駄に時間を溶かした。

B: 始点を任意にとっていいことに気付けず解けなかった。ある1辺だけ白白または黒黒で、あとは全て白黒交互であるようなサイクルを一カ所見つければよい。Unionfindでできる。

C: Aliceは裏返した時の点数の下がり幅が一番大きいカードを裏返す。Bobも裏返されたときの点数の下がり幅が一番大きいカードを取る。priority_queueを使えばよい。

D: 解けず。あとで冷静に考察してみたら思った以上に簡潔に書けた。

まず単純に全ての電荷の配置が確定している場合のp(s)について考える。左から順に+が出現したら高さが1上がる、-が出現したら1下がるというぎざぎざのグラフを書く。色々はしょるとこのグラフの絶対値の総和が答えになることが分かる。

これを効率的に計算する方法を考える。結論としては、高さhとその時点までの絶対値の総和sだけ持って遷移すればよい。+が出たら(h, s)→(h+1, s+h)、-が出たら(h,s)→(h-1, s+h)と遷移する。

総和も同じように考えればよい。DPs[i][h]:=(i番目まで見たときに高さhであるようなパターンでのsの総和), DPc[i][h]:=(i番目まで見たときに高さhであるようなパターン数の総和)とすると

• +が出たら DPs[i+1][h+1]+=DPs[i][h]+h*DPc[i][h], DPc[i+1][h+1]+=DPs[i][h]
• -が出たら DPs[i+1][h+1]+=DPs[i][h]+h*DPc[i][h], DPc[i+1][h-1]+=DPs[i][h]
• ?が出たら両方

としてやって、DPs[2N][0]が答えになる。