https://atcoder.jp/contests/abc133/tasks/abc133_f 前提知識 LCA クエリ先読み 解説 https://atcoder.jp/contests/abc133/submissions/6312857重要なこととして、制約を簡単にした問題が解けないか考えてみる。 今回で言うと、辺の長さの変更が難しいので…

https://atcoder.jp/contests/abc133/tasks/abc133_e 解説 https://atcoder.jp/contests/abc133/submissions/6312375木でmod10^9+7なので、とりあえず木DPを疑う。 dp[cu] := cuを根とする部分木での塗り方の総数 これをベースにまずは考えてみよう。 正直こ…

https://atcoder.jp/contests/abc133/tasks/abc133_d 解説 https://atcoder.jp/contests/abc133/submissions/6312080各山にx1, x2, x3, ... 降ったとする。 すると、ダムには(x1+x2)/2=A1のように溜まっていく。 割り算は面倒なので、全部二倍しておこう。 1…

https://atcoder.jp/contests/abc133/tasks/abc133_c 解説 https://atcoder.jp/contests/abc133/submissions/6313028300点問題にしては難しい問題に見える。 (i×j) % 2019 = (i % 2019) * (j % 2019) となる。 理論的な最小値は0であり、これを目指すことを…

https://atcoder.jp/contests/abc133/tasks/abc133_b 解説 https://atcoder.jp/contests/abc133/submissions/6311855(i,j)の組は全探索できるので、全探索して、距離が整数となる組を数え上げよう。 ルートの解決が少し厄介であるので、距離^2が平方数である…

https://atcoder.jp/contests/abc133/tasks/abc133_a 解説 https://atcoder.jp/contests/abc133/submissions/6311780選択肢は2つある。全員電車か、全員タクシーである。 よって、min(N * A, B)が答え。 int N, A, B; //-----------------------------------…