バチャ記録&自分用解説 Codeforces Round #628 (Div. 2)

Codeforces Round #628 (Div. 2)

f:id:SayakaAmemiya:20200317221038p:plain

Div2だから適当に全完出来るかにゃーとか思いながらバチャに臨んだのれふが, すごい回だった……

後ろ2問, もっと解かれると思って出題したのかにゃ……という感じの問題ではあった(解説見たら理解できる類だった)のれふが, 厳しい……

奇しくも同日に開催されたパナソニックコンに続き, Rated対象の人が大変そうなコンテストだった……？とか思ったり.

(後ろ2問がきついのに対し, 前4問は全体的にギャグ風味なのが尚更……)

A.EhAb AnD gCd

問題概要

2以上の整数 $x$ に対し, $gcd(a,b)+lcm(a,b)=x$ を満たす正整数 $a,b$ の組を一つ求めよ.

※ $gcd(a,b),lcm(a,b)$ はそれぞれ $(a,b)$ の最大公約数と最小公倍数

解法

$a=1$ とした場合を考えると, $gcd(1,b)+lcm(1,b)=1+b$ となるため, $x=1+b$ より $b=x-1$ とすればよいと分かる.

提出コード

B.CopyCopyCopyCopyCopy

問題概要

$n$ 要素の正整数列 $a$ を $n$ 回繰り返して得られる数列の最長部分増加列(LIS)の長さを求めよ.

解法

$a$ 中に $k$ 種類の正整数が現れるとする. 明らかに, 答えは $k$ より大きくならない. また, $k$ 種類の正整数のうち $i$ 番目に小さい値を $i$ 回目に繰り返された数列 $a$ から得るようにすることで, 長さ $k$ のLISを常に得ることが出来る.

提出コード

C.Ehab and Path-etic MEXs

問題概要

$n$ 頂点の木の辺に, $MEX(u,v)$ ( $1\le u,v\le n$ )の最大値が最小になるよう $0$ 以上 $n-2$ 以下の整数を重複なく番号づける方法を一つ求めよ.

※ $MEX(u,v)$ は頂点 $u,v$ 間の辺の番号として現れない最小の非負整数

解法

$MEX(u,v)$ が最大になりうる $u,v$ の組として, 端点のみを考えればよい.

端点が2つのとき(パスグラフのとき), 辺の番号の付け方によらず $MEX(u,v)$ の最大値は一定.

端点が3つ以上の時, それらに隣接する辺に0,1,2,...と小さいほうから番号付けることで $MEX(u,v)$ の値を2にすることができる.

提出コード

D.Ehab the Xorcist

問題概要

すべての要素の排他的論理和が $u$ で, すべての要素の和が $v$ になるような要素数最小の正整数列を求めよ. (存在しない場合-1と出力)

解法

比較的明らかなケースとして,以下のものがある.

・ $u=v=0$ のとき, 答えは $\{\}$ .

・ $u=v$ で $u \ne 0$ のとき, 答えは $\{u\}$ .

・ $u \gt v$ のとき, 答えは存在しない.

そうでないとき, 同一の整数同士の排他的論理和が0になることを考えると(最小とは限らない)答えとして $\{u,\frac{(v-u)}{2}, \frac{(v-u)}{2}\}$ が思いつくので, これをもとに色々考える. 具体的には, 以下の場合を考える.

・ $v-u$ が2で割れないとき, 和と排他的論理和の偶奇が異なるので答えは存在しない.

・ $u$ と $\frac{(v-u)}{2}$ の排他的論理和がこれらの和に等しい場合, ( $u \ne v$ であることから要素数1の答えは存在しないため)答えは $\{u+\frac{(v-u)}{2},\frac{(v-u)}{2}\}$ .

・以上の条件をいずれも満たさない場合, $\{u,\frac{(v-u)}{2}, \frac{(v-u)}{2}\}$ より少ない要素数の数列を構成できないため, これが答え. ( $u$ と $\frac{(v-u)}{2}$ においてともに立っているbitについて考えると, 2つの数では条件を満たすことが出来ないと分かる.)

提出コード

E.Ehab's REAL Number Theory Problem

問題概要

どの要素もその約数が7個以下であるような正整数列 $a$ の(空でない)部分列であって, その総積が平方数になるようなものの要素数の最小値を求めよ. (存在しない場合-1を出力)

解法

約数が7個以下という条件から, どの要素もその素因数はたかだか2種類である. また, 約数に平方数を含む場合, その平方数で割った値に置き換えても答えは変わらない. この処理を行うことで, どの要素も「1」, 「 $p$ 」, 「 $p \times q$ 」と表せる( $p,q$ は素数で, $p\lt q$ ).

ここで, 1と素数を頂点としたグラフを考え, 各要素に対し以下のルールで辺を張る.

・その要素が「1」と表せるならば1に対応する頂点に自己ループを張る.

・その要素が「 $p$ 」と表せるならば1と $p$ に対応する頂点の間に辺を張る.

・その要素が「 $p \times q$ 」と表せるならば $p$ と $q$ に対応する頂点の間に辺を張る.

すると, このグラフの閉路のうち, 最小のものの長さが答えである. (辺を通ることが2頂点の積として表せる要素を選ぶことと等しく, 閉路ならばどの要素も偶数回ずつ掛け合わせられるため)

最小の閉路を求めるには, 全頂点からbfsをし, (最短路として)使われなかった辺のうち始点と他の頂点を結ぶものがあるならば, その頂点までの距離+1が閉路の長さとして得られる. しかし, $a$ の要素の最大値( $=10^6$ )以下の素数は78948個あり, 最悪ケースにおいて間に合わない. そこで, 辺のうち少なくとも一方は $\sqrt {10^6}=10^3$ 以下であることを考え, 始点を $10^3$ 以下の素数(168個存在する)および1に対応する頂点からのみに限る事で, 十分高速に答えを求めることが出来るようになる.

提出コード

F.Ehab's Last Theorem

問題概要

$n$ 頂点の無向グラフが与えられる. 以下のうち, どちらか一方の問題を解け.

・ $\lceil \sqrt n\rceil$ 要素の独立集合(どの2頂点も辺で隣接していないような頂点の集合)を求めよ.

・長さ $\lceil \sqrt n\rceil$ 以上の単純閉路(同じ頂点を二回以上通らない閉路)を求めよ.

解法

適当な頂点を根としたdfs木を作る.

もし現在見ている頂点からその先祖へと辺が伸びているなら, 深さを比較し, その差が $\lceil \sqrt n\rceil -1$ 以上ならば, これは長さ $\lceil \sqrt n\rceil$ 以上の単純閉路なのでこれを出力する. 以下, これが見つけられなかった場合(すなわち, 独立集合を見つけなければならない場合)を考える.

現在見ている頂点に隣接する頂点すべてについて処理を終えたあと, 以下の処理を行う.

・もしその頂点を独立集合として選べるならば, その頂点自身を独立集合として選ばれる頂点の集合とし, 自身に隣接する頂点を独立集合として選べない頂点として記録する.

この処理を行う時点で子孫について独立集合に加える処理は終わっているため, 頂点を選んだ場合の先祖への影響を考える.

ここで, 深さの差が $\lceil \sqrt n\rceil-1$ 以上であるような先祖が存在しないことから, その頂点を選ぶことで選べなくなる先祖は高々 $\lceil \sqrt n\rceil-2$ 個といえる(鳩ノ巣原理).

故に, ある頂点を選ぶことで, 独立集合の要素数が1増える代わりに最大で(その頂点自身を含め) $\lceil \sqrt n\rceil-1$ 個の頂点が選べなくなるといえるが, この考えのもと, $\lceil \sqrt n\rceil$ 要素以上の独立集合が得られることが示せるため, 元の問題を常に解くことができる.

証明の流れ:

$\lceil \frac{n}{\lceil \sqrt n\rceil-1} \rceil \ge \lceil\sqrt n \rceil$ ならば, $\lceil \sqrt n\rceil$ 要素以上の独立集合が得られると言える.