Codeforces #132 (Div. 2) E - Periodical Numbers

Dynamic Scoring 是 3000 的題目 (所以也不是每個高手在現場解決了)
Virtual Participation 時花了 40 分鐘沒能搞定的題
不過當時有正確的大方向 (枚舉)

題意：

將一個正整數 X 表示為 n-bit 的 binary-string, S
不可以有前置零 (leading zeros)
若果存在 長度為 k < n 的 循環節 (period)
(i.e., 使得 S[i+k] = S[i]   for 0 <= i < n-k)
則稱 X 為 periodical

給定區間 [L, R], 問當中有多少個 periodical 的正整數

(題目連結)

思路：

先把問題簡化為
求 [1, R] 當中 periodical 正整數的個數

(那麼最後答案 := DOIT(R) - DOIT(L-1))

對於 循環節 長度為 k 的 X，可以將 X 表示成：

• X = Y × (00...01 00...01 00...01 ... 00...01)   (二進制表示及計算，下同)
• (00...01 00...01 00...01 ... 00...01) 是 m-bit 二進位數，其中 m <= n
• 每一個 00...01 是 k-bit 二進位數

Codeforces #57

2010-02-26 Wed
HKG Time - 0000 to 0200

終於... 在一次 individual contest 做到少人完成的難題目了...!

• 題目
• 排名 (12th)
• 官方 Analysis

---

題解概要：

SRM 491 ※ Codeforces 47

[這篇 Entry 怨言居多... 慎入]

前排 ACM ICPC Regional 忙了一排... 現在還是很忙...-_-
── 最近我才意識到... 我只剩下不到兩個半月時間完成下一份 Research Project
但有 online contest 的話，我還是會盡力抽空去打
(縱使狀態不好, 仍盡量堅持打... 要習慣在狀態不好時 code...)

近來的 Online contest 都很不順利...

---

先是星期六晚 (1am) 的 SRM 491...
這場賽事題目很有意思... 我意思是題目對我來說很難...
雖然很多人提交 600 跟 900，但 sample 比較弱...
最後不少人被 Cha 或 Fail System Test
System Test 時有 "Problem"，本來說約有 10% 的 submission judge 錯了
後來等了兩三小時還未完成...

至Test 終於完成時
才聞說 Challenge Phase 臨近最後幾分鐘 Server 有事故
以致某些人的 Challenge 有問題...
至今(都兩三天了) Admin 還未做更新 Rating 與否的決定
(看來 Un-rated 的機會較大...)

>The match will be rated.
GOOD!!

Codeforces #33 (Codeforces format)

2010-10-07 Thurs
HKG Time - 2300 to 2500

有時間既話, contest 會盡量打

今次又係 Codeforces Format
貌似呢 set 題目比較淺
不過我只能夠好慢咁 submit 左四條
(呢一刻狀態比較差, 好支力)

↑ Submitted...

Codeforces #26 (Codeforces format)

2010-08-16 Mon
HKG Time - 2300 to 2500

• 題目在這
• Standings（大scoreboard）
• Room 10 Scoreboard（My room） 

---

Codeforces format：

留意標題後的括號 - Codeforces format

比賽模式跟 SRM 很相似：

• 難道不同的題目分數不同：
  (A,B,C,D,E) = (500, 1000, 1500, 2000, 2500)
• Submit 時間愈早分數愈高
• 比賽完結時才進行 System Test

不過亦有不同的地方：

Codeforces #24

題目在這

---

剛 Accept 了 C... 比賽只剩下 10 分鐘...
橫豎已不能改變結果，便提早寫 blog 記錄

看自己的 scoreboard 和 submission...

比賽時... 完全地進入了暴走狀態 ── 「亂隊」

──沒有寧靜的打code環境是主因之一.....................

呀... 最後的 10 分鐘被不少人過頭

---

今次的題目比較容易...
題A 和 題B 不論如何，應該要 40 minute 內搞定
可是我卻用了 60 minute... 而且還 WA 了 9 次

題C ... 起手 code 需要一點勇氣...
猜想 M_i 形成的 cycle length 很短

rating 或升或跌多少不太重要...
又是表現很差的一場...

Codeforces #23

依然不是解題報告

---

今次的題目很難呢...
rating 下跌了
但無悔參與了... 因為感覺很有得著

這場比賽題目挺奧妙的... 對算法要求比較高...
Codeforces 的性質就是
總有一兩道非常簡單的題目
題A 激簡單
題B 是簡單題... 但是 trap了 1 hr...（然而 solution 極簡單...orz）
題C 的算法很精妙（現場只有40 人AC）
題D, E... 分別是 2D幾何 及 樹狀dp(?)... 較難

---

題A... 在 2 min 提交... 貌似這是第15個submission
不少人在 0~2 min KO... 此題直接略過

---

題B... 挺奧妙的 graph 題目

題意：
有 N (≤ 10⁵) 個人參加了聚會
在 time=0 時，沒朋友的人離開
在 time=1 時，在剩下的人當中，有1個朋友的人離開
在 time=2 時，在剩下的人當中，有2個朋友的人離開
..
如此類推
問，給定 N，在最後最多可以有多少人剩下來？