tarattataのブログ

競プロの解法などをメモ。気の向いたときだけ書きます。

Yukicoder No.1436 Rgaph

yukicoder.me

問題の概要

自己ループと二重辺を含まない N 頂点 M 辺の有向グラフが与えられる。各辺に +1 または -1 という値を割り当てて、「任意の 2 頂点 u, v ( u \neq v ) に対して、 u から v までのパスで辺の値の合計が０になるものが存在する」ようにせよ。そのような +1 と -1 の割り当てが不可能な場合は -1 を出力せよ。

制約

2 \le N \le 1000
1 \le M \le 2000

解法

条件を満たすような +1 と -1 の割り当てが可能であるためには、以下の(A)(B)の両方を満たすことが必要です。
　(A) 強連結
　(B) 奇数長の初等的サイクルが存在して、かつ、そのサイクルに含まれない辺が1本以上ある
　（※初等的サイクルとは、始終点が一致していて、それ以外に同じ頂点が存在しないようなパスのこと）

＜理由＞
(A)は、任意の2点 u, v ( u \neq v ) に対して u から v までのパスが存在するため。
(B)は、もし奇数長のサイクルが存在しないと仮定すると、ある点Sを固定したとき、Sから各点へのパスの長さの偶奇が固定されてしまい（二部グラフ）、Sから奇数距離の点までのパスは +1 と -1 を同じ個数にできなくなるため。奇数長サイクルがある場合、そこから奇数長の初等的サイクルが存在することも言える。また奇数長の初等的サイクルがあったとしてもそれ以外に辺が一本もなければ、一周すると値の合計が正の数または負の数になるので、例えば一周が正の数だった場合には +1 を割り当てた辺の始点から終点まで、合計値０で移動することができない。

実は、上記(A)(B)の両方を満たしていれば、条件を満たすような +1 と -1 の割り当てを構成できます。
具体的には、例えば以下のようにします。

　(B)を満たす奇数長サイクル C を１つ固定し、その長さを 2k+1 とする。 (k \ge 1)
　 C 上の頂点のうち入次数が 2 以上のものを点 P とする（そのような点が必ず存在する）。
　 P からサイクル C をたどって一周するとき、最初の k 個の辺を -1、それ以外の辺を +1 とする。
　 C に属さない辺は全て -1 とする。
このようにしておくと
　 C を一周したときの辺の値の合計が+1。
　 C 上を P から P 以外の点まで移動したときの辺の合計値は必ず０以下。
になっています。
f:id:tarattata1:20210320165757p:plain

これが正しい割り当てになっていることの説明：
Pを終点とするような C に属さない辺に着目すると、 C 上の点 Q から点 P までの、 C に属さない辺のみからなるパスが存在することがわかりますが、 この点 Q が点 P と異なる場合でも、同じ場合でも、一周の値が 1 のループ C の他に、一周の値が負のループが存在することがわかるので、題意を満たします。
f:id:tarattata1:20210320165807p:plainf:id:tarattata1:20210320165822p:plain

というわけで、解答する上では、強連結であるかどうかのチェックの他、「奇数長のサイクルを探す」ことができればよいことになります。
どうやればよいか迷ったのですが、各点からBFSしてループを検出する方針をとりつつ、頂点を倍加する形にしました。（ある頂点について、始点から偶数回でたどり着く場合と、奇数回でたどり着く場合を区別する）

解答例

https://yukicoder.me/submissions/632541

AGC022 B GCD Sequence

atcoder.jp

問題の概要

Nが与えられたとき、サイズN、各要素が30000以下の、以下のような数列を１つ求めよ。
- 全ての要素は相異なる
- 全ての要素の gcd が1
- 全要素の和を S とするとき、全ての i に対して gcd(a_{i}, S-a_{i}) ≠ 1

制約

3 \le N \le 20000

解法

まず最初に、 gcd(a_{i}, S-a_{i}) ≠ 1 という条件は gcd(a_{i}, S) ≠ 1 と書き換えてよいことがわかります。

gcdが1という条件については、2と3を必ず選んでおけば達成できるので、あとは残りの要素を2の倍数や3の倍数から選んで、和 Sを6の倍数にできれば達成できます。
30000以下の正整数30000個の中から最大20000個を選ぶというのは、かなり個数が多いですが、「2の倍数または3の倍数」は 1以上30000以下の整数のうち 20000個あるので、わりと達成できそうです。
難しかったら5の倍数も入れて、Sを30の倍数にすればよさそう。

ただ、この解法だと、細部をつめて実装するのが、そこそこ大変そうです。

考え続けていたら、以下の解が思い浮かびました。

数列の要素として、以下のように2個ずつのペアを選ぶ。
「x」 と 「30000-x」（ただしxは15000未満で、15000と互いに素でない正整数）
N が偶数なら、このようなペアを選んで要素数が Nになったら終了。
N が奇数なら、このようなペアを選んで要素数を N-1 にした後、「15000」を要素として追加。

こうすれば、和が15000の倍数になり、条件を満たします。

解答例

https://atcoder.jp/contests/agc022/submissions/10973698

Yukicoder 980 Fibonacci Convolution Hard

yukicoder.me

問題の概要

数列 \lbrace a_{n} \rbrace (n \ge 1)を以下で定める。
a_{1}=0,   a_{2}=1,   a_{n} = p⋅a_{n−1} + a_{n-2} (n \ge 3)
正整数 q_{i} (i=1,2,..,Q) に対し、 \displaystyle \sum_{s+t=q_{i}, s,t \ge 1} a_{s}⋅a_{t} を 10^{9}+7 で割った余りを求めよ。

制約

1 \le p \le 10^{9}
1 \le Q \le 2⋅10^{5}
2 \le q_{i} \le 2⋅10^{6}

解法

この問題では q_{i} が Q 個与えられますが、 q_{i} のとりうる値の個数と Q とではオーダーがあまり変わらないので、とりうる値全てについて答を求めることにします。つまり、 N=2⋅10^{6} に対して、 N 以下の q 全てに対して答を求めます。

f:id:tarattata1:20200213121747p:plain

上図の青枠で囲ったような部分の和 S_{i} を全て求めるという問題になりますが、愚直にやると O(N^{2}) かかるので、何か工夫が必要です。このようなとき、１つの方法としては、 S_{2}, S_{3}, S_{4},.. というように順に求めていきながら、少し前（１つ前とか）の結果を使って簡単に S_{i} が計算できると嬉しいです。そこで、数列の漸化式を見て、うまくやれるか考えてみましょう。

数列の漸化式 a_{n} = p⋅a_{n−1} + a_{n-2} を以下のように書いてみます。

(A,B,C) に関する条件 P：「 A+p⋅B＝C」
を考えたとき、 (a_{n-2}, a_{n-1}, a_{n}) は条件を満たす

すると、条件 P は、
① (A,B,C) が条件を満たすとき、定数倍した (rA, rB, rC) も条件を満たす
② (A_{1},B_{1},C_{1})と (A_{2},B_{2},C_{2})が条件を満たすとき、 (A_{1}+A_{2}, B_{1}+B_{2},　C_{1}+C_{2}) も条件を満たす
という性質があります。（線形性）

f:id:tarattata1:20200213121805p:plain

さて、上図の各赤丸部分が条件 P を満たすので、それらの和をとると、
(S_{7},　S_{8}-a_{1}⋅a_{7},　S_{9}-a_{1}⋅a_{8}-a_{2}⋅a_{7}）
も条件 P を満たします。
よって、 a_{1}=0, a_{2}=1 を使うと、 S_{9}=p⋅S_{8}+S_{7}+a_{7} とわかります。
同様にして、
S_{n}=p⋅S_{n-1}+S_{n-2}+a_{n-2} (n \ge 3)
とわかるので、順に S_{i} を求めることができます。

解答例

https://yukicoder.me/submissions/429073

Yukicoder 984 Inversion

yukicoder.me

問題の概要

素数 P と 正整数 N が与えられる。
数列 a_{i}=(i ⋅ N) \bmod P   (i=1,2,..,N)
について、その転倒数の偶奇を求めよ。（偶なら0、奇なら1を出力）
※ \bmod P は、 P で割った余り

制約

2 \le P \le 2^{31}-1
1 \le N \le P-1

解法

例えば、 P=3, N=13 の場合、数列は以下のようになります。
  3, 6, 9, 12, 2, 5, 8, 11, 1, 4, 7, 10
この数列の転倒数の偶奇ということは、この数列（順列）を i→a_{i} という置換とみなしたときに偶置換か奇置換か、を求める問題です。

偶置換か奇置換かの判定は、例えば、サイクルを観察するとわかります。
一般に、ある置換をサイクル(巡回置換)に分解したとき、その長さを L_{1}, L_{2},..,L_{m} とすると、 \sum (L_{i}-1) の偶奇が、偶置換か奇置換かの答になります（巡回置換を互換の積に表せばよい）。 例えば上の例では、 (1,3,9), (2, 6, 5), (4, 12, 10), (7, 8, 11) という 4つのサイクル（巡回置換）に分解されるので、偶置換とわかります。

今回の問題では、1を含むサイクルは集合としては A=\lbrace N^{i}\rbrace で、その要素数を M とおくと、他のサイクルも（例えば要素 a を含むサイクルは a⋅A という形になって）要素数が M になるので、 Mは (P-1) の約数で、 (M-1)⋅\frac{P-1}{M} の偶奇が答になります。

あとは Mを求められればよいのですが、 N^{i} \bmod P が 1 に等しくなるような最小の正整数 i を求めるという話なので、Baby-step Giant-step algorithm などで解くことができます。

※ 実は、 P が奇素数の場合には、 (M-1)⋅\frac{P-1}{M} が偶数であることは \frac{P-1}{M} が偶数であることと同値になり、 N が P の平方剰余であることと同値になるので、それを使って判定することもできます。（ N^{\frac{p-1}{2}} \bmod P が1か否かで判定）

※ 数学的な書き方では、 P が奇素数の場合、 (Z/pZ)^{×} に対して要素 N を生成元とする巡回部分群を考えて、それによる商群の位数の偶奇を答えるという問題でした。

解答例

https://yukicoder.me/submissions/428793

Yukicoder 978 Fibonacci Convolution Easy

yukicoder.me

問題の概要

数列 \lbrace a_{n} \rbrace (n \ge 1)を以下で定める。
a_{1}=0,   a_{2}=1,   a_{n} = p⋅a_{n−1} + a_{n-2} (n \ge 3)
このとき \displaystyle \sum_{i=1}^{N} \sum_{j=1}^{i} a_{i}⋅a_{j} を 10^{9}+7 で割った余りを求めよ。

制約

1 \le N \le 2000000
1 \le p \le 10^{9}

解法

求める式は、以下のものです。

    a_{1}⋅a_{1}
  + a_{2}⋅a_{1} + a_{2}⋅a_{2}
  + a_{3}⋅a_{1} + a_{3}⋅a_{2} + a_{3}⋅a_{3}
  + …
  + a_{N}⋅a_{1} + a_{N}⋅a_{2} + a_{N}⋅a_{3} + ... + a_{N}⋅a_{N}

これを以下のように書き換えます。

    a_{1} ⋅ (a_{1})
  + a_{2} ⋅ (a_{1} + a_{2})
  + a_{3} ⋅ (a_{1} + a_{2} + a_{3})
  + …
  + a_{N} ⋅ (a_{1} + a_{2} + a_{3} + ... + a_{N})

最初に各 a_{i} を求めた後、 (a_{1}), (a_{1} + a_{2}) , ... , (a_{1} + a_{2} + a_{3} +... + a_{N}) という部分は順に O(N) で計算できるので、 全体でも O(N) で計算できます。


他の解法

\frac{(a_{1} + a_{2} + a_{3} +... + a_{N})^{2} - (a_{1}^{2} + a_{2}^{2} + a_{3}^{2} +... + a_{N}^{2})}{2} でも計算できます。
この式変形は、ときどき見ますね。（ここ半年で競プロで3回くらい見ました）

コメント

テスターをやりました。慣れた人なら爆速で解けるだろうと予想していましたが、実際その通りでした。 難易度は★２つでよかったかも。

解答例

https://yukicoder.me/submissions/422888