2015年2月11日 星期三

Codeforces Round #289 (Div. 2, ACM ICPC Rules)

又是一場百感交集的Round...
相對的學習到的東西好像比較少, 也就是為做而做了...(證明我在公司的確很閑)

難得的是跟ACM ICPC的rules, 就是即場判定, 無hacking, 之類吧
共有6條題目, 當然我也只是做了最多人AC的4題了...(還有一題是水過的=.=)

Codeforces Round #289 (Div. 2, ACM ICPC Rules)


A: (頹題, DP/Math)

題意: Given 2D matrix, 某一格的value = 上一格+左一格,  求某一格的value

很直接的所謂DP題目, 其實就是學DP時一定會教的基本例子而已....
有見及此, 我很無聊的不打表, 而跑去試著找個有創意的Solution
....
就是上OEIS找找看有沒有這樣的Sequence, 肯定是有的吧...
原來就是 (2n C n)....
所以我就這樣幹了...O(n) , 如果打表的話是O(n^2)

    for(int i=2*n; i>=n+1; i--) a*=i;
    for(int i=1; i<=n;i++) b*=i;
    printf("%I64d\n", a/b);

B: (頹題, Constructive Algorithm, Greedy)


題意: Given 幾條不同長度的List, 需要把每條List的所有位置填色。任意兩條List的任意顏色的數量差距不能大過1 (eg: 不可以List A有3格紅色, List B 只有1格紅色), 求任意一種填色方法 s.t. 使用的顏色數量 <= k

又一題頹題.....我是很想這樣說的
無耐我中伏多次, 卡題很久, 所以不這樣說了...
只能說它是不太用什麼特別的方法, 可是有一些陷阱一個不注意就會被抓了...
基本就是Greedy地填...是這樣說, 實際如何呢?
把第一層填顏色1, 第二層填2, 如此類推?  
錯了
因為頭兩層可以一起用顏色1....那麼特別處理最低層跟次最低層...可以嗎?
Code起上來也很煩...

結果我還是改邪歸正, 看它數據很小, 所以干脆Brute Force, 每次試填某種顏色之前
先看看會否令Configuration violate要求, 如果要的話就把顏色+1, 不然的話就繼續用該顏色, 同時update 每條List 使用該種顏色的總數...

很慢很蠢, 但AC, O(n^2) 甚至 O(n^2 lg n)也可以

C: (Math, Greedy)


我做的4題內最難/煩的一題...也是我水過了的一題...

題意很簡單: Given 一個Sequence B, 求一個Sequence A s.t. a_i 的 sum of digits = b_i
而且A要是increasing sequence!!

Sequence 長度跟值的maximum都是300, 所以自然想到暴力的方向, 所以就暴力起來了...
我的方法也沒什麼好講的...就是每個可能的數 [1,300]
都Greedy地找出它最小的 a_i, 就是除9除9除9...這樣的方法
然後再寫了一個function 可以把某個數加大, 加大完之後的sum of digit也是一樣的, 當然所謂加大就是最低限度地加大...這個function寫到我快哭了, 其實跟人手進位差不多, 不過要考慮得更多...不然會太慢, 最後類似是找到進位的位置, 把位置後面的部分, replace成上述的最小的a_i
for eg,  "18970", 進位變 19???,  而???的總和是16, 所以replace成16的最小a_i "79",  中間還有位的則補零--> "19079"
開頭的做法是更加笨實的, input每一個數, 我就由該個數的最小a_i, 一路加大直至比sequence中上一個數更大才停止...
當然超時了, 說到時間性, 這題的分析有點複雜, 我大約猜是 O(n^3), 但editorial很嚴謹地說出 n ~340, 我就沒深究了..

那麼如何不超時呢? 很簡單, 暴力
只要發現到其實可以分case解決的話就可以不用由最小的a_i 開始試起, 而是直接加大一次就完事, case分為 b_i 比 b_i-1  大 或者 小, 然後內面再分case...共3-4個cases..

我就不詳細寫了..這題我真心認為沒太大價值, 玩玩就好...
趣事是, 我第一次AC的code, 被我一個很簡單的test case駁倒了...(我找其它AC的code試過, 我的code的確是錯的) 我也在Editorial的comment上留了個言 lol
不過那個bug加一句就fix了, 改了後再交也是AC的
不過這題令我了解到, 只要不怕煩, 也不怕醜, 很難看的Code也是可以AC的=.=

自己看那個醜陋的程度吧...我不想再面對了:

E: (Math, String, Combinatorics)

一題似深還淺, 難分淺與深的題目...
題目給了一條公式, 用來計算一條String的漂亮度
hen the simple prettiness of s is defined by the formula:
The prettiness of s equals

當中vowel = "AEIOUY" 其中的characters. String的長度有5*10^5那麼長, 
肯定是O(n)或是O(n lg n)的了...
由於公式的屎忽程度...
那個分母啊...是各自substring的長度啊..不能抽出來算的啊 

怎樣不用兩個loop以上去計... 不知怎的就是會把思路引去partial sum, 的確也是很有幫助的.. 
但不是直接去數"每條substring內有多少vowels"這樣的, 因為這樣是以substring數為主 避不開n^2的 

那麼換個思路, 數每條substring長度為 s 的, 共有多少vowels? 這樣也沒用, s 的確只有n 個變化, 可是還是要一條條substring去數, 次序換了而已=.= 

當這樣的情況, 我也應該要開始習慣下了... 就可以試試逆轉思路, 
我們肯定正確 (只是太慢) 的solution是 "每條substring內有多少vowels" 
把它逆轉就是"每個vowel被多少條substrings包住?"
這就是正解了! 接下來就只是小心的數, 而且當中自然會用得上partial sum的, 看我用久違的小畫家來解說
圖中紅色的是以O(n) scan string時現在的位置, 剛好是vowel
那麼發現, 要包含它在內的長度為4的substring, 最多只有4條...就是如圖中, 它剛好在substring的最右, 一路移位, 直到substring的最左, 總共4條
同理, 長度為i的最多也只有i條,  但注意, 可能不足 i 條 ...

然後, 長度一樣為 s 的substring其實可以一起算, 題目的公式其實是統計了所有的substrings,
?/1 + ?/2 + ?/3 + .... + ?/N,   當中分母代表substring 長度s
先來看看code...(有時看回去, 我也不知我在寫什麼, 為什麼這樣能AC...=.=)
OK, 洗個澡後回來想清楚了, 關鍵性的一步就是把 substring 數分開三個部分來算
首先是長度為 i 也有i 條的, 他們加起來就是 1+1+1..+1 也就是for loop內的 第一個部分: mi
然後兩部分可以說是對稱的, 那時在公司不知怎的沒怎麼想就分兩個partial sum去做了..
第一部分是上圖的藍色箱子(代表substring) 一直向右移, 移到整個比紅色格子右了 也還沒到整條string的盡頭...這樣的一些substring
第二部分是反過來, 一直向右移,  還沒移到最左格跟紅格重疊時, 最右格已經到了整條string的盡頭了...這樣的一些substring

這樣算起來還是很快的, 只用了O(n)的時間, 我要重申兩點...
  1. 有時真的不知為什麼我會做到那條題目的
  2. 學一個朋友說話: Counting真的是一樣很神奇的工具

#include<bits/stdc++.h>
using namespace std;

char s[500010]; 
int l;
double sum[500010] = {0}, sum2[500010] = {0}, ans = 0;
int main(){
    scanf("%s", s);
    l = strlen(s);
    for(int i=1; i<=l;i++) {sum[i] = sum[i-1] + 1.0/i; sum2[i] = sum2[i-1] + (l-i+1.0)/i;}
    
    for(int i=0; i<l;i++){
        if(s[i] == 'A' || s[i] == 'E' || s[i] == 'O' || s[i] == 'I' || s[i] == 'U' || s[i] == 'Y'){
            //Counting! count each vowel contains in how many substring and add their sum by partial sum directly
            int pre = i+1, post = l-i;
            int mi = min(pre,post);
            ans += mi + mi*(sum[l-mi+1] - sum[mi]) + (sum2[l]-sum2[l-mi+1]);
        }
    }   

    printf("%f\n", ans);
    return 0;   
}
張貼者： 於
標籤： , , , , ,

沒有留言:

張貼留言

訂閱： 張貼留言 (Atom)