yukicoder contest 411 感想 - Programming Coontest

「イエローカードの性質を競プロの問題にできないかな」と思っていたら，ふと生えた問題です．それなりに上手い感じの設定になってくれたと思います．

高難易度にありがちな，状態の持ち方を工夫する必要のある DP の問題です．応用的な考察が必要なこともあり、当初は★3.5を提案していましたが、テスターさんに★2.5～★3を主張されたため修正しました．AC 数が想定よりもはるかに多く，変更して本当に良かったと思います*1．

想定解法は $O(NK)$ の DP ですが、テスターさんから $O(\log K)$ 解法が提案されたため，解説において Bonus. で記載してあります（★4.5～★5相当？）．

私が作問を始めた初期（1年～1年半前？）の頃から作問ストックにあった問題です．かなり典型寄りの問題であり，単独コンテストに回すような問題でもなかったため，どこで出題しようか......と，出題する機会を伺っていたところ，オムニバスコンテストが開催されるとのことで，ここで出題を決めました．

当初は $K \leq 10$ だったのですが，後で「別に $K$ が大きくても普通に解けるよね」ということに気づいたため，今の制約で出題しています（なぜ最初から気づいていなかったんだろう......）．

意図したわけではないですが，2 問とも 998244353 系統の問題にしたところ，ほかの方の問題にも 998244353 系統が多くてびっくりしました．こういう回もあると思います．

ところでこの回の D,E はかなり難しいと思うんですが，私だけですか？（どちらも解くのに1時間くらいかかっている......）

*1:ちなみに難易度投票ではまさかの★2.5が最多でした．私の中でもけっこうな大誤算だと思っており，反省点としたいです．