黃鈺程

@amoshyc

Joined on Dec 26, 2016

  • Graph Dijkstra template <typename T> struct Dijkstra { vector<T> dis; vector<int> par; Dijkstra(int n, T inf) { dis = vector<T>(n, inf); par = vector<int>(n, -1); }
     Like  Bookmark
  • 給定 $ax \equiv b \pmod m$ 的 $a, b, m$,求解 $x$。 如果 $b$ 不是 $g = gcd(a, m)$ 的倍數,則無解。 我們證他的反向,即有解時,$b$ 一定是 $g$ 的倍數。 有解代表存在 $x_0$ 使得 $a x_0 \equiv b \pmod m$,即存在整數 $y$ 滿足 $a x_0 + my = b$。 因為 $a$ 與 $m$ 都是 $g$ 的倍數,所以 $b$ 一定是 $g$ 的倍數。 如果 $b$ 是 $g = gcd(a, m)$ 的倍數,則解為 $x \equiv \left(\frac{a}{g}\right)^{-1} \frac{b}{g} \pmod{\frac{m}{g}}$
     Like  Bookmark
  • UI Window: Zoom Level Breadcrumbs: Enabled Render line highlight Title bar Font Font Family: Fira Code Font Ligature: true Line Height: 1.35
     Like  Bookmark
  • 心得 比賽中解五題,都一次 AC,開心(直到看到 vtuber 最後五分鐘竟然過 F),積分 +71。 另外雖然我聽不懂日語也看不懂日文,但仍想推廣一下這個 vtuber RinSakamichi。她三年前就出道,二年前開始打 atcoder,從以前只能解出三題到這次解出六題,一直在進步,但 youtube 上一直沒什麼觀眾,訂閱數也才 1.1K。若有人感興趣可以去追蹤一下。也許是出於興趣,她三年都沒什麼起色還一直做下去,讓人覺得了不起。 A, B (〃∀〃) C. Doukasen 比賽時沒想到總花費時間除 2 就是相遇的時間,二分搜直接開幹。
     Like  Bookmark
  • Who am I? 一個斷斷續續在玩競程的人,這麼多年過去了依然很菜。最近從 codeforces 轉移至 atcoder,畢竟 atcoder 的比賽時間對台灣友善許多。 喜歡使用 python,但 submit 基本上都用 pypy 而非 cpython,因為在一般運算中 pypy 還是比 cpython 快多了。有時為了使用 AtCoder Library 或確保不 TLE 會改用 c++。 AtCoder (id: amoshuangyc) AtCoder Beginner Contest 223 AtCoder Beginner Contest 222 AtCoder Beginner Contest 184
     Like 1 Bookmark
  • 心得 後半 13 題,比前半 13 題難上不少,讓我慢慢寫。 N. Slimes 給定長度為 $N$ 的序列 $A$,不斷重覆:「合併 $A$ 中的相鄰兩項 $x, y$ 為 $x + y$,花費成本 $x + y$」,直到 $A$ 只剩一個元素。請問在所有合併方法中,總成本最小能是多少? 設 $f(i, j)$ 為合併 $A$ 的半開區間 $[i, j)$ 為一個元素所需的最小成本。 如同 CLRS 中矩陣乘法的最小成本,我們採用 Divide & Conquer 的技巧。
     Like  Bookmark
  • 心得 練習 A, B, C ʕ•͡ᴥ•ʔ D. Even Relation 從節點 0 開始 DFS,遇到長度為奇數的邊,就變色;偶數的邊,顏色不變。 N = int(input())
     Like  Bookmark
  • 心得 久違地打了一場…只解出四題,慘。 A, B, C (⋋▂⋌) D. Between Two Arrays 設 $dp[i, j]$ = 合法的 $C_0, C_1, \cdots, C_i$ 數量,且 $C_i = j$。因為 $C_{i - 1}$ 需要少於 $j$ 就可以,可以寫出轉移: $$
     Like  Bookmark
  • 心得 無事就來寫 atcoder。 A, B, C, D (⁎˃ᆺ˂) E. Sum Equals Xor $a + b = a \text{ XOR } b$ 意謂著 $a$ 與 $b$ 不能有共同的都是 $1$ 的 digit。這常常出現,要背起來!不能都是 1,也就是不會有進位。然後這題就可以用 Digit Dp 解了。 $$
     Like  Bookmark
  • 題目連結 心得 第三題卡了我好久好久,最後跑去先解第四題,10 分鐘 AC,才又回來想第三題。高中就知道我排列組合不好,現在還是不會,我真是太失敗了 ੨( ・᷄ ︵・᷅ )シ,我到底該正著算呢?還是反著算呢?這樣算到底會不會重覆算呢?是不是要枚舉 0 的數量,用重複組合?第五題沒解出來,聽說是經典題,讓我好好研究研究。 A, B ʘ‿ʘ C. Ubiquity 一開始的想法是正著算:在 N 個位置中任取兩個位置,放 0 與 9,其他位置數字任填,所以方法數是 ${N \choose 2} \cdot 2! \cdot 10^{N-2}$,然後範測一直過不了,換了各種方式都還是不行。
     Like  Bookmark
  • 最近遇到不少 digit dp 的題目,而網上的題解通常是 top-down + 遞歸的方法,但有一些題目,例如 Valid payments,如果硬要用遞歸來解,我覺得解法很不直覺。因此在這篇文章我希望整理並統一我 digit dp 的寫法:bottom up + 遞推。 Valid payments 題目相當於在問:「所有 $A$ 進制的 $N$ 位數中(允許 leading 0)有幾個數 $r$ 滿足 $r$ 與 $X + r$ 沒有共同不為 $0$ 的 digit」,即 $\forall_{0 \le i \lt N}, r_i = 0 \lor (X + r)_i = 0$。 設 $y = X + r$,$c$ 是 carry,直式加法如下: $$ \begin{array}{r} &c_3 &c_2 &c_1 &0 \
     Like 4 Bookmark
  • 心得 賽後寫的。 A. Hands 第一直覺就 Dijsktra 模板用起來,不過既然是賽後才寫還是慢慢想吧,第一題不太可能是模板題。 可以發現對 b 來說,向下一層樓有兩種路線: 直接往下,成本 y。 透過水平的通道到 A 樓,再走斜著的通道回 B,成本 2x。
     Like  Bookmark
  • 心得 排 1057,積分 +46。 前二題很快的解出,第三題想不出來,先跳去解第四、第五題。第四題輕鬆過了,第五題在兩個測資會 TLE,回去解第三題,終於在測資的幫忙下弄出來了,最後一點時間將第五題的程式優化,在第 99 分鐘 AC,雖然是假解 XD。第六題也是能解的題目,第三、第五題卡太久了。 拼到最後真的累。 ![](https://i.imgur.com/TtUqJdg.png =300x) source: 點兔第三季
     Like  Bookmark
  • 題目連結 心得 practice。 最近似乎遞推的寫法比較主流,所以我也嘗試用遞推來寫,而非我習慣的遞歸。 A. Frog 1 簡單 dp。 N = int(input())
     Like  Bookmark
  • 心得 第四題又卡住,還好最後一分鐘 AC,應該先去解第五題,簡單多了 (︶︹︺) 把上一場加的積分全還回去了 QQ A, B 簽到。 C. To 3 基於 3 倍數的特性,可以得出不可能刪 3 個 digits 或更多。刪 1 個 digit 的情況為有某個 digit 與 「N 對 3 的餘數(r)」相同。刪 2 個的情況是選兩個 digits 出來,他們的和可以組出 r。實作時小心別讓所有的 digits 都被刪掉了。
     Like  Bookmark
  • 心得 解出 5 題,積分 +54。 第四題漏看了一個條件,害我花了好久。 第六題竟然直接裸著來,我以為這方法會 MLE 就沒寫,可惜。 source A. ReLU 38 秒,下次挑戰不先測直接 submit XD。
     Like  Bookmark
  • 題目連結 心得 第二題鬼打牆,最終解出前三題,排 1245,積分 +35 A. Simple Math A, B, C = map(int, input().split()) A = (1 + A) * A // 2 % 998244353 B = (1 + B) * B // 2 % 998244353 C = (1 + C) * C // 2 % 998244353
     Like  Bookmark
  • 題目連結 心得 解五題,排 1387 A, B 略 C. Repsept 序列的數字可能非常大,該怎麼高速地判定某大數是不是 K 的倍數呢?Horner's Rule!這個技巧真常出現。
     Like  Bookmark
  • 題目連結 心得 賽後才來寫的,這場比賽跟 cf 連在一起,所以就沒打這場了。 A, B, C 都是水題。 聽說第二題會卡 double,得用 long double 才會過,用 python 的表示有這回事嗎 ¯(°_o)/¯ D. Takahashi Unevolved
     Like  Bookmark
  • 題目連結 心得 因為沒同學/朋友要一起參戰,比賽時只來看了一圈題目沒 submit。 A, B, C 水題。 D. Hachi 看完題目想說這麼簡單,怎麼 Standings 上一堆人都先 WA 才 AC,看我一次 AC,然後我就 WA 了三次 (┛ಸ_ಸ)┛彡┻━┻
     Like  Bookmark