blog.bouzuya.net

2022-03-11 アルゴリズムと数学 演習問題集 079, 080 を解いた

アルゴリズムと数学 演習問題集 079 - ModSum を解いた。

問題: https://atcoder.jp/contests/math-and-algorithm/tasks/abc139_d

ABC139 D と同じ問題。

x mod P_i の最大値は P_i - 1 なので x を自由に選べるのであれば \sum_{i=1}^{N} P_i-1 にできる。試しに x が P_i - 1 になるよう 1 つずつずらして配置してみると N > 1 の入力値なら実現できることに気づく。 N = 1 のときはずらせないので 0 になる (このときも式としては同じで良い) 。

N = 1
1 mod 1 = 0

N = 2
1 mod 2 = 1
2 mod 1 = 0

N = 4
1 mod 2 = 1
2 mod 3 = 2
3 mod 4 = 3
4 mod 1 = 0

あとは初項 0 末項 N - 1 公差 1 項数 N の等差数列の和なので (N - 1) * N / 2 で指示通り O(1) にできる。

提出: https://atcoder.jp/contests/math-and-algorithm/submissions/30006107 解説: https://atcoder.jp/contests/abc139/tasks/abc139_d/editorial

アルゴリズムと数学 演習問題集 080 - Difference Optimization 2 を解いた。

問題: https://atcoder.jp/contests/math-and-algorithm/tasks/math_and_algorithm_bl

078 - Difference Optimization 1 (2022-03-10) を難しくした問題。同様に x を頂点とする N 頂点 M 辺のグラフで考える。

まず実際の値が割り当てられているのは x_1 = 0 だけなので x_1 から到達できない頂点は任意の値を設定できる。つまり x_n が x_1 から到達できないなら -1 になる。

そうでない場合は x_n への最短距離が最大値になる。条件は可能なら最大値で使いたいので辺の重み (距離) として C_i で考える。最短距離の制約よりも大きくすると最短距離を構成する辺のいずれかが条件を満たせなくなるので最大値は最短距離になる。

あとはダイクストラ法などで x_1 から x_n への最短距離を求めれば良い。

提出: https://atcoder.jp/contests/math-and-algorithm/submissions/30006478

『のび太の宇宙小戦争』を観た。

今日のコミット。