情報妖精の競プロ日記

AtCoderの問題に対する方針を主に書きます

CODE FESTIVAL 2018 予選A

CODE FESTIVAL 2018 予選Aに参加しました！
CODE FESTIVAL 2018 qual A 旧版
CODE FESTIVAL 2018 qual A beta版

解けた問題だけ解説をしていきますー

要項

CODE FESTIVAL 2018 qual A
unrated
9/22(土) 21:00 ～ 23:00 (120分)
100-200-500-700-800(5問)
ペナルティ: 無し

方針

3完、そして速い4完(ここが突破ボーダーだと思います)
とにかく3完しなきゃ絶対にTHANKSにも行けないので、本気で頑張りましょう。
こんなところで潜伏する意味は薄いので前から解こうね！

A - 配点

3問の合計点はA+B+C点から(A+1)+(B+1)+(C+1)=A+B+C+3点まで取ることができます。
この範囲にSが入っていれば良いので、A+B+C \leq S \leq A+B+C+3を判定すれば良いです。

B - みかん

まずは簡単な実装法を説明します。
整数型で長さがNの配列Sを用意します。はじめ、配列の全ての要素は0です。
次に、各L_i, R_iについてS_{L_i}からS_{R_i}までの全ての要素に1を加算します。
そして、全てのiについて操作が終わった時、任意のjについてS_j \neq 0ならばそのみかんにはA個の房があります。
そうでない時は\max(A, B)個の房があるのが最適ですが、制約よりA < Bなので要するにB個の房があります。
よって、{\rm O}(NM)で解くことができました。
ですが、ここで更に工夫を入れます(もちろん今回の場合、不要なのでやる必要はありません)。
区間加算を高速にやる方法として、imos法という方法が存在します。
今回の場合、L_i, R_iについて、全ての区間に加算する代わりにS_{L_i}に1を加算し、S_{R_i+1}に-1を加算します。
そして、後で累積和を取ると丁度L_iからR_iの区間のみ1増えます。
この操作ならば各iについて{\rm O}(1)で操作が終わることから、計算量が{\rm O}(N+M)で終わります。

C - 半分

まず、この問題において操作の順番は結果に影響を与えないので、こういう時は必ず前から操作すると決めておきます。
操作の順番が関係ない時は操作順に制約を作った方が見通しが良くなります。
さて、まず先頭について操作を考えてみると、\lfloor \log(A_1) \rfloor回までは必ず数字が変化し、それ以降は変化しません。
つまり、\lfloor \log(A_1) \rfloor回より多い操作は考える必要が無くなります。
他のAについても同様なので、Kの操作回数を\min(K, \sum_{i=1}^{N}\lfloor \log(A_i) \rfloor \leq 60N)に変えても問題はありません。
これで一気に計算量が減り、O(NK)が間に合うようになりました。
さて、先頭から順に操作を行っていき、後の要素は先頭に影響を与えないとなるとやることは動的計画法ですね！
そこで、まずはdp_{i, j}をi番目の要素まででj回操作しているときの組み合わせと考えましょう。
その時、遷移は1個前のテーブルのみ見れば良いので、各要素について{\rm O}(\lfloor \log(A_i) \rfloor回くらい計算すれば良さそうで、これは通りそうです。
ですが、実際に試してみるとサンプル1と2で上手い感じのDPが組めません。
これは、やってみると分かりますが0の要素が存在するかどうかの問題で、存在しない時は丁度K回、存在する時はK回以下と条件が異なっているためです。
そこで、0の要素が存在するかどうかもDPに組み込めば、条件を網羅できそうです。
dp_{i, j, k}をi番目の要素まででj回操作しているときの組み合わせであって、k=0ならばA_1からA_iまでに0が存在せず、k=1ならば0が存在することにしましょう。
まず、この時の初期値は次のようになります。
dp_{1, j, 0}はj < \lfloor \log(A_1) \rfloorならば1、そうでないならば0
dp_{1, j, 1}はj = \lfloor \log(A_1) \rfloorならば1、そうでないならば0
この時、遷移は次のようになります。
dp_{i, j, 0} = \sum_{k = j - \lfloor \log(A_i) \rfloor + 1}^j dp_{i-1, k, 0}
dp_{i, j, 1} = dp_{i - 1, j - \lfloor \log(A_i) \rfloor, 0} + \sum_{k = j - \lfloor \log(A_i) \rfloor}^j dp_{i-1, k, 1}
後はこの漸化式通りに計算すれば{\rm O}((N\sum_{i=1}^N \lfloor \log(A_i) \rfloor)^2) \leq 9 \cdot 10^6で間に合います。
尺取り法などを用いて遷移{\rm O}(1)にすることで計算量{\rm O}(N^2\sum_{i=1}^N \lfloor \log(A_i) \rfloor)にもできますが、必要は無さそうです。

結果

oox-- 2完(300点) 1:45-5:48 / 5:48
322位

感想

C問題、何故か漸化式の遷移をミスって無限にバグらせていた(添字ミスです)ので話にならず。
ちなみに漸化式自体は順序だてて考えていけば20分以内には思いつけるはずです。
これはそう難しい式でもなく、また順位表を見れば分かるように速い人たちが5分少々で解いていることからも比較的典型な遷移であると分かるはずです。
こういう時の順位表は役に立って、解いた速さから大まかな問題難易度や考察量を類推することができます。
特に上位コーダーが数分で解いているときは典型的なものの場合が多いので、問題文の単語から考えられる典型パターンを類推しましょう。
今回のC問題だと組み合わせ問題なので、数学あるいは動的計画法であることは秒で予想できるかと思います。
しかも5分で解ける動的計画法の場合、各添字や遷移の意味は必ず分かりやすいものになっているはずです。それこそ操作回数とか。