AtCoder Beginner Contest 137 D～F問題メモ

AtCoder Beginner Contest 137

• AtCoder Beginner Contest 137 解説放送 - YouTube

Eに嘘解法があったらしいとはいえ、A～Eを60分で200位、100分で360位はなかなか参加者レベルのインフレを感じる。

D - Summer Vacation

• $N$ 件の日雇いバイトがある
• $i$ 件目のバイトは働いてから $A_i$ 日後に $B_i$ 円が振り込まれる
• $M$ 日後に得ることのできる金額の最大値を求めよ
• 1日に受けられるバイトは1件まで
• 同じバイトは1回しか受けられない
• $1 \le N,M,A_i \le 10^5$
• $1 \le B_i \le 10^4$

たとえば $M$ 日まであと10日の段階で、11日後以降に報酬が得られるバイトを受けても意味が無い。

あと1日の段階では $A_i=1$ のものしか受ける意味が無いので、その中から報酬最大のものを受けるのがよい。

あと2日の段階では、$A_i \le 2$ のバイトが受けられる。 そのうち、明日受けるものをわざわざ今日受けなくてもいいので、 明日受けると決めたものを除いた中から報酬最大のものを受けるのがよい。

このように、制約が強い後ろの日から考える。 「受ける意味のあるバイト候補リスト」を持ち、$M$ まであと $k$ 日の時に、

• $A_i=k$ のバイトに新しく受ける意味が発生するので、候補に加える
• 候補から、報酬最大のものを受けると決めて、候補から除く

という処理を繰り返すとよい。この候補リストには、最大値を得る優先キューが使える。

キューが空になった時などの例外処理に注意。

E - Coins Respawn

• $N$ 頂点 $M$ 辺の有向グラフ
  • 自己辺や多重辺もあり得る
• $i$ 番目の辺は頂点 $A_i$ から $B_i$ へ向かう
• 辺を通ると $C_i$ ポイントを得られる。同じ辺を複数回通ればそのたびに $C_i$ ポイントを得られる
• 頂点 $N$ にボタンが置かれている
  • 必ずしもはじめて到着した時に押す必要は無く、訪れた好きなタイミングで押してよい
• 頂点1からスタートして頂点 $N$ のボタンを押した時、1度だけ以下の報酬を得られる
  • 報酬: ボタンを押すまでの獲得ポイント - (ボタンを押すまでに通過した辺の数 $\times P$(定数))
  • 上の式が負になる場合は、0とする
• 報酬の最大値が有限か判定し、有限の場合はそれを求めよ
• $2 \le N \le 2500$
• $1 \le M \le 5000$
• 頂点1から $N$ へは到達可能であることが保証される

ボタンを押した時に引かれるポイントは通過した辺の数に依存するので、辺ごとにコストに含めてしまってよい。

また、グラフ上で2点間の距離を求めるアルゴリズムは、だいたい最小値を求めるので、 今回のように最大値を求めたい場合は正負逆転して考える。

すると、辺の「コスト」は、$P-C_i$ として扱えばよさそう。

• 1から $N$ までの最小コストを求めれば、その正負逆転を元に戻した値が答えとなる
• 1から $N$ まで到達できる途中に負の閉路があれば、いくらでも最小値を更新できるので、有限ではない
  • 1から到達できない箇所や、$N$ へ到達できない箇所にある負の閉路は、最終的にボタンを押せないので、関係ない

最小コストを求めるには、リンクに負のコストが現れるのでDijkstraは使えず、Bellman-Fordを使うことになる。

Bellman-Fordは負の閉路があった場合に検出できる。

• 全辺を緩和するたびに「1頂点でも最短距離が更新されたか」を見て更新が無くなれば全頂点への距離が確定
• 閉路がないなら、頂点の数だけ緩和ループを回せば必ず確定するはず
• →更新が無くならない場合は、そこに負の閉路がある

今回の場合「その閉路を通った後 $N$ に行けるか？」を確かめる必要がある。以下の2つの方法が考えられる。

• あらかじめ頂点 $N$ から逆向きに探索し「$N$ に到達可能な頂点」を調べ、その頂点だけでBellman-Fordを行う
• $N$ 回の緩和ループ後に更新のあった頂点から探索し、$N$ に到達可能か調べる

1から到達できない閉路は、Bellman-Fordでも検出されないので特別な考慮の必要は無い。

F - Polynomial Construction

• 素数 $p$ と、'0'または'1'からなる長さ $p$ の数列 $a_0,a_1,...,a_{p-1}$
• 以下の条件を満たす長さ $p$ の数列 $b_0,b_1,...,b_{p-1}$ を求めよ
  • 関数 $\displaystyle f(x)=b_0 + b_1x + b_2x^2 + b_3x^3 + ... + b_{p-1}x^{p-1}=\sum^{p-1}_{i=0}{b_ix^i}$ を定義
  • 各 $i(0 \le i \lt p)$ につき、$a_i \equiv f(i) \mod{p}$
  • 各 $i(0 \le i \lt p)$ につき、$0 \le b_i \lt p$
• $2 \le p \le 2999$

愚直には、連立方程式が $p$ 個あり、変数が $p$ 個あるので、行列として考えて、掃き出し法で解ける。ただし、計算量は $O(p^3)$ となり、間に合わない。

行列の各行が全て等比数列の場合に特化した研究があるらしく、ヴァンデルモンドの行列式というらしい。

この場合、逆行列を $O(p^2)$ で求められるので、間に合う。というか上記Wikipediaの「応用」で述べられていることが、そのまま問題となっている。 具体的な逆行列の求め方は、英語版のVandermonde_matrixあたりに載ってそう？（未確認）

で、この解法はまあ知ってるか知ってないか感が強くて、思いつくのは厳しい。

ただし、今回の場合は、もう少しヒラメキ寄りの解法が使えて、それが解説pdfで解説されている。

$x(0 \le x \lt p)$ に対して、フェルマーの小定理から以下が言える。

$$x^{p-1} \equiv \left\{ \begin{array}{ll} 0 & (x=0) \\ 1 \mod{p} & (otherwise) \end{array} \right.$$

なので、たとえば $x=3$ の時に $f(x)=1$ としたい場合、

$$f(x)=1-(x-3)^{p-1}$$

とすると、綺麗に $x=3$ の時のみ1、後は0 となる。

さらにこれは好きなだけ繋げられて、$x=3,5,8$ の時だと以下のようにできる。

$$f(x)=1-(x-3)^{p-1}+1-(x-5)^{p-1}+1-(x-8)^{p-1}$$

なので、$a_i=1$ である $i$ に対して $1-(x-i)^{p-1}$ を繋げることによって、目的の関数が得られる。

あとはこれを展開して、各係数 $b_i$ を求める。

$(x+k)^{p-1}$ の展開形における $x$ の係数は、二項係数を使って

$$\displaystyle (x+k)^{p-1} = x^{p-1} + \binom{p-1}{1}x^{p-2}k + \binom{p-1}{2}x^{p-3}k^2 + ... + \binom{p-1}{p-2}xk^{p-2} + k^{p-1}$$

なので、二項係数と $k$ の等比数列 $1,k,k^2,...,k^{p-1}$ を掛け合わせると、各項の係数に加算すべき値が分かる。

計算量を把握すると、

• 二項係数は共通なので事前計算して$O(p \log{p})$
• 以下を $a_i=1$ である $i$ ごとに処理
  • $b_0$ に1を加算
  • $-i$ の等比数列を求めて、二項係数と掛け合わせて、各 $b_j$ から減算
  • $O(p^2)$

Pythonではなかなか $O(p^2)$ が厳しいが、NumPyを使って等比数列を $k=0～p-1$ について一括で求めるようにすれば間に合う。

というか、等比数列を必要な $k$ ごとに個別に求めるとTLEだったのに、一括で計算すると不要な $k$ まで含んでいるにもかかわらず500ms程度にまで高速化されたので、ほぉ～やっぱNumPyは速いんすねぇ～となる。