毎年恒例、競技プログラミングの祭典 CODE FESTIVAL の予選に参加しました。

CODE FESTIVAL は今年で5年目となる リクルート 主催のコンテスト。成績優秀な若者は希望すれば「本戦」に出場できて、みんなで大会の会場に集まって競プロができる、らしいです。

とはいえ私は出場資格がないので、いつもの AtCoder Beginner Contest と同じ気持ちでやっていきます。

問題リスト：

A - 配点

問題概要：3つの問題を出題することになった。1問目の配点は A 点か A+1 点のどちらかにする。同様に、2問目は B か B+1、3問目は C か C+1。配点の合計を S にできるか？

解説：すべての組み合わせ (8通り) を試せばOK。

もう少し短く書くこともできます。合計点としてありえる点数の範囲を考えます。最小は A+B+C、最大は (A+1) + (B+1) + (C+1) = A+B+C+3。この範囲内ならどの合計点もありえます。

A+B+C <= S && S <= A+B+C + 3

提出：

B - みかん

問題概要：みかんが N 個ある。みかんの房の個数は必ず A か B のどちらか。いくつかの範囲 [L, R] に関して、番号が L 以上 R 以下のみかんの房の数は A と分かった。みかんの房の個数の合計値は、最大でいくらか。

解説：「L以上R以下」の範囲に含まれないみかんの房の個数が不明なので、それを適当に決めて最大化します。

AとBの大きいほうを選ぶのが最適です。

みかんの個数や範囲の個数が少ないので、あとは問題に書かれているとおりに計算すれば解けます。

提出：

C - 半分

問題概要：長さNの数列が与えられる。数列のいずれかの要素の値を半分にする (端数切り捨て) 操作を合計でK回行う。結果として得られる数列の種類は何通りか。10^9+7 で割ったあまりを求めよ。

解説：こういう問題は、まず簡単なケースの樹形図を書くと分かりやすい気がします。書いてみると、操作を行う順番は関係なさそうです。つまり、1要素目を半分→2要素目を半分、という2操作は逆にしても結果が同じです。以下では、各要素に対して「何回操作を行うか」を考えることにします。

操作の手順が異なったとしても、同じ数列を複数回数えてはいけないことに注意です。ある要素に行う操作回数が異なるなら、結果として異なる数列が得られるでしょうか？ 要素の値が 0 でなければ異なる値になりますが、0 は何回半分にしても 0 です。

(ここから長い脇道) これは重複組み合わせに思えてきました。参考：

例えば、非負整数 x, y, z の方程式 x + y + z = 2 の解は何個かという問題。まず、2個の玉と2個の仕切りからなる順列を考えます。

○ | ○ | ↔ 1 + 1 + 0 = 2
| ○ ○ | ↔ 0 + 2 + 0 = 2

仕切りで区切られた区間にある玉の個数を x, y, z とすれば、この順列と方程式の解は 1:1 対応です。順列の計算で (2+2)! / (2!・2!) = 6通り、と計算できました。

今回の問題では、玉の個数の代わりに操作回数を x, y, z, ... とします。前述の通り操作回数には「要素の値が 0 になるまで」という上限をかけて考えたいので、なんらかの工夫が必要です。

もし下限だったら、つまり x ≥ 1 だったら、玉の個数を最初から1つ減らしておき、 x ≥ 0 (つまり無条件) で上述の順列を計算し、最後に x に1を加える、という手順で解消できます。これは x' = x - 1 という変数変換に対応します。

では x ≤ h に対して x' = K - x と変数変換したらどうでしょうか。(K は操作回数の合計値。) 制約が x' ≥ K - h という下限の形に変わったので、同様に解ける、ような気がしました。いま思うと制約 x + y + z = K を x' + y + z = ? という形に変形しないといけないんですが、よく考えずに x' + y + z = K としてしまったのでダメになりました。この道はダメだ、引き返そう。(ここまで長い脇道)

長い脇道でしたが収穫がなかったわけではなく、「操作回数の上限の総和」に気づきました。値を半分にする操作を繰り返して 0 にするのにかかる回数は対数オーダーであり、とても小さいです。

その長さの配列がメモリに乗るぐらいに小さい。その回数だけループを回してもいいぐらいに小さい。夢と解法の幅が広がります。

i 番目の要素の操作回数の上限を H(i) とします。操作回数の上限に達するということは、すべての要素が 0 になったということです。この状況で ΣH + 1 回目以降の操作には意味がありません。そのため K がいくら巨大でも ΣH + 1 を超えている意味はありません。

だんだん楽になってきました。すべての要素について、それに何回操作するかを列挙して数え上げます。メモ化再帰にすれば O(N log K) です。

最後にコーナーケースに対処します。どの要素も操作回数が上限に達しないような組み合わせでは、「0 になった要素を使って操作回数を稼ぐ」ことができないので、操作回数がちょうど K になっているときだけ計算します。桁DPを思い出しながら「要素を 0 にしたか」を記録しておけばOK。

提出：

おわりに

ひさしぶりに500点の問題をオンタイムACできたので嬉しいです。