選訓一天一 OI 計畫 #3 ><
這篇的主要內容雖然是選訓的時候打的，但因為那是公開的所以理論上我不能當下發文，
後來結束之後就一直拖稿到現在，燒雞

[4/13] 更新：從上一場好像就不計算範測了，所以把分數比例更新過了。

賽前

看到 USACO Open Contest 在這幾天辦，所以就決定去打了，
時間是 11:30 ~ 16:30，有跨午餐。

賽中

開場先打了 ~/.vimrc，然後把全部的題目都讀完：

• A Apple Catching
  有 $N$ 個事件，每個事件有兩種可能：
  1. 在時間 $t_i$ 的時候 $x_i$ 出現了 $n_i$ 隻牛
  2. 在時間 $t_i$ 的時候 $x_i$ 出現了 $n_i$ 隻顆蘋果
• 每隻牛能夠以 $1$ 單位的速度移動，但每一隻牛只能抓一顆蘋果，另外要是蘋果出現的時候沒有牛去抓他，那顆蘋果就會消失。
  輸出最多能抓到幾顆蘋果。
  $0 \leq t_i \leq 10^9,\, 0 \leq x_i \leq 10^9,\,0 \leq n_i \leq 10^3$
  [21_/21] 無額外限制

沒什麼想法，但維度太多了感覺不好做，

• B Pair Programming
  定義一個程式的運作是這樣定義的：
  • 一開始 stack 是空的
  • $+$ 會 push 一個 $1$ 進去
  • $d$ 會把整個 stack $\times d$，特別的，如果 $d = 0$ 會清空整個 stack。
• 你有兩個長度是 $N$ 的程式，在所有把他們合併而不改變相對順序的條件下（共有 $\frac{(2N)!}{N!N!}$ 種），有多少種不同的最終結果？ 輸出 $\mod 10^9 + 7$。
  $1 \leq N \leq 2000$
  [1_/15] $N \leq 6$
  [3_/15] $N \leq 100$
  [3_/15] $N \leq 500$
  [8_/15] 無額外限制

光讀懂題目就花很久的時間了，原本的題目沒有這麼好懂，
讀懂之後大概就知道他要 DP 了，但還是想了很久要怎麼列狀態跟轉移，

• C Balancing a Tree
  你有一棵樹，定根在 $1$，第 $i$ 號節點可以在上面放 $[l_i,\,r_i]$ 的整數，
  令 $s_i$ 是第 $i$ 號節點上的數字，找出一種放法使得 $\displaystyle\max_{u,\,v \in \text{subtree of }u}{|s_u - s_v|}$ 最小。
  $2 \leq N \leq 10^5$
  [1_/14] $l_i = r_i$，不須構造 $s_i$
  [1_/14] $l_i = r_i$，須構造 $s_i$
  [1_/14] 樹是一條鍊，不須構造 $s_i$
  [1_/14] 樹是一條鍊，須構造 $s_i$
  [4_/14] 須構造 $s_i$
  [4_/14] 不須構造 $s_i$

稍微想一下就可以發現直接對答案二分搜就好，就一邊想細節一邊去吃飯。

吃完飯就回來實作了，第一次用 vim 打打字有夠慢，還出一堆語法 bug，
傳上去之後

01:35 C 2_/14

$\newline$

只過範測= =
稍微測了一段時間抓到一些問題，修一修再傳上去

01:44 C 10_/14

$\newline$

不用構造的都過了，大概想了一下還是抓不到錯在哪裡，就先去想 AB 了。

A 沒什麼頭緒，把時間對座標的圖畫出來還是觀察不到可以怎麼做，也沒有子題可以寫，
這時候回去看 B 就有點想法了，把 $dp$ 式列成
$dp_{0,\,i,\,j} = $ 用完第一個的前 $i$、第二個的前 $j$，最後是 push 的種類數
$dp_{1,\,i,\,j} = $ 用完第一個的前 $i$、第二個的前 $j$，最後是 $\times d$ 的種類數
小心注意 $0$ 要重置、$1$ 要忽略，就可以用 $O(N)$ 的時間轉移，
但實作超級麻煩= =

從開始打第一行到把範測修好總共就花了快一個半小時，終於能傳上去了之後

03:42 B 8_/15

$\newline$

現在兩題 BC 都要 debug，而且 B de 完還要回去優化前綴和，
又測了一下抓不到問題，就決定先去看看 C 到底構造錯在哪裡。

測一下就抓到構造假解了，我的構造要從樹上往下做而不是只拿根的限制就好，所以寫完之後傳上去

03:51 C 2_/14

$\newline$

不知道改到什麼連不用構造的都錯了= =
結果是自己複製到第一筆 submission，笨死，
再傳上去就拿到了，

03:54 C 14_/14

$\newline$

心態有稍微回來一點點，但還是覺得自己剩一小時才拿一半有夠笨，
接下來就 AB 交替想，在畫 A 的圖之後突然發現牛的涵蓋範圍轉 45 度就是矩形了，這樣一來就可以好好的 greedy，
寫了掃描線之後

04:31 A 21_/21

$\newline$

當下覺得自己最後還能想出來真的有夠賽，這種 45 度我已經遇過好幾次竟然可以看不出來，
最後就回去找 B 的 bug 但找不出來，不壓前綴和的原因是這樣還要再實作很多，而且壓了也不見得會過，所以就放著了。

Result

					Sum
A	21				21/21
B	1	3	3	2/8	8/15
C	1	1	4	4	14/14
Score					844/1000

Rank 67 among all pre-college participants in this division.
有成功升上 Platinum，好耶

檢討

整場最大的問題大概是實作速度跟穩定度，感覺我已經抓到自己這件事不知道幾次了，
在各大 OJ 上題數超少的下場大概就是這樣吧，很多題目都不實作就放著精神導致比賽打得有夠爛，
這年要好好把 Queue 裡的東西都要實作完才算結束，不能單單只是解掉而已，
還有就是 A 那題觀察的東西不難但我觀察的太慢了，
總之我很笨，都不好好練程式被抓到。

心得

這幾天回來看當初選訓的這些事，
當然還是會很氣師大卡常，但基本上我覺得好像也沒那麼難過了，
至少我在這兩個禮拜過的很快樂，可以不用管學校的事情（但我現在要補的東西好多，不想做zzz）
明年就是最後一年了，就這一年，好好補好我之前沒有扎實練好的，
這樣的態度應該會比之前那樣健康很多吧，
好好享受最後能夠在高中打競程的時光。