脳log[20260103]

2026年01月03日 (土) [AtCoder] 今日は ABC439（Promotion of AtCoderJobs） があった。幸先の悪い新年の始まり。■A 問題 2^n - 2*n。やります。■B 問題 Happy Number。やります。概ね減少するけどループがないとわからなかったので BFS で。■C 問題 2026。間に合うように解けません。■D 問題 Kadomatsu Subsequence。瞬殺だと思ったんだけど、７の因子と５の因子と３の因子が共存できないと勘違いして排他で処理を書いたらサンプルの３で答えが足りなかった。書いた時間の２倍以上をデバッグに使った。■E 問題 Kite。ずっと DP をやろうとしていた。y=0 と y=1 に対応した２系統の DP 列で答えを出そうとして、最終的にうまくいかないことがわかった。じゃあどうやったらうまくいくか、改めて考えると LIS が見えてくるのにそんなに時間はかからなかった。そこから立て続けにペナルティ２つ。同じ地点の競合がうまく処理できなかった。逆順では解決しないと思ったから回りくどい書き方をしたけど、やっぱり逆順でいけるんじゃないか？ 余談。DP から LIS への頭の切り替えでちょっと苦労したギャップは、LIS では求めるものが明示的に値として記録されていないというあたり。作業配列の長さという形で LIS の長さが求まる。重層的な記録をインクリメンタルに更新する処理の進め方からは、LIS も DP の一種に見えるけど、ここでは区別した。■時間いっぱいの最遅 ABDE ４完。ということは最速 ABCD ４完と同等のパフォーマンスになるのかな、嬉しくないが。自分のすべての提出。■■■C 問題。組み合わせ全探索が許されていたんだね。y の上限が N のルートまでだから、２つの組み合わせはおよそ２乗でだいたい N。……という見積もりができなかったんだなあ。■■■F 問題 Beautiful Kadomatsu。終了後にちらっと読んでわかんないと思ってたんだけど、AtCoder Problems で水 diff だと見えたのでなめて取りかかってみた。提出 #72258562 (AC)。３つの状態に対応して３本の BIT を持った。状態というのは、点、上昇中、折れ曲がって下降中の３つ。最初に点があり、２点目で下降を始めた場合は絶対に門松的にならない。上昇するなら上昇中に移行する。上昇から下降に転じた段階で門松的になり、そこから上昇に転じたときに門松的ではなくなり再び上昇中に移行する。一直線の DP。数列を走査しながら状態を更新し、同時に各要素が門松的な部分列の末尾となる数を数えていく。■解説はよくわからないね。配列を２本と木を１つ使っているみたいで定数倍は良さそうだけど計算が難しそう。すべての部分列の累積和を求める典型にあてはめて端から順番に数えましょうよ。