n-knuu's logs

憧れ駆動。だいたい競プロ

SnackDown Online Pre-elimination round A

数学 ダブリング codechef

SnackDown Online Pre-elimination round Aにe-monさんと出た。
1000位以上が次のOnline Elimination roundに進めて、204位だったので進めた。

Art(MAKEART)

e-monさんが読んで解いたので知らない

N different palindromes(NDIFFPAL)

僕が読んで書いた

  • 問題

文字列Sの部分列S[i..j]が回文となる組(i, j)の個数がN(10^4以下)となるようなSを答えよ
テストケースT個(10^2以下)

  • 解法

"abc...xyzabc..."と順番にアルファベットをN個出力すれば、(1, 1), (2, 2), ..., (N, N)のみが回文となる。
O(TN)

  • コード


Sharing Candies(GIVCANDY)

e-monさんが読んで、僕とe-monさんで解法を考えて、e-monさんが書いた

  • 問題

AlvinはA個の、BertoはB個のキャンディを持っている。AlvinにC個ずつのキャンディの袋を、BertoにD個ずつキャンディの袋を、それぞれにいくつか与えることで、AlvinとBertoの持っているキャンディの個数の差の絶対値を最小にしたい。そのときの最小値を求めよ。

  • 解法

Alvinにx袋、Bertoにy袋与えたとする。このとき、答えがK(>=0)の場合、|(A+Cx)-(B+Dy)| = K、つまりCx-Dy=K+B-AもしくはDy-Cx=K+A-Bとなる。
gcd(C, D)=1のとき、方程式Cx-Dy=1は必ず解を持つので、K=0とできる。
つまり、Cx-Dy=B-Aは、A<=Bのとき必ずx,yが0以上となる解を作れる。A>Bのときは、Dy-Cx=A-Bを考えれば同様に可能。
gcd(C, D) = g(>1)のとき、Cx-Dy=K+B-Aが解を持つには、(K+B-A) % g = 0にならなければいけない。よって、K=min((B-A+g)%g, (A-B+g)%g)が答えになる。

  • コード


Longest Increasing Subsequences(MAKELIS)

僕が読んで、e-monさんが考えて解いた

  • 問題

LISの総数がKになるような、長さNの順列(但しNは100以下)を求めよ。

  • 解法

素因数分解してうまく埋めるとできるらしい(また後で書く)

Chef and his study plans(SUBSEG2)

僕が読んで解いた

  • 問題

開区間[start_i, end_i]がN個(10^5以下)が与えられる。
このとき、以下のクエリがQ個(10^5以下)が与えられるので、それに答えよ
クエリ: 開区間[plan_start_j, plan_end_j]が与えられるので、その区間で区間スケジューリング問題を解け
1 <= start_i <= end_i <= 10^6
1 <= plan_start_i <= plan_end_i <= 10^6
Time Limit: 0.75s

  • 解法

区間スケジューリング問題なので、ある値tが与えられたときに、次にどの区間を取ればいいかが一意に決まる。
よって、1<= t <= 10^6について、時刻tで次の区間をとったときの終わりを記録しておけばよい。
これは、時刻tでとる次の区間は、時刻t-1で取る区間よりも前にならないことを利用して、尺取り法っぽくやれば線形でできる。

ただ、クエリが与えられるたびに、そのまま次のものを辿って数えていくと最悪O(QN)になる。
そこで、時刻tから2^k個、区間をとったときの終わりの時刻を求めておいて、クエリのたびに二分探索すればlogオーダーに落ちて間に合う。
この操作は蟻本のLCA*1のところに書いてある操作(ダブリング)を真似すればよい。

  • 計算量

最大の時間をTとすると、O(T + T log T + Q log T)
(座圧すると、O(T)=O(N+Q)になるのでもう少し速くなりそう？)

  • コード


感想

チーム戦楽しい
e-monさん、用事があるっぽかったのに3問も任せてしまって申し訳ない感じだった

*1:第二版 p.293