なんか一日家に引きこもってしまった。家の中でラジオ体操ぐらいの運動はしたが。明日はジョギングくらいしたい。

---

関節部の肌の調子がすこぶる悪い。かさかさする。

---

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

ABC126-F: なんとかかんとか自力AC。かなり悩んだ挙句、最終的な答えはギャグみたいな天才構築だった。

まず$K\geq 2^M$のとき、数列$a$は$2^M$のビットを1にすること自体できないので不可能ということが分かる。

それから$M=0$のときは$K=0$のときのみ可能、$M=1$のときは$K=0$ならば可能で$K=1$ならば不可能ということがちょっと実験してみれば分かる。

そして$0\leq K < 2^M$かつ$M\geq 2$のとき、実は必ず条件に合う$a$が構成できる。$M\geq 2$において$0\ xor\ 1\ xor\ 2\ xor\ …\ xor\ 2^M – 1$が必ず0になることに気付くと解ける。

$[0, 2^M)$のうちKを除くものを昇順に並べた数列を$P$, 降順に並べたものを$Q$として、$P, K, Q, K$と並べるとこの数列は条件を満たしている。例えば$M=3, K=2$とすると

(0 1 2 4 5 6 7) 3 (7 6 5 4 2 1 0) 3

といった感じになる。K以外の数字については全てPとQに含まれ、XORで打ち消された結果Kだけを挟むことになるので条件を満たす。Kは数列Qを挟むが、これは$[0, 2^M)$から$K$だけを除いたものの総xorであり、$[0, 2^M)$の総xorが0であることを踏まえるとこの値は$K$になる。

気付けば単純だが、一体どうやって気づけるんだこれ？

---

ABC270に参加した。

A: 2進数。

B: 丁寧に場合分けするだけ。

C: いつも頂点1を根としがちなのでLCAとかが一瞬頭によぎったが、普通にXかYを根にすればいいだけだった。

D: 貪欲法をしたくなったが制約からDP臭がしたので、DPの必要があることに気付けた。ちゃんと貪欲の反例を考えたわけではないが、なんか単純にデカいのから取ろうとすると後の選択肢が狭まるんだろう。

DP[k]:=(残りの石がk個の状態で手番が回ってきた場合のそこから増やせる最大スコア, 最大スコアを得るための最善手)

として管理する。

E: 単純にシミュレーションすると当然TLEなので、リンゴの数が同じバスケットをまとめて考える。それだけだとまだTLEしうるので、まだリンゴが残っているバスケットの数を管理しながら1周分をまとめて計算する。次の1週で終わるという段階になったら単純にシミュレーションすればよい。リンゴの数の種類は高々N個なので$O(N)$。

F: どこからどう見ても最小全域木問題。空港と港を考慮するために、空と海を仮想頂点とする。

• 各島、空、海を結ぶ最小全域木
• 各島、空を結ぶ最小全域木
• 各島、海を結ぶ最小全域木
• 各島を道路のみで結ぶ最小全域木(全域木になっていない場合がありうるので確認処理を入れる)

上の4通り全ての最小値が答えになる。Eよりも簡単。しかししょうもないミスでロスってしまった。

G: 式変形すれば分かる通りの離散対数問題。なんか離散対数は$O(\sqrt{P})$で解けるものらしい。後でupsolveしておこう。よく見るとA≦1の場合は離散対数どころではないので特別扱いしなければならない。