A. Still TBD

0埋めされた数をきちんとscanfで読めるか不安だったのだがどうやらできるらしい． 解答例

また文字列の辞書順比較でもよかったらしい．

B. Digital Gifts

換算して合計する． 解答例

C. Synthetic Kadomatsu

正答率が低い問題．300点とはいえ私の苦手な操作の特性を考える系の問題が解けたのは大きいと思っている． 解答例

まず$N \le 8$に注目して何らかの全列挙を考えるが，すべての操作について全列挙するのは流石に間に合わなそう．ここで延長／短縮魔法は合成魔法の後に使っても同じであることに注目すると，合成結果を全列挙してから延長／短縮を行えばよいことが分かる．全列挙の計算量は$N$が小さいので問題ない．

これにより合成結果が列挙できたから，これに延長／短縮魔法を適用してA,B,Cの候補を選べばよい．これは順序を入れ替えて，A,B,Cの候補を選んでからA,B,Cに揃うように魔法をかければよい．候補をうまく選ぶ方法は割と考えにくそうだが，実はこれも全列挙で間に合う：3重ループでA,B,Cの候補を適当に選んで差を計算すればよい．

別解(editorial)

竹の用法は「Aに使う，Bに使う，Cに使う，使わない」の4通り．よってこの$4^N$通りを試行すればよい．合成回数について：使わなかった竹の本数を$s$とおくと，$n-s$本の竹が合成によって3本になる．一回の合成で竹が1本減ることから合成の回数は$n-s-3$回となる． 解答例

D. Lazy Faith

最近のABC-Dにしては簡単．最初のACコード（綺麗なものは下掲）: 解答例

各$s_i, t_i$をそれぞれ配列$S,T$に入れておく．すると各$x_i$に対して$S,T$を二分探索すれば，左右について$x$に最も近い値$s_l,s_r,t_l,t_r$が得られる．存在しない場合が面倒で，変な関数を作ってしまった．もうちょっと簡潔に書けたとは思うが．

移動の方法は次の8つ：

• $t_l \leftarrow s_l \leftarrow x (\text{if } t_l \lt s_l)$
• $s_l \leftarrow t_l \leftarrow x (\text{if } s_l \lt t_l)$
• $x \rightarrow s_r \rightarrow t_r (\text{if } s_r \lt t_r)$
• $x \rightarrow t_r \rightarrow s_r (\text{if } t_r \lt s_r)$
• $s_l \leftarrow x, s_l \rightarrow t_r$（折り返す）
• $t_l \leftarrow x, t_l \rightarrow s_r$
• $x \rightarrow s_r, t_l \leftarrow s_r$
• $x \rightarrow t_r, s_l \leftarrow t_r$

これはまず$x \rightarrow s \rightarrow t$（直進）と$x \rightarrow s, t \leftarrow s$（折り返し）を考え，左右反転版を考え，最後に訪れる順番が$x \to t \to s$となるものを考えることで列挙した．このうち上4つは次のように纏められる（下4つも纏めると却って複雑になるため行わない）：

• $\min \{t_l, s_l\} \leftarrow x$
• $x \rightarrow \max \{t_r, s_r\}$

これらのコストを愚直に計算して最小値を取ればよい．コスト計算を1箇所凡ミスして1WA．

editorialでは配列の先頭と末尾に-infとinfを加えている．こうすると二分探索で現れるindexが必ず配列の範囲内になるから取り扱いが楽になる．これは覚えておきたい．このテクニックを用いたコード: 解答例

なお私の解法では1クエリに対して4回二分探索を行って$s_l,s_r,t_l,t_r$を求めているのだが，editorialでは「$*_l = *_{r-1}$」という性質を利用して2回に抑えている．確かに$* _r$は$* _r \gt x$を満たす最小の候補であるから$* _{r-1}$は$x$未満であり，これは$* _l \lt x$を満たす最大の候補（本問では$x$と等しくなるような$* _ i$は存在しない）．