やっておきたい作業があったので久しぶりに完徹してしまった。

---

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

ARC142-C: u+v>3とか言われているが、要するに頂点1,2間以外の全ての2頂点間の距離が測れる。

正直演繹的にどう発想すれば良いのかはよくわからないが、2N回測れるというので、頂点1,2を除く全頂点の頂点1からの距離と頂点2からの距離をとりあえず測ることにしたら上手くいった。

頂点1,2以外の全頂点について、その頂点を経由した場合の頂点1,2間の距離を計算して最短距離を求める。基本的にはこれで答えが求まるが、問題は頂点1,2が隣接していて、どこも経由しないのが最短という場合。

このパターンの場合、最短距離の計算結果は3になる。本当に最短距離が3である場合と実際には隣接している場合(最短距離=1)を見分けるにはどうするか。

本当に最短距離が3である場合、頂点1,2間に2つの頂点が挟まっていて、それぞれ「頂点1からの距離1/頂点2からの距離2」「頂点1からの距離2/頂点2からの距離1」のはずである。そしてその2つの頂点の距離は1のはずである。この条件が満たせていなかったら実際には隣接していると見てよい。

ARC141-B: 最初は数式でいろいろ考えていたが、そういうのはおそらく筋が良くない。

2進数で数字の大小を考える。整数xとyがあるとき、「x<y」⇔「xとyで異なるビットの中で最も上位のビットが x側:0, y側:1」である。これを$B_{i-1}<B_{i}=B_{i-1} \oplus A_{i}$であることと合わせて考えると、任意の$i$について、$A_{i}$の値が1であるビットのうち最上位のビットは$B_{i-1}$において値が0になっているビットである。これにさらに$A_i<A_{i+1}$を合わせて考えると、$A_i$の最上位ビットはどんどんより上のビットにならなければならないことがわかる。$M\leq 2^60$を超える数値は選べないので60を超える長さの数列は構成できず、以上から$N>60$を考える必要はない。

あとは消化試合。$A_i$の選択肢として最上位ビットが$2^0$であるような数値、$2^1$であるような数値、$2^2$であるような数値…の数を計算する。当然Mを超えてはいけないことに注意。あとは最上位ビットがより大きい数値にしか遷移できない、ということを念頭に長さNの数列のパターン数を計算すればよい。