AtCoder Beginner Contest 143
A - Curtain (100点)
atcoder.jp
カーテンは2枚あるので覆うことのできる長さはで、窓の長さがなのでを出力すればでACが取れます
拙解 (C++14): Submission #8019173 - AtCoder Beginner Contest 143
B - TAKOYAKI FESTIVAL 2019 (200点)
atcoder.jp
が小さいので食べ方を全探索してもで間に合います
と変形するとでもできるみたいです
拙解 (C++14、解法): Submission #8021063 - AtCoder Beginner Contest 143
拙解 (C++14、解法): Submission #8050198 - AtCoder Beginner Contest 143
C - Slimes (300点)
atcoder.jp
隣り合う同じ色のスライムは最終的に1匹になるので、ランレングス圧縮をした後の長さがそのまま答えになります
これはで求められるので制約にも間に合います
ランレングス圧縮は色々便利なのでライブラリなどを作っておくと便利です
拙解 (C++14): Submission #8022385 - AtCoder Beginner Contest 143
D - Triangles (400点)
atcoder.jp
棒の選び方は全部で通りあるので、愚直に全探索すると間に合いません(※C++などの十分早い言語で高速化の工夫をすれば間に合うようです)
ですが、最も長い辺でない2辺を選べば残り1辺の長さの範囲が決まります
とすると、三角形のできる条件はとなります
なので、をソートしておいてすべての2辺の組み合わせに対して二分探索で最も長い辺の数を求めるととなり間に合います
拙解 (C++14): Submission #8030461 - AtCoder Beginner Contest 143
E - Travel by Car (500点)
atcoder.jp
必ずしも最短経路を通ればいいということではなく、例えばこのような場合、上側を通ると距離は最小(9)なものの給油回数は2回となり、下側を通ると距離は長い(10)ものの給油は1回で済みます
そのため辺の長さの合計ではなく給油回数を距離とした新しいグラフを作る必要があります
今回は頂点が個しかないのでのワーシャルフロイドを使っても間に合います
給油1回で行けるところに辺を貼って新しいグラフを作り、そのうえでさらにワーシャルフロイドをすると、任意の頂点から任意の頂点へ何回の給油で行けるかがすべて格納されたテーブルが出来上がりました!よって各クエリはで求められます
前準備、全クエリの合計でACです
拙解 (C++14): Submission #8035455 - AtCoder Beginner Contest 143
F - Distinct Numbers (600点)
(手を付けてません)