Codeforces Round #502 参加記録

Dashboard - Codeforces Round #502 (in memory of Leopoldo Taravilse, Div. 1 + Div. 2) - Codeforces

途中でサーバが落ちて、unratedになってしまいましたが…結果は3完。predictorの数値だとレートはけっこう上がってたみたいなのでちょっと残念です。

f:id:betrue12:20180811120804p:plain

A～Dの4問を振り返っていきます。

A. The Rank

Problem - A - Codeforces

問題の通り「合計点数が大きい順→同点ならidが小さい順」にソートして、id=1が何番目に出てくるか調べればOKです。

Submission #41340341 - Codeforces

B. The Bits

Problem - B - Codeforces

ビット列: $a, b$ が与えられます。 $a$ のビット2つの入れ替え方のうち、入れ替えることで $a | b$ の値が変化するものの数を求めます。

まず、0と0、1と1の入れ替えはもちろん意味がありません。0と1を入れ替えた時にorの値が変化するかどうかは、入れ替えた場所の $b$ のビットに応じて変わります。入れ替えた場所の $b$ の2ビットをそれぞれ $b_{1}, b_{2}$ として表を書きます。

$b_{1}$	$b_{2}$	$10 \vert b_{1}b_{2}$	$01 \vert b_{1}b_{2}$
0	0	10	01
0	1	11	01
1	0	10	11
1	1	11	11

$a$ において1と0を入れ替えた時には、 $b_{1}, b_{2}$ が両方1の時でない限り、orの値が変化します。

そのため、 $a$ の1と0のペア数から、その中で対応する $b$ のビットがともに1であるものを引けばよいです。

Submission #41344556 - Codeforces

C. The Phone Number

Problem - C - Codeforces

$1, ..., n$ の順列のうち、その最長増加部分列（LIS）と最長減少部分列（LDS）の長さの和が最小になるものを1つ作れ、という問題。

この問題ですが、以下のように作るのが最適です。

f:id:betrue12:20180811150554p:plain

$\sqrt{n}$ で数列を分割し、LISとLDSの長さがともに $\sqrt{n}$ になるように構成します。

$\sqrt{n}$ が整数にならない場合でも一番上や一番下で調整することで、LISとLDSの長さの積が $n$ 以上であればこのような構成をすることができます。そのため、 $\sqrt{n}$ が整数でないときは以下のようにします。

$r = \lfloor \sqrt{n} \rfloor$ とする。このとき、 $\sqrt{n}$ が整数でなければ $r^{2}+1 \le n \le (r+1)^{2} - 1$ である。
$n \le r(r+1)$ の時、LDSの長さを $r$ 、LISの長さを $r+1$ とする。
の時、以下のどちらかとする。ともに長さの和はである。
- LDSの長さを $r+1$ 、LISの長さを $r+1$ とする。
- LDSの長さを $r$ 、LISの長さを $r+2$ とする。（ $(r+1)^{2} - 1 = r^{2} + 2r$ であるため収まる）

さて、これが最適であることの証明ですが…AtCoderの問題に似たようなものがあり、その解説に書いてある方法が結構分かりやすかったので紹介します。

E - LISDL

f:id:betrue12:20180811150356p:plain

ある順列を考えます（適当に作りました）。各点に対して、「その点が終点であるような最長増加部分列の長さ」を付けていきます。これらの値は、もちろん数列全体のLISの長さ以下になっているはずです。

ここで、例えば2が付けられた点は、「それ以前の点で、2が付けられたもの」より小さいということが言えます。もし後の点のほうが大きい場合は、前の点を終点とする長さ2の増加部分列に後の点をくっつけると長さ3の部分列ができるので、後の点には3以上の数字が付いているはずです。

ということは、「番号2を持つ点」だけを集めると減少列になります。もちろんこれは全ての番号について言えるので、「同じ番号を持つ点の数」の長さの減少列が作れることになります。

整理すると、

数列全体のLISの長さを $A$ とする。それぞれの点に「その点が終点であるような最長増加部分列の長さ」の番号を付けていく。
点が $n$ 個で番号が $A$ 種類なので、「同じ番号を持つ点の集合」としてサイズが $\lceil\frac{n}{A}\rceil$ 以上のものが必ず存在する。
この「同じ番号を持つ点の集合」は減少列を成すので、数列全体のLDSの長さ（ $B$ とする）は必ず $\lceil\frac{n}{A}\rceil$ 以上になる。

さらにLISとLDSの長さの積を考えると、 $AB \ge A\lceil\frac{n}{A}\rceil \ge n$ となります。これは、任意の順列に対して必ず成立する条件です。

この条件下で $A+B$ を最小にしようとすると、まさに前半で示したような $A$ と $B$ の選び方となります。*1

Submission #41348326 - Codeforces

D. The Wu

Problem - D - Codeforces

公式解説だと半分全列挙が絡んだ解法だったのですが…もう少し単純な方法でも通すことができたので、そちらで書きます。

$n$ 桁のビット列2つに対して計算される値で、「上から $i$ ビット目が一致していれば $w_{i}$ 加算」という値を全ビットについて合計したものをWu値と呼ぶことにします。先にビット列集合 $s_{1}, ..., s_{m}$ が与えられ、その後にクエリで1つずつ文字列 $t$ とボーダー値 $k$ が与えられるので、 $s_{1}, ..., s_{m}$ のうち $t$ とのWu値が $k$ 以下であるものの個数を答えなさい、という問題。

まず、ビット列の長さが最大でも12しかありません。先に与えられるビット列の数もクエリの数も多いですが、ビット列は全部で4096通りしかないので、それを超えたぶんは必ず重複しています。これらをまとめて考えられそうです。

また、ビット列2つのペアのWu値がいくつになるかは最大 $4096^{2}$ 回（入れ替えを除けばもっと少なく）計算すれば求められます。やってやれないことはない回数です。

また、Wu値の値もあまり大きくなく、制約から最大でも1200です。

以上の情報から、クエリを処理するために以下のような前計算が現実的な時間で可能です。

ビット列集合から、 $2^{N}$ 通りのビット列がそれぞれいくつあるかの分布を計算する。
考えられる入力（ $2^{N}$ 通り）と、ビット列集合に含まれる列（ $2^{N}$ 通り）の全ペアについて、Wu値を計算する。これとさきほどのビット列集合の分布から、「クエリでこの入力が来た際に、Wu値がこの値となるビット列の個数」が全部計算できる。
これをWu値が少ない方から累積和を取ると、「～～Wu値がこれ以下のビット列の個数」となる。