AtCoder Beginner Contest 137
Updated:
- Review: 2020-06-02
Source codes
Solutions
A - +-x
$\max(A + B, A - B, AB)$ を出力する。
B - One Clue
$X - K + 1, \dots, X + K - 1$ を出力する。
C - Green Bin
$S _ 0, S _ 1$ がアナグラムで一致するとは、文字列をソートすると同じ文字列になるという意味である。よって map<string, ll> M; に文字列を突っ込んでいって、 $c(c - 1)/2$ の総和を取ればよろしい。
D - Summer Vacation
それぞれの仕事 $(A _ i, B _ i)$ について、この仕事は第 $M - B _ i$ 日目よりも前に着手することがお給料が発生することの必要十分条件である。そこで priority_queue<ll> Q; を宣言し、 $i = M - 1, M - 2, \dots, 0$ に対し、 $i$ 日目にやれる仕事を $Q$ に突っ込む。そして $Q.top()$ の仕事をやって $Q.pop()$ する。これで答えが出る。
実装上のポイント
仕事は日付を key に vector で持っておくべきである。つまり 2 次元 vector を使う。
vector<vector<int>> V(M + 1);
for (auto i = 0; i < N; ++i)
{
int A, B;
cin >> A >> B;
if (A > M)
{
continue;
}
V[A].push_back(B);
}
ポイント
スケジューリングは終端でソートして priority_queue を使うことが多い。
E - Coins Respawn
$0$-indexed とする。
第一段階
この問題では、まず「 $0$ から到達可能であり、 $N - 1$ に到達可能である」頂点以外には全く用がないことがわかる。そこで以下の議論では、そのような頂点を取り除くことにする。これらは DFS をそれぞれ行うことで判定ができる。
第二段階
この問題では最後の $TP$ を引く動作は、各辺の重みを $-P$ しておくことで不要となる。まずこの言い換えをしておく。
この問題は辺の重みを長さと考えると、最長の経路を求める問題であると考えることができる。すると重みを $-1$ 倍することにより、最短経路の問題へと帰着できる。しかし辺の長さは負を許しており、負閉路の存在をも否定できていない。負閉路が存在する場合、答えは $-1$ である。したがってベルマンフォード法を使用することになる。
ベルマンフォード法の実装
$M$ 個の辺を最大 $N + 1$ 回捜索することにする。各回において最短距離が update されたかをみて、そうでなかったら終わりである。これは最短経路を取る場合はその経路では $N$ 頂点しか経由しないからである。 $N + 1$ 回以上やっても更新が続くということは、負閉路ががあるということである。
ll bf()
{
vector<ll> D(N, infty);
D[0] = 0;
bool updated{false};
for (auto t = 0; t < N + 2; ++t)
{
updated = false;
for (auto const &e : E)
{
if (!e.valid)
{
continue;
}
auto tmp{D[e.src] + e.cost};
if (D[e.dst] > tmp)
{
D[e.dst] = tmp;
updated = true;
}
}
if (!updated)
{
return max(0LL, -D[N - 1]);
}
if (t == N + 1)
{
return -1;
}
}
assert(false);
return -2;
}
ポイント
基本事項の積み重ねで答えがでる。
F - Polynomial Construction
模範解答
フェルマーの小定理により、 $i \in \mathbb{Z}/p\mathbb{Z}$ について、
\[
1 - (x - i)^{p - 1} =
\begin{cases}
0 & x \neq i, \\
1 & x = i.
\end{cases}
\]
である。指定された $i$ について、この総和を取ればよろしい。実装においては、二項定理を使って
\[
1 - \sum _ {j = 0} ^ {p - 1}
\begin{pmatrix}
p - 1 \\
j
\end{pmatrix}
(- i) ^ j x ^ {p - 1 - j}
\]
を計算して加えればよろしい。計算量は $O(p^2)$ である。
別解
ラグランジュ補間多項式を使ってもできる。
\[
F(x) = x(x - 1) \dots (x - (p - 1))
\]
とする。 $k \in \mathbb{Z} / p \mathbb{Z}$ に対し、 $g _ k (x) = F(x) / (x - k)$ とすると、
\[
\frac{g _ k (x)}{g _ k (k)} =
\begin{cases}
0 & x \neq k, \\
1 & x = k.
\end{cases}
\]
である。この総和を取ればよろしい。
$x^p = x$ を用いると $F(x)$ は $\deg F \leq p - 1$ の形で書ける。すると $F(x)$ は根を $p$ 個数持っているので、因数定理により $F(x) = 0$ が従う。この議論は詳しくは Tenka1 Programmer Contest 2019 E - Polynomial Divisors の解説に書いてある。よって $F(x) = 0 = x^p - x$ とすることができる。これを組立除法の要領で多項式の割り算をすると $O(p^2)$ で解答が出る。
ポイント
ギリギリ答えが出せた。 $N \approx 2000$ だと $O(N^3)$ は無理、 bitset を用いるか $O(N^2 \log N)$ 以下に落とさなければ勝ち目がない。
Others
ABCF が解けた。レーティングも溶けた。
Review: 2020-06-10
A - sample: 3, tle: 2.000, time: 02:58, from_submit: 80:13
B - sample: 3, tle: 2.000, time: 01:21, from_submit: 78:52
C - sample: 3, tle: 2.000, time: 03:33, from_submit: 75:19
D - sample: 3, tle: 2.000, time: 10:37, from_submit: 64:41
E - sample: 3, tle: 2.000, time: 40:59, from_submit: 23:43
F - sample: 3, tle: 2.000, time: 23:43, from_submit: 00:00