geam1113’s diary

主にAtcoderのコンテストの備忘録を書きます。AtCoder緑と水色を行ったり来たりしています。

AtCoder Beginner Contest 287 備忘録

コンテストページ: https://atcoder.jp/contests/abc287
コンテスト中AC: A〜E

C - Path Graph?

パスグラフのとき、両端の次数は1で、それ以外は2です。また、連結成分の数はただ1つになる必要があります。
以上から、以下がパスグラフである条件です。

  • 次数1の頂点がちょうど2つ存在し、その他の頂点の次数は全て2
  • 連結成分がただ1つ

上は、次数をカウントしていくことで判定でき、下はUnion Findにより、判定できます。

実装: Submission #38391709 - UNIQUE VISION Programming Contest 2023 New Year (AtCoder Beginner Contest 287)

D - Match or Not

S,Tの先頭及び末尾からの何文字目までが一致させられるかをあらかじめ計算しておき、その情報を合体させます。

具体的には、bool型の配列L,Rを以下のように定義します。

L_i:=Sの先頭からi文字目とTの先頭からi文字目までを一致させられるならtrue、一致させられないならfalse

とし、同様に、先頭を末尾に言い換えたものをRとします。
ここで、便宜上L_0 = R_{N+1}=trueとします。

x=kの場合には、一致できるかをL_k \wedge R_{k+1}として判定できます。

L,Rは、先頭または末尾の端から順に調べていき、i番目のS_i,T_iについて、

  • S_i \neq ? \wedge T_i \neq ? \wedge S_i \neq T_i

となったらそれ以降は全て一致させられなくなるので、全てfalseで、それまでは全てtrueとします。

実装: Submission #38402444 - UNIQUE VISION Programming Contest 2023 New Year (AtCoder Beginner Contest 287)

E - Karuta

少し前の問題でRolling Hashを使っていたので、Rolling Hashで解きました。

S_ij文字目までのハッシュ値H_{i,j}とします。

全てのi,j\ (1\leq i \leq N,\ 1\leq j\leq |S_i |)について、H_{i,j}の個数を連想配列でカウントします。

改めて、i番目の文字列について、H_{i,1},\ H_{i,2},\ \cdots ,\ H_{i,|S_i|}の個数が全体で何個あるかを調べていき、ハッシュ値の数が2以上であるものは自分以外にもそのハッシュ値を持つ文字列が存在することを示しているので、その中で最大のものが答えになります。

実装: Submission #38475994 - UNIQUE VISION Programming Contest 2023 New Year (AtCoder Beginner Contest 287)

(コンテスト後に実装見直し)

AtCoder Beginner Contest 286 備忘録

コンテストページ: UL Systems Programming Contest 2023(AtCoder Beginner Contest 286) - AtCoder
コンテスト中AC: A〜E

D - Money in Hand

公式解説とは異なる方法でO(NX)とする方法を書いておきます。

Sliding Window Agrregationを使います。

DP遷移の一例を示します。
A_i = 4, B_i = 2, X=24の時、i-1番目のj\ mod\ 3 = 0のDP値を集めて配列とします。
C=\{dp[i-1][0],\    dp[i-1][4],\ dp[i-1][8],\ dp[i-1][12],\ dp[i-1][16],\ dp[i-1][20],\ dp[i-1][24]\}

同様にi番目のj\ mod\ 3 = 0のDPテーブルの更新を考えると

dp[i][0] \leftarrow C_0

dp[i][4] \leftarrow C_0 \vee C_1

dp[i][8] \leftarrow C_0 \vee C_1 \vee C_2

dp[i][12] \leftarrow C_1 \vee C_2 \vee C_3

dp[i][16] \leftarrow C_2 \vee C_3 \vee C_4

dp[i][20] \leftarrow C_3 \vee C_4 \vee C_5

dp[i][24] \leftarrow C_4 \vee C_5 \vee C_6

このように、j\ mod\ A_iが等しいものだけを集めると、最初の方を除いては値を求めるための区間は、長さが一定のまま1つずつ右にずれていくだけということがわかります。

そのため、スライド最小値を一般化したSliding Window Agrregationが使えます。
半群やモノイドが乗せられるはずだったと思いますが、実装はモノイドにしました。モノイドの型はbooleanを、二項演算は論理演算のORを、単位元はfalseにしておけば良いです。

コンテスト中の実装: Submission #38204795 - UL Systems Programming Contest 2023(AtCoder Beginner Contest 286)
Sliding Window Agrregationの実装: Submission #38292225 - UL Systems Programming Contest 2023(AtCoder Beginner Contest 286)

E - Souvenir

Nが小さいので全点対間最短経路をワーシャル・フロイド法によって求めることが可能です。
お土産の価値も最短経路の求め方と似たような感じで求めることができます。
二次元配列Cを、

C[i][j]:=i,j間のお土産の価値

とおきます。
初期値として、

  • 頂点u,v間に有向辺があるなら、C[i][j] \leftarrow A_v
  • 頂点u,v間に有向辺が無いなら、C[i][j] \leftarrow 0

このようにして求めていくと、ワーシャル・フロイド法の最短距離のテーブルdistの更新の際、

  • dist[i][j] \gt dist[i][k]+dist[k][j]なら、C[i][j]\leftarrow C[i][k] + C[k][j]

  • dist[i][j] = dist[i][k]+dist[k][j]なら、C[i][j]\leftarrow max(C[i][j], C[i][k] + C[k][j])

と更新すれば良いです。
なお、このままだと始点の価値が足されていないので、s_i,\ t_iの始点の価値を足して、C_{s_i,\ t_i}+A_{s_i}が求める価値です。

実装: Submission #38211470 - UL Systems Programming Contest 2023(AtCoder Beginner Contest 286)

AtCoder Beginner Contest 285 メモ

コンテストページ:AtCoder Beginner Contest 285 - AtCoder

コンテスト中AC:A〜D
コンテスト後自力AC:E,F

D - Change Usernames

ユーザ名の重複を取り除き、番号を振り直したものをs=\{s_0,\ s_1,\ \cdots\ ,\ s_m\}とします。

s_iからs_jに、s_jからs_kに変更することを考えます。
配列の途中に要素を挿入する場合に末尾要素から順に後ろにずらしてスペースを作りますが、同じように、s_js_kに変更してからs_is_jに変更すれば、2つの変更を達成できます。

達成できない場合を考えると、例えば、s_iからs_jに、s_jからs_kに、s_kからs_iにする変更は不可能です。

これらの関係を有向グラフの問題にすると見通しが良くなります。

sの各要素を頂点、s_iからs_jに変更したい場合にs_iを始点、s_jを終点として有向辺を張ります。ユーザ名の変更は、有向辺を一回辿ることと考えることができます。

この有向グラフに閉路があると、移動順を決められず、達成できないことがわかります。逆に閉路がない場合、トポロジカルソートして、末尾から順に移動すれば達成できます。

従って、このグラフに閉路存在するかを判定すればよいです。
コンテストでは、AtCoder Libraryの強連結成分分解を使いました。
実装: Submission #38053494 - AtCoder Beginner Contest 285

E - Work or Rest

連勤する日数に対して、得られる生産量は固定です。

例えば3連勤すればA_1+A_2+A_1が生産量です。
これは、Aの累積和をとっておき、連勤する日数の偶奇で場合分けすることでO(1)で計算できます。

この問題では、以下のように考えることができます。

i連勤に必要な日数をw_ii連勤で得られる生産量をv_iとする。合計日数がN以下となるように選んで連勤する時、得られる生産量の最大値を求めよ。但し、各連勤は何度してもよい。

これは個数制限の無いナップサック問題と同じです。連勤日数は最大でN-1日なので、O(N^2)で解けます。

注意が必要なのは、i連勤に必要な日数はi日ではないということです。
前か後ろの一方にのみに休日を入れておけば全体として矛盾がないので、i+1日としておけば良いです。
実装: Submission #38131229 - AtCoder Beginner Contest 285

F - Substring of Sorted String

S_l,\ S_{l+},\ \cdots ,\ S_rを、S_{l,r}と表現します。

S_{l,r}Tの連続する部分列であるための条件は以下の2つです。

  • S_{l,r}が昇順に並んでいる
  • 文字をabc順に並べた時にS_{l}より後ろ、かつ、S_rより前の文字c_iについて、S_{l,r}に含まれるc_iの個数とS全体に含まれるc_iの個数が等しい

1つ目は自明だと思うので、2つ目を具体例で示します。

S_{l,r}=aabccdfとします。
まず、S_l = a,\ S_r = fS_{l,r}の先頭と末尾ですが、これはSに何個含まれていても良いです。例えば、Tの連続する部分列が、

aaabccdfffff

であったとしても、

a|aabccdf|ffff

という感じに分けることを考えればS_{l,r}に一致させることができることがわかります。

反対にafの間の文字、b,c,d,eS_{l,r}に含まれる個数とS全体に含まれる個数が一致しなければいけません。
もし、S_{l,r}以外の箇所にこれらの文字が含まれていた場合、昇順ソートしてTにした時に、S_{l,r}の間に1文字以上挿入されることになり、一致しなくなります。

次に、これらの計算方法です。
まず、昇順に並んでるかどうかですが、これは順序付き集合Uで、以下を管理します。

  • Sの連続する部分列であって、その部分列が昇順であるように(最長に)分割した時の、各部分列の開始位置

例えば、S=aabcdacfdaは、aabcd|acf|d|aと分割できるので、U=\{1,6,9,10\}となります。

l,rが与えられたとき、U上を二分探索し、l及びrより大きい最小の整数(upper_bound)が一致すれば、S_{l,r}は昇順です(実装では、\inftyUに入れておけば扱いやすいです)。

文字変更クエリでは、Uの中身を変更していきます。変更される可能性があるのはx,x+1の2つです。文字変更によって、新たに昇順になったか、または昇順でなくなったか、に応じて、Uからx,x+1を追加または削除すればよいです。

値の追加、削除、二分探索が可能なデータ構造(C++ならset)を用いれば各クエリでO(logN)で処理できます。

次に、2つ目の条件ですが、これは値の1点更新を伴う区間和を処理できればよいので、Fenwick Treeで対応できます。

なお、2個目のクエリで全ての文字について、その個数を求めたとしても、文字種が26しかないので計算量としては問題ないです。

実装: Submission #38099915 - AtCoder Beginner Contest 285

AtCoder Beginner Contest 282 備忘録

コンテストページ: HHKB Programming Contest 2022 Winter(AtCoder Beginner Contest 282) - AtCoder
コンテスト後にAC: A〜C
コンテスト後にD,Eは自力で解けず 。Fは自力AC

D - Make Bipartite 2

コンテスト中はよくわからない勘違いでACできませんでした。

まず、連結成分に2部グラフでないものが含まれていた場合、辺追加後のグラフも2部グラフにならないので0です(これが抜けていました)。以下、全ての連結成分が2部グラフであるとします。

まず、連結成分内同士を繋ぐ場合の辺の本数を求めます。
連結成分の1つCについて、頂点を2つの独立集合U=\{u_1,\cdots ,u_k\}V=\{v_1,\cdots ,v_m\}に分けます。これは頂点を2色彩色した場合に同色となる頂点集合と同じです。

UまたはV内で辺を繋ぐと2部グラフでなくなります。UVの頂点同士はどのように繋いでも2部グラフのままです。

Uの任意の頂点uについて、Vの全ての頂点と辺を繋ぐことが可能なので、合計m本の辺を繋ぐことができるわけですが、既に辺が存在する場合はその分を引かなければなりません。

つまり、um-N(u)本の辺を繋ぐことができます。但し、N(u)uから出ている辺の本数とします。
従って、連結成分内で繋げる辺の本数はi=1,\cdots ,kについて、u_iで繋げる辺の本数の総和を求めればよいです。

次に、連結成分間です。
任意の連結成分C_i,C_j間では、全ての頂点間の辺を繋ぐことができます。もし、頂点を2色彩色した場合の同色同士を辺で繋いだとしても、一方の連結成分の色を全て反転させればよいです。

よって、連結成分C_1,\cdots C_{i-1}の頂点数の合計がSであり、C_iの頂点数が|C_i|だとすれば、S\times |C_i|本の辺を繋ぐことができます。
以上から、連結成分間について、連結成分の頂点数の和を順次計算しながら、辺の本数を求めていくことができます。

実装: Submission #37366599 - HHKB Programming Contest 2022 Winter(AtCoder Beginner Contest 282)

E - Choose Two and Eat One

公式解説を見ました。
こういう問題はどうやったら気づけるのか難しいところです。 AtCoderの過去問 (ネタバレ注意)で、似たような感じの木で考える問題もありました。これも葉から順に操作していくというものでした。
1つずつ選んでいく感じの問題は木を疑ってみると良いのかもしれません。

F - Union of Two Sets

公式解説そのままだったので、解法の詳細は省略し、解法に至った経緯だけメモしておきます。

まず、全ての区間の組を得ようとした場合、N^2個必要です。ワーストケースのN=400の場合だけを考えても、M\leq 50000という制約を越えるため、全ての区間を列挙することは不可能です。

そこで、例えば、区間の数をNlogN個に落とすことができれば、解決できそうです。
そんなわけで、区間の長さを2分の1ずつ小さくすることを考えます。

N=10を例にします。10/2=5なので、長さが5の区間について考えます。 全ての長さ5の区間をカバーするためには、始点を1つずつずらす必要があります。そのため、

[1,5] [2,6] [3,7] [4,8] [5,9] [6,10]

が必要です。
これを眺めたところ、ここから適切に区間を2つ選ぶことで長さ5〜10の区間すべてをカバーできることがわかりました。
一般化すると、

長さiの閉区間について、[1,i],\ [2,i+1],\ \cdots , \ [N-i+1,N]から適切な2組を選ぶことで、長さ1,2, \cdots ,2iの全ての区間を作ることができる。

また、各長さの区間の個数はN個以下となることから、全ての区間を列挙してもNlogN個以下となります。
以上から、1\leq 2^i \lt Nのすべての区間を列挙しておけば、クエリに答えられます。

クエリでは、区間の長さ以下となる最大の2の冪乗について、その指数が必要になります。
これは、ビットが1である最上位のビットが何番目かを得ればよいです(__builtin_clzが使えます)。

実装: Submission #37417443 - HHKB Programming Contest 2022 Winter(AtCoder Beginner Contest 282)

AtCoder Beginner Contest 281 参加記録

コンテストページ: https://atcoder.jp/contests/abc281
コンテスト中AC: A〜D
コンテスト後にEをAC(自力)

D - Max Multiple

  • N,K,Dが小さい
  • 倍数はmodの情報があれば良い

これらからDPだろうと判断しました。
情報としては、

  • 何項目までを考慮したか
  • 選んだ項の総和のmod\ D
  • 選んだ項の個数

が分かればよいので、

dp[i][j][k]:=Ai項目までを考慮し、選んだ項の総和のmod\ Djであり、選んだ項の個数がkであるときの選んだ項の総和の最大値

遷移は以下のとおりです。

  • A_{i+1}を選ばない場合
    dp[i+1][j][k]\leftarrow max(dp[i+1][j][k], dp[i][j][k])

  • A_{i+1}を選ぶ場合
    dp[i+1][(j+A_i)\ mod\ D][k+1]\leftarrow max(dp[i][(j+A_i)\ mod\ D][k+1], dp[i][j][k]+A_i)

初期値は、dp[0][0][0]\leftarrow 0としておき、その他は-1などで埋めておけばよいです。

なお、dp[i][j][k]-1の場合は遷移元としないようにする必要があることに注意します。

答えは、dp[N][0][K]です。

提出コード: Submission #37160568 - AtCoder Beginner Contest 281

E - Least Elements

コンテスト中multisetで解こうとして結局だめでした。コンテスト後にWavelet Matrixで解けました。

A_{i-M+1}からA_iまでを昇順に並べた数列をB_iとします。B_iの先頭K項の和をS_iとします。

i=M+1,M+2,\cdots ,Nについて、A_{i-M}を削除し、A_iを追加した場合に、B_{i-1}からB_iにどのように変化したかがわかれば、S_{i-1}から変化分を増減させることで、S_iを計算できます。

これを考える時、A_{i-M},A_iがそれぞれB_{i-1},B_iK番目以内かそうでないかの4通りを考えれば良いです。

具体的に説明します。

  • A_{i-M}B_{i-1}K番目以内
    この時、A_{i-M}の分、和は減少します。

    • A_{i}B_iK番目以内
      A_{i-M}が削除され、A_iが挿入することを考えると、削除されて空いた箇所に左詰めまたは右詰めで各要素が移動し、A_iが挿入されたと考えることができます。
      このケースでは、新たにA_iK番目以内となってその分の和が増加するので、
      S_i \leftarrow S_{i-1}-A_{i-M}+A_i
      と計算できます。

    • A_{i}B_iK番目より後ろ
      A_{i-M}が削除されて空いた箇所にそれより後ろの要素が左詰めされて、A_iが挿入されます。
      このケースでは、B_{i-1}におけるK+1番目の要素がB_iで新たにK番目となり、この分の和が増加するので、これをB_{i,K+1}とおけば、
      S_i \leftarrow S_{i-1}-A_{i-M}+B_{i,K+1}
      と計算できます。

  • A_{i-M}B_{i-1}K番目より後ろ
    このケースでは、A_{i-M}による和の減少はありません。

    • A_{i}B_iK番目以内
      A_iが挿入されると、A_{i-M}の削除によって空いた箇所に右詰めされるように動きます。 このケースでは、新たにA_iK番目以内となってその分の和が増加し、B_{i-1}K番目だった要素がB_iにおけるK+1番目となって、この分が減少するので、
      S_i \leftarrow S_{i-1}+A_i-B_{i-1,K}
      と計算できます。

    • A_{i}B_iK番目より後ろ
      A_iは和に影響しないので、 S_i \leftarrow S_{i-1}
      となります。

B_iを全て記録することはN^2の領域が必要となるので、不可能だと思います。また、仮にそれが可能だとしても、C++vectorなら昇順ソートが毎回必要ですし、multisetでは何番目の要素かを得るのに時間がかかります。

そこで、Wavelet Matrixを使います。Wavelet MatrixはO(NlogA_{max})で構築し、O(logA_{max})で指定区間の任意のx番目に小さい要素を得ることが可能です。(但し、A_{max}Aに含まれる要素の最大値)
これで、O(NlogA_{max}+QlogA_{max})で解くことができます。

実装: Submission #37188154 - AtCoder Beginner Contest 281

AtCoder Beginner Contest 280 備忘録

コンテストページ:
コンテスト中AC: A〜E

D - Factorial and Multiple

制約上、O(\sqrt{K})くらいの解法、すなわち素因数分解や約数を利用した解法を疑います。今回は素因数分解で解けました。

Kが素因数pを1つだけ持つとします。N!Kの素因数を全て含む必要がありますが、p合成数ではないので、2つ以上の正整数の積で表すことができません。従って、少なくともp!は必要であり、N\geq pであることが確定します。

pが2個含まれる場合を考えると、p!の次にpが現れるのは2p!なので、N\geq 2pが確定します。

一般化すると以下が言えそうですが、これは誤りです。

Kに素因数pe個含まれる時、N\geq epが成り立つ

反例として、K=8があります。
2が3個含まれるので、N\geq 6が必要かといえば、そうではなく、N\geq 4で達成できます。
これはpの倍数にpが2個以上含まれることによって発生しています。

そこで、以下は成り立つと言えます。

Kに素因数pe個含まれるとする。p,2p,\cdots epの順に探索し、pの数がe個以上に初めてなるものをkpとするとき、N\geq kpが成り立つ

これをKに含まれる素因数全てについて求めていきます。
K=p_1^{e_1}\times p_2^{e_2} \times \cdots \times p_m^{e_m}素因数分解されたとすれば、各素因数について前述の値を求め、それらをx_1,x_2,\cdots ,x_mとすると、

N\geq max\{x_1,x_2,\cdots x_m\}

が成り立つ必要があるので、Nとしてとりうる最小値はmax\{x_1,x_2,\cdots x_m\}であり、これが答えです。

かなり大雑把に計算量を見積もります(間違っていたらすみません)。
素因数は2以上なので、素因数の個数の和はlogK個以下です。よって、各素因数について各倍数を調べる部分は合計logK回以下です。また、各倍数に含まれる素因数の個数もlogKを超えないはずなので、かなり大雑把に見積もってもO(log^2 K)で済みます。

そのため、おそらく素因数分解の計算量がボトルネックとなります。
素因数分解はあまり効率的ではない試し割りであっても、O(\sqrt{K} + logK)くらいかと思います。(素因数の個数が合計でlogK個以下なので、同じ素因数で複数回割る部分を考慮してlogKをつけましたが、不要かもしれません)

提出コード: Submission #36979663 - Denso Create Programming Contest 2022 Winter(AtCoder Beginner Contest 280)

E - Critical Hit

期待値DPの典型的な考え方で解けます。

状態uが遷移元でその期待値をE_uとする。
状態v_1,v_2,\cdots v_mに遷移し、
遷移先の期待値がE_{v_1},E_{v_2},\cdots E_{v_m}で、
遷移する確率がp_{v_1},p_{v_2},\cdots p_{v_m}で、
遷移にかかる操作回数がw_{v_1},w_{v_2},\cdots w_{v_m}の時、
E_u = p_{v_1}(E_{v_1} + w_{v_1}) + p_{v_2}(E_{v_2} + w_{v_2})+\cdots + p_{v_m}(E_{v_m} + w_{v_m})

今回の場合、体力がiの状態からは、
体力がi-2i-1の状態に遷移し、
遷移する確率が\frac{P}{100}\frac{100-P}{100}で、
遷移にかかる操作回数が、いずれも1回なので、

E_i = \frac{P}{100}(E_{i-2}+1) + \frac{100-P}{100}(E_{i-1}+1)

この式に従って計算すれば、メモ化再帰やDPなどで解けます。
なお、メモ化再帰ではi\lt 0となる場合の処理について注意します。

提出コード: Submission #36983677 - Denso Create Programming Contest 2022 Winter(AtCoder Beginner Contest 280)

計算方法がフィボナッチ数列に似ているので、以下のように考えれば行列累乗で解けそうです。



\begin{pmatrix}
E_{N+1} \\
E_N \\
\end{pmatrix}

=

\begin{pmatrix}
  \frac{100-P}{100} &  \frac{P}{100} \\
1 & 0 \\
\end{pmatrix}

\begin{pmatrix}
E_{N} \\
E_{N-1} \\
\end{pmatrix}

=

\begin{pmatrix}
  \frac{100-P}{100} &  \frac{P}{100} \\
1 & 0 \\
\end{pmatrix}^N

\begin{pmatrix}
E_{1} \\
E_{0} \\
\end{pmatrix}


AtCoder Beginner Contest 279 備忘録

コンテストページ: TOYOTA SYSTEMS Programming Contest 2022(AtCoder Beginner Contest 279) - AtCoder

コンテスト中AC:A〜D
コンテスト後にE,Fを自力AC。

D - Freefall

下に凸な関数っぽい感じだったので、下のサイトを参考に三分探索しました。
三分探索を救いたい - Qiita

誤差が出てくるので、出てきた操作回数±10くらいの範囲を探索しました。
一応、ACできましたが、疑問がいくつか残ったままだったので、コンテスト後に調べてみました。

整数の三分探索の方法

公式解説によれば、繰り返しの条件をr - l > 2として、終了後にrからlまでの最小値を答えれば良いようです。
おそらく、3分する点がlと重複しない間は探索を繰り返すものと思います。

探索範囲の最大値

t\geq \frac{A}{B}ならf(t) \geq f(0)となるので解は\frac{A}{B}以下となる、ということらしいです。詳細は公式解説参照。

下に凸であることの判定

上に凸,下に凸な関数と二階微分 | 高校数学の美しい物語
上記サイトによれば、二階微分が非負整数なら下に凸と判定できるそうです。

ざっくりとした理由をメモしておきます。

まず、一階微分は接線の傾きであり、下に凸の場合単調非減少となる必要があるそうです。確かに、下に凸の二次関数などを例に考えれば、最小値より前は傾きが負で、最小値に近づくにつれてだんだん傾きは小さくなり(0に近づき)、最小値で0になります。そして、その後は傾きは正になり、傾きは大きくなっていくことが想像できます。
そして、傾きが単調非減少になるためには、傾きの変化量は常に非負である必要があるので、二階微分が非負になるということが理解できます。

高校数学から大分遠ざかっていたので、微分を思い出しながら実際にやってみます。

f(x) = Bx+\frac{A}{\sqrt{x+1}}

• 一階微分
Bxの項はBになります。

次にAを含む項です。

合成関数の微分を思い出すと、

u = x+1,\ f(u) = \sqrt{u}

のとき、

\{f(u)\}' = f'(u)u'

です。
Aを含む項は、

\frac{A}{\sqrt{x+1}}=A(x+1)^{-\frac{1}{2}}

ですから、その微分は、

A\cdot -\frac{1}{2}\cdot (x+1)^{-\frac{3}{2}}\cdot 1
 = -\frac{1}{2} A (x+1)^{-\frac{3}{2}}

よって、

 f'(x)=B-\frac{1}{2} A (x+1)^{-\frac{3}{2}}

です。

• 二階微分
同様に合成関数の微分を使うことで、

f''(x) = -\frac{1}{2} A \cdot -\frac{3}{2}(x+1)^{-\frac{5}{2}}
= \frac{3}{4} A (x+1)^{-\frac{5}{2}}

となります。x\geq 0において、f''(x)\geq 0が成り立つので、下に凸であることが示されました。

提出コード: Submission #36819682 - TOYOTA SYSTEMS Programming Contest 2022(AtCoder Beginner Contest 279)

E - Cheating Amidakuji

このユーザ解説と同じ方法でした。

実装: Submission #36848977 - TOYOTA SYSTEMS Programming Contest 2022(AtCoder Beginner Contest 279)

F - BOX

公式解説と同じ方法でした。

実装: Submission #36835935 - TOYOTA SYSTEMS Programming Contest 2022(AtCoder Beginner Contest 279)