A. Anti-Adjacency

選ぶ数の最大値をなるべく小さくしたいことから，1から1つ飛ばしで数を選んでいくのが最適．このとき$k$個目$(k=1,...)$の数は$k$番目の正奇数，すなわち$2k-1$であるから，これと$n$との大小を比較する． 解答例

B. Path

問題文の処理をそのまま実装するDFSを書いた．道に番号を振ってそれぞれの道を通ったかを配列で記録しておけば，3回の移動で「すべての道を」「1回ずつ」通ったかは迷いなく判断可能． 解答例

editorialの解法は漏れを作りそうなため，個人的にはこちらの解法のほうが好ましく思う．

C. When I hit my pocket...

こういう操作の特性を考える系の問題はあまり得意ではない．実験をした． 解答例

本文中にある操作を上からP,Q,Rとする．最終的に円を持っていても利益がないので操作Q,Rの数は同数．すると例えば操作列はPPPQRPPQQRRP...のようになるが，P...PQR...QRと整列して構わない．このときPの数を$p$，QRの数を$q$とすると，$p+2q=k$． このときのスコアは$p+1+(b-a)q$ $= (k-2q)+1+(b-a)q$ $= (b-a-2)q+k+1$．

$q$の係数が負または0，すなわち$b-a \le 2$の場合は$q$が少ないほうがよく，$q=0$としてスコアは$k+1$．そうでない場合は$q$は多いほうが良い．ただし操作Qを行う条件として$p \ge a-1$，変形して$q \le \frac {k-a+1} {2}$が必要であり，$q = \lfloor \frac {k-a+1}{2} \rfloor$としてスコアを算出すればよい．ここで$q \ge 0$にも注意：$q$が負のときは$q=0$とする．

最初は$p$について整理しようとして散々な目に遭った．$q= \frac{k-p}{2}$を用いると$p+1+(b-a)q$ $= p+1+(b-a)(k-p)$ $= p(1-(b-a))+1+(b-a)k$．$b-a \gt 1$のときは$p$の係数が負なので操作Q,Rを増やすべきだが，操作Qを行う条件として$p \ge a-1$．素直に$p=a-1$としたいが，$q$は整数なので$k-(a-1)$の偶奇で場合分け：偶数のときはそのまま$q=\frac {k-(a-1)}{2}, p=a-1$．奇数のときは$q = \lfloor \frac{k-(a-1)} {2} \rfloor$ $(=\frac {k-a} {2})$としてしまうと1操作余るため，それを操作Pに回して$p=a, q=\frac {k-a} {2}$とする．というように，$p$について整理するほうが面倒．

ところでeditorialでは最初から$b-a \le 2$かを見ている．これは操作QR（スコア$+(B-A)$）と操作PP（スコア$+2$)の比較と見れば納得できる：$b-a \le 2$であれば後者を選んだほうがよく，$b - a \ge 2$であれば前者を選んだほうが得をする．

D. Ears

散歩が1回だけという条件を読み落としていたが，そうでなくても解けなかったと思う．

解説(editorialなど)

まず散歩により耳がどうなるかを考えると，これは[$0$]^*-[偶数$\ge 2$]^*-[奇数]^*[1]-[偶数$\ge 2$]^*-[$0$]^*という$5$つの区間が並んだ形になる．逆にこの条件下であれば任意数の石を入れることができる^[2]．

この結果の導出についてはこちらの記事が大変参考になった：始端$\to$終端という一番単純な形から考えてみる．この2点を固定すると，散歩のバリエーションとしてあり得るのは途中箇所に往復を加えたものだけであるから増分は必ず偶数となり，ここから導かれる^[3]． 以下では当該記事も含めた2記事を参考文献としている（後掲する）．

本問で行う操作は次の2つ：

1. 散歩によって位置$i$の石の個数を$b[i]$とする
2. 各$b[i]$に好きな回数だけ$\pm 1$をし，$b[i]=a[i]$とする

各位置$i$が散歩のときどの区間だったのかを考える．先に述べた区間を順に$Z_l,E_l,O,E_r,Z_r$とする． 前の数字が区間$A$であるとすると区間の順序から位置$i+1$は$A$以降の種類のどれかになるはずであり，逆にどれになっても構わない^[4]．

位置$i$が当て嵌まる区間の種類を仮定すると，$a[i]$の値から必要な操作の回数もわかる（先に述べたように$b[i]$が好きなように作れるため）：

• $a[i]$が$Z_l$: $b[i]=0$から$a[i]$回操作を行って$a[i]$にしたとするのが最小
• $a[i]$が$E_l$: $b[i]$は2以上の偶数であることから，
  • $a[i]=0$のとき操作は$2$回（$b[i]=2$として$-2$する）
  • $2$以上の偶数のとき$0$回（そのまま）
  • 奇数のとき$1$回（$b[i]=a[i]+1$とすると，操作で$-1$することで$a[i]$が作れる）
• $a[i]$が$O$: $b[i]$は奇数であるから，
  • $a[i]$が奇数であれば操作は$0$回
  • 偶数であれば$1$回（$b[i]=a[i]+1$とする）
• $a[i]$が$E_r$: $E_l$と同様
• $a[i]$が$Z_r$: $Z_l$と同様

肝心の区間を決めたい．以前に「区間の境界を1つ決めると残りの境界も決まる」というタイプの問題を見たことがあるが今回はたぶんそうはならない．DPができる：$dp[i][K] \coloneqq$「$a[i]$が区間$K$であるときの操作回数の最小値」とすると，先に説明したように区間の遷移を書ける．すなわち区間$K$に対して先の操作回数を$f_K (a[i])$，$K$またはそれ以前の区間の種類を$P(K)$とおくと：

$$dp[i+1][K] \gets \min_{J \in P(K)} \{ dp[i][J] + f_J (a[i]) \}$$

となる．配るDPとして解釈したほうが先の記述に合っているが，配るDPを式で書くときの慣例がよくわからず． 計算量は$K$が5通りなので$O(L)$．考察さえ済めばかなり綺麗に書ける． 解答例

参考

1. https://betrue12.hateblo.jp/entry/2019/02/10/014031
2. http://koba-e964.hatenablog.com/entry/2019/02/10/003030

---

1. 始端=終端のとき長さ$0$もあり得る． ↩︎

2. 怪しい説明：例えば現在の散歩範囲に含まれる区間$[p,q]$に$+4$したい場合を考える．$p$に着いたときに$p \to q \to p \to q \to p$を行えば$+4$かつ元通り$p$に戻る．加えたい数字が変わるところで区間を切ってそれぞれに対して同様の処理を行えば互いに独立になるので大丈夫そうな気がしてくる． ↩︎

3. このように考えたほうが散歩範囲の左端と右端が現れる理由が若干明確になる気はする． ↩︎

4. $Z_l$と$Z_r$，および$E_l$と$E_r$は条件として同じであるから，例えば区間$K$について$K \to Z_l$と$K \to Z_r$ではより自由度の高い左側だけを考えてもよい．とはいえ実行時間的にはわずかに早くなるだけだった（オンラインジャッジで実行時間が計れるかは微妙ではある）． ↩︎