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

ARC140-C: 自力AC。実装はややこしいが方針は気付けば簡単だった。

まず、Aの長さはN-1なので嬉しさの上界は自明にN-1である。検討してみると、条件次第ではこれが達成できるのでその場合はそれが最適になる。

嬉しさがN-1だとすると、Aの値は1,2,3,…N-1でなければならない。$|P_{N-1}-P_N|=N-1$なので、$P_{N-1}=1,P_N=N$か$P_{N-1}=N,P_N=1$のどちらかである。仮に前者とすると、$P_{N-2}=N-1$である。以下同様に考えていくと、Pは$\lceil N/2\rceil$から始まってジグザグと振幅の大きくなっていく波のような形、もしくはその反転の2通りしかありえないことが分かる。

ということで、初期値Xが$\lceil N/2\rceil$もしくは反転パターンである$\lceil (N+1)/2\rceil$であるパターンでは嬉しさN-1が達成可能で、そうでない場合は嬉しさN-2が上限である。検討すると、嬉しさN-1が達成できない場合でも必ずN-2が達成可能で、これが最善であることが分かる。

最善なパターンはジグザグの振幅のパターンとその反転パターンだと書いたが、これを貼り合わせることで、初期値Xを抜き出しても残りで嬉しさN-2を達成する順列が構成できる。

具体的なやり方としては以下のようになる。嬉しさN-1を達成する順列のうち(N+1-X)が早く表れる方をQ、遅く表れる方をRとする。「X」「(N+1-X)が現れるまでのR」「N+1-X」「(N+1-X)が現れた後のQ」をこの順で繋ぐとこれは初項Xかつ嬉しさN-2の順列になっている。実験的にがちゃがちゃやったらこの方法になった。これでこの問題が解けた。

QとRがどっちがどっちになるかというのを当初計算で判定できないかと足掻いていたのだが、バグりまくるし、どうせO(N)なのだから愚直に両方で(N+1-X)の位置を求めて判定するようにした。時間制限に間に合うのならより確実なやり方にスッと切り替える、みたいなのは意識的にやっていきたいところだ。

---

筋トレをした。今日は腹筋。なんか上手く効かせられなかった気がする。

---

鬼トレをやった。

---

新サイトのデザインを進めた。見た目としては大体満足できる形になったので、パフォーマンスチューニングを行っていきたい。

軽く調整してみたところ、やはりと言うべきか、Webフォントがボトルネックになっている。速さを求めるならWebフォントは捨てた方が良さそう。