CODE FESTIVAL 2018 qual A 参加記録

本戦参加資格はありませんが、普通にunratedなコンテストとして参加。

結果は4完で68位。資格があれば本戦行けてそうな順位ですね…

f:id:betrue12:20180922234652p:plain

4問振り返ります。

A - 配点

解法

作れる合計点の最小値は $A+B+C$ 、最大値は $A+B+C+3$ で、その間の点は全部作れます。この範囲に $S$ が入っているか調べればよいです。

ACコード

（Ruby）Submission #3241130 - CODE FESTIVAL 2018 qual A

B - みかん

解法

制約が小さいので愚直にやれば十分通ります。「房の数は $A$ でなければいけない」フラグを各みかんごとに持って、条件ごとに $L_{i}$ から $R_{i}$ までのフラグを立てていけばよいです。最終的にフラグが立っているみかんは $A$ 、立っていないみかんは $B$ とすればOKです。

ACコード

（Ruby）Submission #3241826 - CODE FESTIVAL 2018 qual A

半分

C - 半分

解法

段階を踏んで、少しずつ考察していきましょう。

ウォームアップ

正整数を2で割ると、どんどん値は小さくなり、やがて0になります。0になった後はいくら2で割っても0のままです。例えば最初の整数が7の場合、7→3→1→0→0→0→... となります。

数え上げにおいては「数え上げる要素として区別されるかどうか？」がとても大事なので、その観点で言い換えると

0になるまでは、数値と2で割った回数が1対1対応し、区別される。
0になって以降は、何回割っても区別されない。

このように言えます。このことから、まずは問題文を次のように解釈できます。

「 $i$ 番目の要素に、合計 $K$ となるように正整数 $k_{i}^{\prime}$ を割り当てる。 $a_{i}$ を2で割って0になるまでの回数を $t_{i}$ として、 $k_{i} = \min(k_{i}^{\prime}, t_{i})$ とする。 $(k_{1}, ..., k_{N})$ の場合の数を求めよ。」

$k_{i}^{\prime}$ が $a_{i}$ を2で割った回数に対応し、 $k_{i}$ がそれに「0になって以降は何回割っても区別しない」ということを加味したものです。このように解釈することで、具体的な $a_{i}$ の値を考えなくてよくなります。

ここで $t_{i}$ の値を見積もっておきましょう。 $\frac{10^{18}}{2^{60}} = 0.86...$ であり、制約上最大の値である $10^{18}$ は2で60回割ると0になります。つまり、 $0 \le t_{i} \le 60$ です。これは後で使います。

場合分け

さて、このような場合の数をどうやって数えましょう。0になる、つまり $k_{i} = t_{i}$ となる要素が存在する場合がやっかいなので、まずそこで場合分けをしてみます。

0になる要素が存在しない場合、0を操作して「無駄に回数を重ねる」ことができないので、ぴったり 回の操作で到達可能な数列しか作れない。つまり、以下の条件を全て満たすの個数を数え上げる。
- 全ての $i$ について $k_{i} \lt t_{i}$
- $\sum k_{i} = K$
0になる要素が1つでも存在する場合、0を操作し続けることでいくらでも回数を水増しできるので、回以下の操作で到達可能な数列は全て作ることができる。つまり、以下の条件を全て満たすの個数を数え上げる。
- 全ての $i$ について $k_{i} \le t_{i}$
- 少なくとも1つの $i$ について $k_{i} = t_{i}$
- $\sum k_{i} \le K$

これらは排反（両方に含まれる数え上げ対象がない）なので、それぞれを数えて合計すればよいです。

このように場合分けをしてしまうと、実際に2で割った回数 $k_{i}^{\prime}$ を考慮しなくてよくなり、 $k_{i}$ を $k_{i} \le t_{i}$ の範囲だけで考えればよくなります。これがとても嬉しくて、 $T = \sum t_{i}$ とすると $\sum k_{i} \le T$ であり、先程見たように $t_{i} \le 60$ なので $T \le 50 \times 60 = 3000$ 、つまり合計が高々3000くらいになりました。 $O(T^{2})$ が間に合うのであれば、動的計画法で解けそうです。

動的計画法

ということでDPをします。「 $i$ 番目まで見て、それまでの $k_{i}$ の和が $j$ であるような場合の数」を $dp\lbrack i\rbrack\lbrack j\rbrack$ として考えるとシンプルに解けそうです…が、先程見たように「0になる要素が1つでも存在するか？」で場合の数たちを区別してあげる必要があります。そこで、「0になった要素が存在する/しない」という条件を追加します。

「0になった要素が存在しない」のほうを $dp\lbrack i\rbrack\lbrack j\rbrack\lbrack 0\rbrack$ 、「存在する」のほうを $dp\lbrack i\rbrack\lbrack j\rbrack\lbrack 1\rbrack$ とします。0になった要素が存在するとは、ある $i$ について $k_{i} = t_{i}$ であるということなので、遷移は以下のようになります。

f:id:betrue12:20180923104141p:plain

これは $O(T^{2})$ で最後まで回せます。最終的な答えは、「場合分け」のセクションで記載したそれぞれの数え上げ対象を足して、

$dp\lbrack N\rbrack\lbrack K\rbrack\lbrack 0\rbrack + \sum_{j \le K} dp\lbrack N\rbrack\lbrack j\rbrack\lbrack 1\rbrack$

となります。ただし $K$ が大きいときにはそのまま実装すると範囲外アクセスや大量のループが起こるので注意です。実際には $K \le T$ の範囲ならどれだけ $K$ がどれだけ大きくても関係ないので、 K = min(K, T) としてしまっても問題ないです。

ACコード

（C++）Submission #3243706 - CODE FESTIVAL 2018 qual A

※解説文のほうを公式解説に合わせたので、上のコードとはdpの0と1が逆です。

D - 通勤

解法

到達条件と給油条件

家、ガソリンスタンド、オフィスをまとめて「ポイント」と呼ぶことにします。家を0番目、オフィスを $N+1$ 番目のポイントとしておきます。

高橋くんがそれぞれのポイントにたどり着いた時の挙動として、以下の2つを考える必要があります。

ガソリン切れを起こさず、そのポイントに到達できるかどうか？
そのポイントがガソリンスタンドだった場合、そこで給油をするかどうか？

これらはガソリンの残量によって決まります。そのポイントに到達した時点でガソリンの残量が負であれば到達不可能ですし、0以上 $T$ 未満であれば給油をします。

ガソリンは毎回満タンまで給油するので、これらの条件は「最後にどのポイントでガソリンが満タンになったか？」だけから決まります。これをパラメータとしてDPしてみましょう。

動的計画法

$dp\lbrack k\rbrack\lbrack i\rbrack$ を「 $k$ 番目のポイントまで見たときに、 $k$ 番目のポイントまで到達可能であって、最後にガソリンが満タンになったポイントが $i$ 番目になるような場合の数」とします。

$k$ 番目のポイントに到達した時に、 $0, ..., k-1$ 番目のポイントのうち最後に満タンになったのがどこかによって、以下の3パターンになります。

遠すぎて、到達できない。
到達できて、ガソリンを給油する。
到達できるが、近すぎてガソリンをあまり消費していないため、ガソリンを給油しない。

この境目は $k$ 番目のポイントとの距離だけで決まり、見ていくポイントを右に進めると境界も単調に右に動いていくため、しゃくとり法が使えます。

f:id:betrue12:20180923103800p:plain

それぞれについて、 $k$ 番目のポイントをガソリンスタンドにしたとき、書店にしたときの遷移を考えます。

f:id:betrue12:20180923111853p:plain

最後の合計結果を見ると、 $k$ 番目のポイントを見た時のDPテーブルの値は、 $k-1$ 番目のポイントを見た時の値と比べて以下のようになっています。

「到達不可」に分類されるところは0。
（到達できて）「給油する」に分類されるところは据え置き。
（到達できて）「給油しない」に分類されるところは、2倍される。
新しい要素として $dp\lbrack k\rbrack\lbrack k\rbrack$ に、「給油する」に分類されるポイントについて $dp\lbrack k-1\rbrack\lbrack i\rbrack$ を合計したものを入れる。

これを2次元テーブルを全部埋める形でやっていくと時間がかかりすぎるので、高速化します。

DP高速化

まず、2次元のDPテーブルを作るのは無駄が多いです。状態は1手前の値のみに依存し、値が据え置きのところもあるので、これを1次元配列で管理して差分だけ更新していくことを考えます。すなわち、 $dp\lbrack i\rbrack$ を「いま見ているポイントまで到達可能であって、最後にガソリンが満タンになったポイントが $i$ 番目になるような場合の数」とします。説明上、「今見ているポイント」は引き続き $k$ と表記します。

「「到達不可」に分類されるところは0」は、しゃくとり法で境界を動かしていくたびに0を埋めていけばいいです。（実際には、これはやらなくてもいいですが、一応）

次に、新しい要素を入れるのに使う「「給油する」に分類されるポイントについて $dp\lbrack i\rbrack$ を合計したもの」です。これはDPテーブルの区間和になるので、逐次累積和を取っておいて差分を使ったり、しゃくとりで境界を動かすたびに差分更新をすればよいです。累積和のほうが個人的にはバグらせにくくてオススメです。

最後に残ったのが「「給油しない」に分類されるところを2倍」で、これはとても厄介です。ですが、以下のように考えることができます。

f:id:betrue12:20180923110650p:plain

「DPを1ステップずつ進める途中で区間内の値を全て2倍する」と考えるととても厄介です。ですが1つ1つの要素に注目すると、「値がセットされる→何回か2倍される→先の値を更新するのに使われる」という流れになっています。途中で更新するのが面倒なら、「何回2倍されるか」を予め求めておいて、最初から掛けておけば良いのです。

つまり、 $k$ 番目のポイントを考える時に $dp\lbrack k\rbrack$ にセットする値は、「それ以前の「給油する」に分類されるポイントについて $dp\lbrack i\rbrack$ を合計したもの」に「それ以降、ポイント $k$ で満タンにした車が給油されないポイントが $k+1, ..., N$ のうちいくつ存在するか」だけ2を掛けたものになります。