ARMERIA

放置していたけど更新再開、Rubyと競技プログラミングの話が中心になっていく予定です

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

Problem - A - Codeforces

問題概要

正整数  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コード

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個あれば絶対に過半数を占めることはありません。

このことから、過半数の条件を真面目に考えなければいけないのは長さ59以下の区間だけで、それ以上の区間は累積和を使えばよいことが分かります。これなら高速です。

解法をまとめると、

  1. 各要素のビット数を数える。
  2. ビット数の累積和と、累積和の偶奇ごとの個数を数える。
  3. 左端を固定する。左端から長さ59以下の区間は、区間和と区間内の最大値を計算して真面目に条件判定する。
  4. それ以降は累積和の差分を取って高速に計算する。

これで解けます。

※公式解説とほぼ同じですが、公式解説では累積和の条件だけで全区間を足してしまった後、過半数の条件に違反するものを引き算するという方法になっています。どちらでもよいです。

※実装上は、よほど制限時間が厳しくない限り59というギリギリを攻める必要はなくて、「60くらい」と考えて長さ65くらいまで真面目に条件判定する実装をしてもよいですし、そちらのほうが安全です。

ACコード

さいごに

どちらも、無駄に難しい解法に走って失敗してしまった回でした。そしてDiv1の人々はやっぱり強いです…Bを300人以上が通しているとは。厳しい戦場です。