【TOI2019 三模 pD】自助餐

題目敘述

Output only題。
給定正整數$n$, $k$, $d$, $T$，找出$T$個集合$S_1,S_2,...,S_T$滿足
  1.  $S_i \subset \{0,1,2,...,n-1\}$
  2.  $|S_i | = k$
  3.  $\forall i \neq j,\, | S_i \cap S_j | \le d$

Subtask

  1. $n=5$, $k=3$, $d=2$, $T=10$
  2. $n=8$, $k=5$, $d=3$, $T=8$
  3. $n=20$, $k=12$, $d=7$, $T=16$
  4. $n=64$, $k=32$, $d=16$, $T=125$
  5. $n=65$, $k=32$, $d=17$, $T=125$
  6. $n=49$, $k=7$, $d=3$, $T=2401$
  7. $n=121$, $k=11$, $d=4$, $T=161051$
  8. $n=1369$, $k=37$, $d=2$, $T=50653$
  9. $n=49$, $k=7$, $d=5$, $T=117649$

作法

大致上可以把這些subtask分成三類：
  1.  Subtask 1~3是小測資。
  2.  Subtask 4~5是$n$為二的冪次的測資，我們可以注意到把Subtask 4的全部集合補上一個65就是Subtask 5的答案了。
  3. Subtask 6~9都滿足特定的規律：$n=k^2$, $T=k^{d+1}$
接著一個一個說明每一類的作法：

Subtask 1~3

$n=5$直接枚舉所有5取3就可以了，$n=8$也可以自己手構一下

而$n=20$就得跑程式爆搜了，一個作法是從$S_1$慢慢選擇到$S_T$，要選擇$S_t$時，random產生1000個候選集合$s_1,s_2,...,s_{1000}$，把那些不符合條件（aka $\exists j<t,\, |S_j \cap s | > d$）的篩掉，然後找
$$\sum _{i=0}^{t-1} |S_i \cap s |$$
最大的$s$，然後讓$S_t=s$。
這個作法跑十秒鐘大概10輪內就有結果了(?)，運氣好當然會更快XD

Subtask 4~5

如同上面所說的我們其實只要處理Subtask 4。因為$k=\frac{n}{2}$所以這個集合含有一半的數字。另外注意到$d=\frac{n}{4}$，所以如果隨機選擇兩個合法的集合$A,B$，則滿足$i \in A$且$i \in B$的$i$期望上有$ 64 \times \frac{1}{2} \times \frac{1}{2} = 16$個，剛好和$d$一樣。但我們不可能真的隨機取125個集合，所以這時就可以發揮一些derandomization的精神了。

第一個簡單的想法是我們把滿足第$i$個bit是1的所有數字搜集起來變成$S_i$，例如$S_1$會搜集所有奇數，$S_6$會搜集所有不小於32的數字，那明顯$|S_i \cap S_j|=d$。然而這樣只有6個集合，離125有好大一段距離。

接下來會發現如果$S$是一個答案的集合，那把$\tilde{S}=\{0,1,2,...,n-1\} \setminus S$塞到答案好像也不會出事，因為
$$|\tilde{S_i} \cap \tilde{S_j}| = n- |S_i| - |S_j| + |S_i \cup S_j|=\frac{n}{4}$$
$$|\tilde{S_i} \cap S_j| = |S_j| - |S_j \cap S_i| = \frac{n}{4}$$
這樣我們就有12個滿足條件的集合了。還是離答案有點距離。

最後稍微來改進第一步的想法，因為某種程度上我們要“隨機”的產生集合，我們只要讓任意兩個集合是獨立的就好了，所以如果我們製造一個集合
$$S'=\{x \mid x\text{的第一個bit}+ x\text{的第二個bit}=1\}$$
可以知道$S'$, $S_1$, $S_2$是不獨立的，因為把集合轉換成bitset後會有
$$S'=S_1 \oplus S_2$$
其中$\oplus$表示exlusive or。但如果我們只看$S'$, $S_1$時這兩個集合是完全獨立的，稍微證明一下就會發現這兩個集合交集的大小的確是16。

定義$f(x)$為$x$的bit數量除以二的餘數（也就是(__builtin_popcount(x)%2)）。依照這個思路我們可以構造出集合$S_1, S_2,...,S_{63}$滿足
$$S_i=\{x\mid f(x \oplus i)=1\}$$
再補上所有$\tilde{S_i}$
$$\tilde{S_i}=\{0,1,2,...,n-1\}\setminus S_i = \{x\mid f(x \oplus i)=0\}$$
這樣我們就有126個集合了，隨便刪掉其中一個就成功構造出來啦！

Subtask 6~9

我們已經知道這些測資有規律：$n=k^2$, $T=k^{d+1}$，實際上我們還可以發現$k$是質數，有了這些我們就可以開始我們的構造。

首先$d=0 $的構造非常簡單，所以我們可以觀察看看$d=1$的情況。首先因為$T=k^2=n$，我們可以用一個$n \times n$的表格來表示我們的構造（如同上面$n=8$的示意圖），其中第$i$列第$j$行為黑色代表$j-1$有出現在$S_i$中。接著嘗試構造$k=3$的情形：
很自然的，我們會希望每一列都滿足第$1$~$k$格中恰有一個黑格，第$k+1$~$2k$格中恰有一個黑格....第$(k-1)k+1$~$k^2$格中恰有一個黑格，所以每一個集合$S_i$可以用$k$個介於$0$~$k-1$正整數$(a_0,a_1,...,a_{k-1})$表示：
$$S_i=\{ 0 \cdot k + a_0, 1 \cdot k + a_1,..., (k-1) \cdot k + a_{k-1}\}$$
令有序 k-tuple $A_i$ 為$S_i$的表示法，我們希望對於所有$i \neq j$ ，$A_i$, $A_j$一樣的元素只有一個，或者說$A_i$, $A_j$的hamming distance至少為$k-1$。
我們可以注意到$k=3$的構造中$A_i$的前兩項跑遍所有$0\le x < 3$,$0\le y < 3$的$(x,y)$（可以觀察上面的圖，上面的構造甚至滿足$3x+y+1$為列的編號），觀察最後三排我們可以得到所有$A_i$的規律
$$A_i=(x,y,(x+y)\%3)$$
當$x$和$y$各自跑遍$0$~$2$時，我們就完成了這個表格。

為什麼這個構造是對的呢？假設有不一樣的$(x_1,y_1)$,$(x_2,y_2)$滿足$(x_1,y_1,(x_1+y_1)\%3)$和$(x_2,y_2,(x_2+y_2)\%3)$中有兩項一樣，如果他們後兩項一樣那我們就有
$$y_1=y_2$$
$$(x_1+y_1)\%3=(x_2+y_2)\%3$$
進而推出$(x_1,y_1)=(x_2,y_2)$，所以他們根本是同一行，矛盾。其他狀況也會得到一樣的結論。

接下來的$A_i$內部的所有運算都在模k下進行（注意到以下的運算中$k$是質數）
我們可以把這個作法推廣到一般的$k$，我們讓$A_i$為形式
$$(x,x+y,x+2y,...,x+(k-1)y)$$
一樣讓$x$,$y$跑遍所有$0$~$k-1$，如果存在不一樣的$(x_1,y_1)$,$(x_2,y_2)$滿足$(x_1,x_1+y_1,...,x_1+(k-1)y_1)$和$(x_2,x_2+y_2,...,x_2+(k-1)y_2)$中第$i+1$項和第$j+1$項一樣，我們會有
$$x_1+iy_1 \equiv x_2+iy_2 \pmod{k}$$
$$x_1+jy_1 \equiv x_2+jy_2 \pmod{k}$$
相減後得到
$$(j-i)y_1\equiv (j-i)y_2 \pmod{k}$$
$$y_1\equiv y_2 \pmod{k}$$
代回得到
$$x_1\equiv x_2 \pmod{k}$$
所以$(x_1,y_1)=(x_2,y_2)$，矛盾。

上面的精髓在於我們找了$k$個線性獨立的式子$x$, $x+y$,...,$x+(k-1)y$，因為只有兩個變數，所以只要其中兩項一樣就代表是同個$(x,y)$生成的。現在我們希望只要有$d+1$項一樣就是同個集合，我們就需要$d+1 $個變數$x_1,x_2,...,x_{d+1}$，然後讓這$d+1$個介於$0$~$k-1$的變數跑遍所有$k^{d+1}$種可能。實際上，我並沒有以下構造的線性獨立證明，但總之在題目的狀況下都過了：我們考慮以下線性式（$1\le i \le k$）
$$f_i(x_1,x_2,...,x_{d+1})=i^0 \cdot x_1 + i^1 \cdot x_2 + ... + i^{d} \cdot x_{d+1}$$
然後考慮所有
$$(f_1(x_1,x_2,...,x_{d+1}),f_2(x_1,x_2,...,x_{d+1}),...,f_k(x_1,x_2,...,x_{d+1}))$$
讓$x_1$, $x_2$,..., $x_{d+1}$跑遍$0$到$k-1$，這就完成我們的構造。

 最後就是上code啦！

後記

賽中完全沒看出Subtask 6~9的規律，所以拿到Subtask 1,2,4,5就收工了。Subtask 3賽中沒想到好random法，只弄出大小14的構造，上面的做法是bb給出來的，Subtask 6~9則是賽後聽到規律後花了幾個小時搞出來的。最後感謝oToToT告訴我raw string的用法，所以可以看出我的程式碼中Subtask 3（aka 賽後補的程式碼）是用raw string處理的，還要感謝Adrien Wu寫出快速的checker code。所以說....

Bonus

如何寫出這題的checker呢？
目前Adrien Wu的checker只需要6秒喔！

留言

張貼留言

這個網誌中的熱門文章

【TOI2019 二模 pA】吠市數列

題目敘述 給定一質數$p$和$a_0$, $a_1$，定義數列$\{a\}$滿足遞迴式 $$a_n=a_{n-1}+a_{n-2}+1,\, \forall n \ge 2$$ 現在我們知道$x$, $a_x$, $y$, $a_y$, $k$，求$a_k$。若無解輸出$-1$，若有超過一解輸出$-2$ $x$, $y$, $k$都在long long範圍內，$p$在int範圍內 作法 首先根據簡單的運算我們有 $$a_n=F_{n-2}a_0+F_{n-1}a_1+F_{n}-1$$ 其中$\{F\}$為費波那契數列（$F_0=F_1=1$），且$F_{-1}=0$, $F_{-2}=1$ 令$a=F_{x-2}\%p$, $b=F_{x-1}\%p$, $c=F_{y-2}\%p$, $d=F_{y-1}\%p$, $e=F_{k-2}\%p$, $f=F_{k-1}\%p$ （用矩陣快速冪等方法求得） 我們有 $$ag_0+bg_1 \equiv a_x -(F_{x}-1) \pmod p$$ $$cg_0+dg_1 \equiv a_y -(F_{y}-1) \pmod p$$ 然後想要知道 $$eg_0+fg_1$$ 是多少 二元一次聯立方程式式國中課程內容，但如果套用到模運算下會很麻煩，尤其我們並不是真的要求$g_0$, $g_1$，而只要$eg_0+fg_1$。以下提供一個暴力分case的方法，雖然應該存在簡短的方式，但這種直覺的作法應該不容易漏case。 首先有個簡單的Lemma説對於所有質數$p$，不存在$i$使得$F_i$, $F_{i+1}$都是$p$的倍數，證明會在後面補。所以不會發生$a=0$且$b=0$，也不會發生$c=0$且$d=0$的情況。接下來就是分類了： $\mathbf{a=0}$       首先我們可以用$bg_1 \equiv a_x -(F_{x}-1)$求出$g_1$，然後代入第二條式子得到 $$cg_0 \equiv a_y -(F_{y}-1)-dg_1 \pmod p$$ 若$c=0$ $a_y -(F_{y}-1)-dg_1 \equiv 0$，則無限多組解 否則無解 若$c\neq 0$，直接計算出$g_0$
閱讀完整內容

【TOI2019 三模 pA】圓的最佳覆蓋

圖片
題目敘述 平面上有$n$個點，請問一個半徑為$r$的圓內部最多可以有幾個點？（圓周視為內部） $n\le 1000$, 值域和$r$都在$10^4$內 作法 一個很直覺的想法是如果有一個最佳狀況的圓，我們總是能稍微調整讓這個圓貼住其中至少兩個點，也就是說圓周上至少會有兩個點。這樣枚舉所有$\binom{n}{2}$個點對，畫一個半徑$r$且經過這兩點的圓，然後檢查每個點是不是在這個圓的內部，複雜度為$O(n^3)$，賽中只能拿到60分。 只要枚舉點對複雜度就已經$O(n^2)$了，後面檢查應該沒什麼機會更快，這代表枚舉點對行不通。所以我們試試看只枚舉一個點，然後看所有經過這個點的圓內部有幾個點。 假設現在固定圓要經過一個點$A$，那這個圓的圓心$O$必須在$A$為圓心，$r$為半徑的圓上。 一個重要的觀察是：對於其他的點$P$，當圓心在某個夾角內的時候，這個點才會在圓的內部裡面，如下圖所示。 有了這個觀察，題目就變成環狀區間加值，最後問最大值的問題，簡單做個差分就解決了。 那要怎麼計算一個點貢獻什麼區間呢？這可以用簡單的三角函數計算，如圖 如果$P$剛好在圓$O$上時，$OP=OA=r$，所以$\alpha=cos^{-1}(\frac{d}{2r})$，所以假設向量$AP$的幅角是$\theta$，那區間就是$[\theta-\alpha,\theta+\alpha]$。 實作上，因為是環狀的，所以先計算圓心角度為$0$的答案，然後繞一圈去更新答案即可。複雜度為$O(n^2logn)$（枚舉固定點$O(n)$，排序和差分$O(nlogn)$）。 附上程式碼
閱讀完整內容