ジョギングをした。4.2km。

今日なんとなく気付いたことなのだが、自分は走るときにどこか少しブレーキをかけている。

足という人体の構造によるのか靴の構造によるのか、着地の衝撃はばねのようにしてある程度推進力に出来ることが感覚的に分かった。しかし自分は、速すぎるとよろしくないという無意識の感覚があるのか、それを足で吸収してしまっている。これを踏まえて、今日はちょっと意識的にブレーキをかけないように、ばねの作用を出来る限りそのままに利用して走ってみた。

案の定、後半疲れて失速した。おそらく速く走ると脚を動かす量も大きくなるからだと思う。しかし走り心地として悪くなかった。もっと体力を付けて長い距離を疲れず速く走れるようになりたい。

---

ARC162に出た。大負け。単純に頭の回転速度が足らなかった。素早く考察する！分かったことは素早く整理する！

A: 人Nが折り返したとき(=すべての人が折り返したとき)、人は数字の順にコース上に並んでいると考えて良い。

簡単な場合としてPi=iの場合を考える。ここで人iに区間賞を受賞させようと思った場合、人1～i-1をスタート付近で留まらせて人i+1～Nをゴール付近で留まらせ、人iを一瞬でゴールからスタートまで運べばよい。これで間違いなく区間賞になる。

Pi≠iのとき、上の手法を適用しようとすると追い抜かれる人が出てくる。そのような人はダメ。そうでなければ必ずいける。定式化すれば、すべてのj>iについてPj>PiならばOKでそうでなければアウト。

B: 左端から順に1,2,3…を入れていくことを考える。もし1の位置が最右でなければ一回の操作で行ける。最右の場合、ひとつずらせば同じように出来る。これを繰り返せば2N回以内で大体揃う。

ただしこれをやっていくと、最後にN, N-1が来て揃えられない場合がある。実験してみた感じ転倒数っぽいので転倒数を計算した。転倒数が奇数なら不可。そうでないなら2N回以内で必ず揃う。厳密な証明はめんどいのでしていない。

Nは最大でも10^3なので、操作にはたっぷりO(N)かけてよい。

C: クソギャグ問題。気付くのに大変遅れてACできなかった。しかも制約がゆるいことにも気づくのが遅れて考察のスピードが鈍った気がする。

まず、大まかな方針としてDFSで部分木ごとに見て行くとよい。ここの部分木のmexをKにすると決め打ってそれが出来るかを考える。

空欄の数の偶奇とか色々考えたのだが、全部無意味で、空欄が0か1か2以上かしか考えなくてよい。2以上ならBobが必ずKを書き込めるので不可。0のとき、選択肢はないので普通にmexを見ればよい。1のとき、Aliceが必ず1個自由に数を追加できると考えればよい。その上でKと一致させられるか見ればよい。

ギャグに気付いてから頑張ったが、空欄が1個のときの場合分けが捌ききれずに終わった。