SnackDown Online Pre-elimination round A
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