Codeforces Round #512 参加記録＆解説（Div1 A, B）

Dashboard - Codeforces Round #512 (Div. 1, based on Technocup 2019 Elimination Round 1) - Codeforces

結果は355位で、レートが結構下がってしまいました…

f:id:betrue12:20180924113227p:plain

Div1のAとBを振り返ります。Div2ではDとEに対応しています。

A. Vasya and Triangle

問題概要

正整数 $n, m, k$ が与えられる。 $xy$ 平面上の $0 \le x \le n$ かつ $0 \le y \le m$ の領域内に格子点3つを取り、それらを結んだ三角形の面積が $\frac{nm}{k}$ となるようにせよ。またはそれが不可能であることを判定せよ。

制約

$1 \le n, m \le 10^{9}$
$2 \le k \le 10^{9}$

本番はかなり面倒な構成方法をした挙げ句にシステスで落ちましたが…簡単な構成方法があります。

格子点のみを頂点とする多角形の面積に関して、「ピックの定理」というものがあります。この定理から、このような多角形の面積は必ず $\frac{1}{2}$ の整数倍になります。

$\frac{nm}{k}$ が $\frac{1}{2}$ の整数倍でなければならないので、 $2nm$ が $k$ で割り切れない場合、答えは NO となります。以降、割り切れる場合を考えます。

仮に $(0, 0), (n, 0), (0, m)$ の3点をとった場合、その面積は $\frac{nm}{2}$ です。作りたい面積はその $\frac{2}{k}$ 倍です。先程「 $2nm$ が $k$ で割り切れる」という条件を調べたので、 $k$ の素因数は2を除いて $n, m$ どちらかの素因数になっています。このことから、以下のように考えることができます。

$k$ が2で割り切れる場合、まず $k$ を2で割って $k^{\prime} = \frac{k}{2}$ とする。その後 $k^{\prime}$ の素因数を、 $n$ または $m$ の割れる方から割っていく。
$k$ が2で割り切れない場合、先に $k^{\prime}$ の素因数を、 $n$ または $m$ の割れる方から割っていく。その後 $n, m$ のうち、素因数で1回以上割ったほうをどちらか選んで2倍する。（素因数で1回以上割ると値が $\frac{1}{2}$ 倍以下になるので、2倍することで $n, m$ が元の値よりも大きくなることはない）

このようにして小さくした $n, m$ で3点 $(0, 0), (n, 0), (0, m)$ を取り三角形を構成すると、作りたい面積が実現できます。

ACコード

（C++）Submission #43341268 - Codeforces

B. Vasya and Good Sequences

Problem - B - Codeforces

問題概要

長さ $n$ の数列 $a_{1}, ..., a_{n}$ が与えられる。この数列の連続部分列のうち、以下を満たすものの個数を求めよ。

「要素を1つ選び、その2進数表記におけるビット2箇所を選んで入れ替える」という操作を好きなだけ行うことで、数列全体のXORを0にできる。

制約

$1 \le n \le 3\times 10^{5}$
$1 \le a_{i} \le 10^{18}$

解法

これも本番はかなり面倒なしゃくとりを書いていて、何とか通ったからまだいいのですが、シンプルな解法で解説してみます。

「「要素を1つ選び、その2進数表記におけるビット2箇所を選んで入れ替える」という操作を好きなだけ行うことで、数列全体のXORを0にできる」まずはこの条件を言い換えてみます。1要素内で好きなだけビットを入れ換えられるので、ビットの位置は気にしなくて良いでしょう。区間内の各要素のビットの個数を考えたときに、以下の2つが満たされていればよいです。

ビットの個数の総和が偶数である。
1つの要素が、ビット総数の過半数を持っていない。

f:id:betrue12:20180924125238p:plain

「ビット総数が偶数となる区間」だけであれば累積和で簡単に求められますが、2番目の条件が厄介です。

ここで、1つの要素が持つビット数の範囲を考えます。 $1 \le a_{i} \le 10^{18}$ という制約から、まず下限は1個です。そして2進数で1を60個並べた数がおよそ $1.15 \times 10^{18}$ で制約を超えてしまうことから、上限は59個です。上限もさることながら下限が1というのも効いていて、例えばビット数59個の要素があっても、それ以外に要素が59個あれば絶対に過半数を占めることはありません。