コンテストページ
AtCoder Regular Contest 099 - AtCoder
解法
C - Minimization （300 点）
入力の数列は実は関係なくて、結局すべてを覆わないといけませんから、ceil( (n-1) / (k-1) ) です。
D - Snuke Numbers（500 点）
異常枠です。下の方の位に 9 が何個続いているかで場合分けをして全列挙をします。
候補のお名前は x です。x の 9 でない桁の最下位が i 番目だとして、10i を I と置きましょう。 すると、最低限 x + I に勝つ必要があって、逆に言うとそれに勝てれば無敵です。
次に、x の下の方の 9 ばかりの方を消した数を y と置きましょう。 すると式変形を頑張ると条件は (y - S(y)) * I ≦ 1 + (9 * i - 1) * I となります。 大切なことは、y - S(y) が y に関して単調増加になっていることです。ですから、小さい順に試していけばすべてわかります。y の最下位の数字が 9 であるときにはスキップしておくとよいです。
E - Independence（700 点）
なるべく均等に分ければよいです。 また、条件は補グラフが二部グラフと同値ですから、連結成分ごとに二部グラフ分解をすればよいです。
均等に分ける部分はいろいろとやりようがあると思うのですが、私はナップザックで解きました。 ただし、遷移に 0 があったりなかったりするので、0 がなかったら dp[i] = false をしましょう。 ところで豆知識なのですが in-place にしなければこのような分岐は必要ありません。コンテスト中に気づきましょう！（泣）
なお、こちらの問題はすでに解いたことがあります。考察が本質、実装は無ですから、実質 700 点の無料配布です。
感想
AGC ですか！？
難易度自体は AGC に遠く及びませんが、傾向は通づる物を感じてしましました。
結果
98 位 2425 橙パフォです。D がギリギリで通って嬉しかったです。
感触としては悪くはなかったですし、それに加えて E 履修済みブーストが無視できないレベルで寄与していると思うのですが、それで 2425 というのはなかなか厳しいものがあります。
そこまで大きな戦略ミスはなかったのですが、あえて言えば、D で「1010 まで全探索をして観察」の時間が長すぎたという説はあります。私はコンピューターで「とりあえず回してみる」に手を出すと、そこから紙の世界に戻ってくるのが若干遅れる癖があるかもしれません。心に刻みましょう。
