ganmo::cout

競技プログラミング始めました

AtCoder Beginner Contest 143

atcoder.jp

A - Curtain (100点)

atcoder.jp
カーテンは2枚あるので覆うことのできる長さは2Bで、窓の長さがAなのでmax\{0,A-2B\}を出力すればO(1)でACが取れます
拙解 (C++14): Submission #8019173 - AtCoder Beginner Contest 143

B - TAKOYAKI FESTIVAL 2019 (200点)

atcoder.jp
Nが小さいので食べ方を全探索してもO(N^2)で間に合います
\displaystyle\begin{align*}
\sum_{1 \le i \lt j \le N} d_i d_j &= \frac12 \sum_{i \ne j} d_i d_j \\
&= \frac12 \left( \sum_{i, j} d_i d_j - \sum_{i = j} d_i d_j \right) \\
&= \frac12 \left\{ \left( \sum_{i=1}^N d_i \right)^2 + \sum_{i=1}^N d_i^2 \right\}
\end{align*}
と変形するとO(N)でもできるみたいです
拙解 (C++14、O(N^2)解法): Submission #8021063 - AtCoder Beginner Contest 143
拙解 (C++14、O(N)解法): Submission #8050198 - AtCoder Beginner Contest 143

C - Slimes (300点)

atcoder.jp
隣り合う同じ色のスライムは最終的に1匹になるので、ランレングス圧縮をした後の長さがそのまま答えになります
これはO(N)で求められるので制約N\le 10^5にも間に合います
ランレングス圧縮は色々便利なのでライブラリなどを作っておくと便利です
拙解 (C++14): Submission #8022385 - AtCoder Beginner Contest 143

D - Triangles (400点)

atcoder.jp
棒の選び方は全部で{}_N C_3=O(N^3)通りあるので、愚直に全探索すると間に合いません(※C++などの十分早い言語で高速化の工夫をすれば間に合うようです)
ですが、最も長い辺でない2辺を選べば残り1辺の長さの範囲が決まります
a \le b \le cとすると、三角形のできる条件はb-a \lt c \lt b+aとなります
なので、\{L_i\}をソートしておいてすべての2辺の組み合わせに対して二分探索で最も長い辺の数を求めるとO(N^2 \log N)となり間に合います
拙解 (C++14): Submission #8030461 - AtCoder Beginner Contest 143

E - Travel by Car (500点)

atcoder.jp
必ずしも最短経路を通ればいいということではなく、例えば

f:id:aprilganmo:20191104140351p:plain
最短経路が給油回数最小にならない例
このような場合、上側を通ると距離は最小(9)なものの給油回数は2回となり、下側を通ると距離は長い(10)ものの給油は1回で済みます
そのため辺の長さの合計ではなく給油回数を距離とした新しいグラフを作る必要があります
今回は頂点がN \le 300個しかないのでO(N^3)ワーシャルフロイドを使っても間に合います
給油1回で行けるところに辺を貼って新しいグラフを作り、そのうえでさらにワーシャルフロイドをすると、任意の頂点から任意の頂点へ何回の給油で行けるかがすべて格納されたテーブルが出来上がりました!よって各クエリはO(1)で求められます
前準備O(N^3)、全クエリQ \times O(1) = O(N^2)の合計O(N^3)でACです

拙解 (C++14): Submission #8035455 - AtCoder Beginner Contest 143

F - Distinct Numbers (600点)

(手を付けてません)