2024/2/10に開催されたABC340C問題Divide and Divideの自分用解説です。

桁数が大きいときTLE…

効率的なやり方がわかりませんでした。

サンプルコード(解説ページからコピペ)

大事そうなとこ解説

line7：マップ mに与えられたキーNが存在するかどうかを調べています(mapのcount関数は、与えられたキーがすで　　　　　　　　　　に存在するか調べる)。もしNがm内に存在する、つまり、すでにf(N)の計算結果がm[N]に格納されている場合、その結果を返します。これにより、同じNに対する計算がよくなるんですね。

line8：実際の計算部分です。Nに対する計算結果をf(N/2)+f((N+1)/2)+Nと定義し、その結果を m[N] に代入します。

今回のようにすでに計算したものを配列に保存して、2回目以降は配列から呼び出すだけにする処理を’メモ化再帰’というらしいです。

反省

メモ化再帰、知らなかったですね。勉強になります。
でも知らなかったから解けなかったー、というほど複雑でもない気がします。発想力がたりないというか。。。

最近全然レートが超停滞中。C問題を解けなきゃ茶色にはなれなそうですね。