| 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
\[ 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つ飛ばしの積」を計算するのが課題です。
あるいは結論だけを確かめるならば、最右辺に $x = a$ を代入してみるとよいです。Fermatの小定理より、$a=i$ の場合のみ $1$、他は $0$ となります。
このことを用いると、1件あたりの $f_i$ が $O(p)$ で計算できて、問題全体としては $O(p^2)$ で答を出すことができます。
