[AtCoder 参加感想] 2019/08/10:ABC 137

  A B C D E F
問題文
自分の提出
結果 AC AC AC AC AC AC

スポンサーリンク

全体感想

108分6完(4ペナルティ)で53位でした。

D,E も含めてなかなか難しかったです。

たぶん、D,E,Fはほぼ同じような類型が過去問(atcoder or 他)にあるのではないでしょうか?直接的な心当たりはないですが…。
まぁ、そういうのは嫌いじゃないです。過去問勉強がレート向上に分かりやすく反映されるってことですし。

問題C – Green Bin

アナグラムの判定を行うには、例えばソートして同一性を判定すればよいです。

‘acornistnt’ -> (sort) -> ‘acinnorstt’
‘constraint’ -> (sort) -> ‘acinnorstt’

ソートした結果を集計すると、アナグラム文字列の個数が判定できます。集計には、defaultdictやCounterが使えます。

辞書等のキーに使う場合、listではなくtupleや文字列にしましょう(hash関数を備えた型を使う)。

問題D – Summer Vacation

仕事 $(A,B)$ は、締切が $M-A$ の仕事と認識します。各 $x$ に対して、「締切が $x$ 日目以前のものをとるときの最善の取り方」を更新していきます。

$x-1$ 日目までに取得できる最大価値が $b_1,\ldots,b_k$ であるとき、$x$ 日目までの仕事(価値 $B$)は次のようにします:

・$k< x+1$ なら、任意の仕事を追加できる。
・$k = x+1$ なら、$B$ がどの $b_i$ よりも小さければ追加する利点なし。ある $b_i$ より大きければ、これまで行う予定にしていた仕事のうち最小価値のものをキャンセルして、その仕事を追加する。

価値の列を、最小値が分かるように追加・削除できればよいので、heapq が使えます。それぞれ heappush, heappushpop を使って実装しました(heappushpop は、実現できることは、heappush → heappopと同一ですが、パフォーマンスが良いです)

問題E – Coins Respawn

最後の支払いは、1回辺を使用するたびにその都度 $P$ を支払うとしても同じです。したがって、辺に重み $C_i – P$ を乗せると、経過時間を無視して、最長重み経路に帰着できます。

実際には、$-1$ 倍して、最小重み経路の問題として解きました。これは、有名なbellman_fordアルゴリズムにより解けます。というか、かなりそのまんまに近い出題ですね。

scipy.sparse.csgraph.bellman_fordを利用しようとしましたが、何度か失敗しました。ひとつの理由は、負閉路の検出に関するもので、 [入力例3] の場合などの負閉路を拾ってエラーを返してしまいます。この負閉路は、2頂点間距離の計算には悪さをしないので、「負閉路エラーでした。距離は計算していません。」というのでは困ります。

終点から始点に辺を張ったときの、強連結成分に限定すればよいとも思ったのですが、うまくいかず。

結局、とりあえずpypyで自作して通しました。要復習。

問題F – Polynomial Construction

$0\leqq i < p$ に対して
\[ f_i(x) = \begin{cases} 1 & ( x = i)\\0 & (他) \end{cases}\]
というような多項式 $f_i$ を構成することを考えます。
代入は多項式の和と交換するので、$a_i = 1$ となる $i$ に対して$f_i$ の和をとったものが答えとなります。

この $f_i$ は、明示的な式で表すことができます。例えば $p = 7$ で $i = 2$ ならば、
\[ f_2 = \text{(定数)} \times x(x-1)(x-3)(x-4)(x-5)(x-6) \]
などと書けます(因数定理。高校数学では実数や複素数範囲での因数定理を学ぶが、任意の体、例えば $\mathbb{F}_p$ 上の多項式についても成り立つ)。この「定数」を求めたり、右辺の「1つ飛ばしの積」を計算するのが課題です。
「1つ飛ばしの積」を全部計算する場合には、ひとつの考え方としては、「左からの累積」「右からの累積」を順次計算していくと、多項式の積の計算を $O(p)$ やる形で計算できます。この方法だと、最後に両側からの積をマージするところで、$O(p)$ 次式の積を $p$ 回計算する必要があり、計算量が $O(p^3)$ になります。手元PCでは、2秒以内に実行できましたが、AtCoderではTLEになりました。→ ■
※ 大きい多項式の積を、np.convolveからFFTに置き換えれば通るかも?思考から抜けていましたが、あとで試してみます。 → AC 
結局 $f_i$ にはより易しい明示公式がありました。次が成り立ちます:
\[ f_i(x) = – \frac{x^p-x}{x-i} = – \frac{(x-i)^p – (x-i)}{x-i} = 1 – (x-i)^{p-1}. \]
・1番目の等号は因数定理。$x^p-x$は$x=0,1,\ldots,p-1$を全て根に持つ。
・2番目の等号は$(a\pm b)^p = a^p\pm b ^p$(ただし$\pmod{p}$における等号).

あるいは結論だけを確かめるならば、最右辺に $x = a$ を代入してみるとよいです。Fermatの小定理より、$a=i$ の場合のみ $1$、他は $0$ となります。
さらに、次が成り立ちます:
\[ (x-1)^{p-1} = \frac{(x-1)^p}{x-1} = \frac{x^p-1}{x-1} = x^{p-1} + x^{p-2} + \cdots + x + 1.\]
\[ (x-i)^{p-1} = \frac{(x-i)^p}{x-i} = \frac{x^p-i^p}{x-i} = x^{p-1} + ix^{p-2} + \cdots + i^{p-2}x + i^{p-1}.\]
はじめは二項係数を計算して展開したのですが、計算結果を見て気づきました。

したがって、$i^k\pmod{p}$ を全ての $k$ に対して計算することがすなわち $f_i$ を計算することに対応します。

このことを用いると、1件あたりの $f_i$ が $O(p)$ で計算できて、問題全体としては $O(p^2)$ で答を出すことができます。

タイトルとURLをコピーしました