DISCO presents ディスカバリーチャンネル コードコンテスト2019 予選：D - チップ・ストーリー　～黄金編～

問題

https://atcoder.jp/contests/ddcc2019-qual/tasks/ddcc2018_qual_d

考え方

ある数 N を P 進数で表記したときにどのようになるか考えると解ける。つまり N を P 進数で表記したときに下の桁の数から b_0,b_1,b_2,\cdots,b_M で表されたとすると N=b_0*P^0+b_1*P^1+b_2*P^2+\cdots, +b_M*P^M と表すことができる。

\forall k \in \mathbb{N}, p^k \equiv 1\ (mod\ P-1) であるから N について P-1 の余りをとると N=b_0*P^0+b_1*P^1+b_2*P^2+ \cdots +b_M*P^M \equiv b_0+b_1+b_2+ \cdots +b_M\ (mod\ P-1) となる。

よって、N を P 進法で表したときの桁和が a_p であると仮定すると、N を P-1 で割った余りが a_p であることが言える。これは 2 \le P \le 30 なる P-1 を法として、各 a_p に中国剰余定理を適応することができて、そのような N は LCM(2,\cdots,30) \approx 2.3 * 10^{12} \gt 10^{12} であるから [1,10^{12}] に唯一定まる。そのような N が定まったときに仮定の条件を満たしているか確認すればよい。

Submission #4323411 - DISCO presents ディスカバリーチャンネル コードコンテスト2019 予選

どこに着目して考察するべきだったか

P 進数で考えるときに、実際にある数 N を P 進数表記して考えるということはよさそう

何がバグっていたか

得た知見(典型ポイント)

  • 中国剰余定理

類題

AtCoder Regular Contest 068：E - Snuke Line

問題

https://atcoder.jp/contests/arc068/tasks/arc068_c

考え方

これは難しい...

考えていたこと

  • imos法で区間を含むか数える、がこれは重複して数えてしまうのでダメ。
  • d を全通り試すことは O(logM) でできるのでこれは全探索

解説見た

公式解説のベースに考えていく。がほぼまんま公式解説の写しみたいになってしまった...

今区間の長さ d\ (1 \le d \le M) について考えていることにする。l_i, r_i なる i 番目の区間について区間の長さが d よりも大きい r_i - l_i + 1 \gt d 場合は必ず 1 回以上は訪れることになる。そうでないとき、つまり r_i - l_i + 1 \le d であるときは高々1回のみ訪れることになる。

上記から区間の長さ r_i - l_i + 1 で分類して考えることができて、これが重要な考察である。区間の長さが小さい区間から考えていく。これは各区間について区間の長さで昇順ソートすればよい。

駅 j\ (0 \le j \le M) に含まれる種類の数を cnt_j で表すことにする。

区間の長さが k = r_i - l_i + 1 の区間 i について k \lt d を満たしているとき l_i \le j \le r_i なる cnt_j に 1 を加算する。これは BIT などのデータ構造を用いればよい。(区間加算できるように imos 法のような工夫が必要)

このとき cnt_0 + cnt_d + cnt_{2d} + \cdots が区間の長さが d 未満の区間に含まれる種類の合計となる。これに、区間の長さが d 以上の区間の個数を足せばよい。

長さ d 未満の区間の数について、区間の長さ d で含まれる場合は d+1 でも必ず含まれるので、それぞれの区間については 1 回見ればよいことがわかる。区間の長さ d でどこまでの区間まで計算したか保持しておけばよい。

よって全体の計算量は O((MlogM + N)logM) となる。

ちなみに d で全探索しても logM になるのは、区間の個数は \displaystyle \int_1^M \frac{M}{x}dx \approx MlogM 個であるため。調和級数を近似すると log で抑えられるというテク。

ちなみに放送解説も見たが、xy平面の個数をO(logM)で数える手法が難しかった

どこに着目して考察するべきだったか

区間に含まれる名産物は重複する可能性があるので、重複しないように数える工夫が重要。今回の問題の場合、区間の長さで分類することで、「必ず1つ以上含まれる or 含まれるかどうかわからないが高々1つ」の区間に分類できる。「含まれるかどうかわからないが高々1つ」である区間は、長さ d ごとに数えると重複せずに数えることができる。

何がバグっていたか

得た知見(典型ポイント)

  • 重複しないように工夫する(区間の長さで分類 or 区間の左端に着目)
  • 区間 [l, r] を xy 平面にプロット

類題

参考

Educational DP Contest / DP まとめコンテスト：Z - Frog 3

問題

https://atcoder.jp/contests/dp/tasks/dp_z

考え方

ConvexHullTrick を用いる。もらうDPを考えよう。

dp[i] := 足場 i\ (0-indexed) に至るときの最小のコスト

と定義する。この時DPの遷移は

dp[i] = min_{0 \le j \le i-1}(\ (h_i - h_j)^2 + C + dp[j])
\ \ \ \ \ \ \ \ =min_{0 \le j \le i-1}(\ (-2 h_j * h_i) + (h_j^2 + dp[j]) + (h_i^2 + C))

となる。(-2 h_j * h_i) + (h_j^2 + dp[j]) の部分は h_i に関する1次関数と捉えることができて 0 \le j \le i-1 なる j における1次関数たちの最小値は ConvexHullTrick を用いると O(logN) で求めることができる。 h_i^2 + C は定数と考えることができる。

そうすると 0 から順に各 i における最小値を求めることができる。

Submission #4312635 - Educational DP Contest

どこに着目して考察するべきだったか

ConvexHullTrick のテクを知っているということと、コストが何かの2次式で定義されているときに式を展開すると1次式として捉えることができて ConvexHullTrick が使えるようになる。

何がバグっていたか

得た知見(典型ポイント)

  • ConvexHullTrick

類題

第4回 ドワンゴからの挑戦状 予選：D - ディスクの節約

問題

https://atcoder.jp/contests/dwacon2018-prelims/tasks/dwacon2018_prelims_d

考え方

まずは最小値に単調性があるので、最小値 x を二分探索することにしよう。つまり以下の問題を考える。ディスク使用量をコストと呼ぶこととする。

「最小値を x とするとき、タスクを実行する過程でコストが x を超えないように、1番目のタスクが実行可能な状態にすることができるかどうか？」

1 \le N \le 20 という制約も参考になるかもしれないが、過程の状態のタスク集合は必ずしも連結とは限らない。解説で示されている例がその一つの例である。

なので、木ではなく、bitでタスクの状態を管理することとする。bitの状態を全探索しよう。あるタスクを実行するのに依存がないタスクから実行できることになる。まずはタスク x_i を実行するのに必要なタスク集合を bit で表す。

bit の状態遷移は以下を考える。

  • 状態を減らす(bit に含まれているタスクを除く)
  • 状態を増やす(依存先が全てbitに含まれているタスクを実行集合に加える)

このようにして状態を遷移させたときにコスト x を超えずにタスク1 が実行可能な状態集合を取りうることができればOK。そうでなければNGである。計算量は O(2^N * logN)。なおJavaだと二分探索の最大値をちょうど最大になるようにしないと通らない。

Submission #4308994 - 第4回 ドワンゴからの挑戦状 予選

どこに着目して考察するべきだったか

タスクの集合は非連結になりうるので木DPではうまくいかない。bitの集合を全探索しようという気持ちになると解ける。

何がバグっていたか

  • 依存関係を bit で表現する

得た知見(典型ポイント)

  • 集合の全探索は bitDP

類題

「みんなのプロコン 2019」：F - Pass

問題

https://atcoder.jp/contests/yahoo-procon2019-qual/tasks/yahoo_procon2019_qual_f

考え方

操作の結果の文字列を考えていく。ある文字列が構成されていると仮定したときに次の文字を置くことができる場合は、赤/青のボールごとに考えればシンプルに求めることができる。

DPを考えよう。合計で赤い R のボールが R 個、青い B のボールが B 個あるとする。

dp[r][b] := 結果の文字列で R を r 個、 B を b 個使うときの場合の数

と定義しよう。このとき次の文字列になりうることができる場合を考えよう。赤いボールの場合について考える。r+b 個の文字列が構成されていて、次の文字列になりうるのは、 r+1 番目の赤いボールを r+b 番以内のすぬけ君が持っている場合である。青いボールの場合も同様に考えることができる。

DP初期値は dp[0][0] = 1 である。

DP遷移は以下のように考えることができる。

  • dp[r+1][b] += dp[r][b]
  • dp[r][b+1] += dp[r][b]

解は dp[R][B] となる。

Submission #4277743 - Yahoo Programming Contest 2019

どこに着目して考察するべきだったか

操作を直接考えるのではなく、最終的な文字列を構成できる場合の数の考えると見通しがよくなる。

何がバグっていたか

得た知見(典型ポイント)

  • 状態を仮定して、次の状態へ遷移できるかどうか考える
  • 結果の場合の数を数え上げる

類題

Mujin Programming Challenge 2018：F - チーム分け

問題

https://atcoder.jp/contests/mujin-pc-2018/tasks/mujin_pc_2018_f

考え方

放送解説が秀逸。chokudaiさんが考察の進め方を解説している。

さて、まずは入力の数列をソートしても問題ないのでソートしておく。状態を定義するが、どのように状態を定義すればよいか難しい。

人ごとにグループの所属している状態を持つと、O(2^n) 程度の状態数になるのでそのようには考えない。誰がではなく、何人残っているか？であれば O(N) の状態数で考えることができる。残りの人数を状態として持つことを考える。

グループの人数を決め打つとどこからどこまでが対象なのか明確になる。人数の決め打ちは制約の厳しい状態から考えていく。人数が多い場合のほうが厳しく、グループになりうる人が上から決まっていく。よってDPの遷移を決めることができる。

dp[i][j] := i 人以上のグループまで作っていて、i 人以上のグループを許容する人が j 人残っているときの場合の数

と定義する。i-1 人のグループを k 個作るときすでに残っている j 人に加えて、i-1 人以上のグループになることができる人も新たにグループ分けの対象になる。それぞれ i 人以上のグループになることができる人の数を cnt[i] として求めておこう。

DPの初期値は dp[n+1][0] = 1 でDPの遷移は

\displaystyle dp[i-1][j + cnt[i-1] - (i-1) * k] += dp[i][j] * \prod_{i=1} {}_{j + cnt[i-1] - (i-1) * k} \mathrm{C}_{i-1} * \frac{1}{k!}

となる。このDPの遷移の形は類題のGroupingに似ている気がする。

解は dp[1][0] である。

Submission #4303359 - Mujin Programming Challenge 2018

どこに着目して考察するべきだったか

まずはソート。人ごとのグループ分けを考えるのではなく、人数で考えることがポイント。あとはグループ人数を決め打つことができるかどうか

何がバグっていたか

得た知見(典型ポイント)

  • ソートしても問題ないときはソートしておく
  • 何かを決め打つと状態が決まる（ある状態がどの状態に寄与するか）

類題

「みんなのプロコン」本選 オープンコンテスト：B - チーム決め

問題

https://atcoder.jp/contests/yahoo-procon2017-final-open/tasks/yahoo_procon2017_final_b

考え方

差の最大値を最小化したい。これはよくある典型問題で、最小化したい値 x を二分探索することで最小値を求めることができる。問題を言い換えると

「差を x とするとき、\{A_N\}, \{B_N\} を用いてペアを K つ以上作ることができるかどうか判定し、この x の最小値を求めよ」となる。

x が決まれば、貪欲法で求めることができる。\{A_N\}, \{B_N\} はソートしておく。各 A_i について A_i - x 以上の最小の B_j とマッチングさせることが最善である。ただし B_j \gt A_i + x となる場合はマッチングできない。そのようにマッチングさせていったときにペアが K つ以上できるかどうか求めれば良い。

Submission #4277378 - 「みんなのプロコン」本選 オープンコンテスト

どこに着目して考察するべきだったか

最大値の最小化は二分探索で解けることは典型問題なので、ぱっと思いつけないといけない。

何がバグっていたか

得た知見(典型ポイント)

  • 最大値の最小化(最小値の最大化)

類題