A Coding E. Coli

2018年5月26日星期六

[比賽紀錄] LeetCode Weekly Contest #86

睡過頭…

同步 post 於 WP

https://colistar905208901.wordpress.com/2018/05/27/leetcode-weekly-contest86/

Q1. Magic Squares In Grid

給定一個 100 x 100 2d-array，
問有多少 3 x 3 sub-array 是魔方陣。
(即行列對角線都是 15 且數字 1~9 不重複。)

這種範圍超小的拼速度題目重點變成了怎麼寫比較快，
直覺的做法有兩種：

直接靠定義作，每個 sub-array 檢查八條跟數字範圍。
因為 3×3 魔方陣只有一種 (跟他的旋轉鏡射) 先把那種手寫出來後做 pattern matching 。

由於還要做八種旋轉鏡射，這題當然是寫 1. 快很多啦。

Q2. Keys and Rooms

有許多房間，每個房間都有其他房間的鑰匙。
你一開始在房間 0 ，問你能不能進入所有房間。

非常明顯的純 BFS 題，事實上這根本是直接給你 adjacency matrix 的意思。

Q3. Split Array into Fibonacci Sequence

將一個 digit 串拆成 >= 3塊，
滿足剛好由左而右形成類似費氏數列的關係。
例如 “110111122335588143″ 拆成 [11, 0, 11, 11, 22, 33, 55, 88, 143]

串長度至多 200 ，一看又是純粹考實作。

因為要處理 leading zero 問題，
最簡單的想法當然是把整個數列以整數方式儲存後再轉為字串，作字串比對。
這樣單一次比對的複雜度是 $O(length)$ ，顯然很充裕。

那麼就只要枚舉前兩項 F1, F2 即可。

Q4. Guess the Word

給你一個 100 words 的字典，單字長度都是 6。
對方已經想了一個字典內的單字，你要在 10 次 guess 中猜到它。
你每次 guess 可以猜一個單字，他會告訴你有多少個字元位置正確 (match)。
例如答案為 “abcdef" 你 guess(“abccfe") 會得到 3

又是 100 看到就知道複雜度不是重點。

考量我們有一個 wordlist 的情況，有什麼做法能比亂猜更好？
因為字典在我們這邊，我們可以每個都 guess 看看，看 match 的分布哪個最好。
怎麼判斷 match 的分布哪個最好最單純的想法就是 minimize max value。

照著這樣做就可以過了。

(第一次寫的時候根本沒有minimize max value，固定 guess index 0 當然的錯了)

時間分配

Q1 (+26min)
Q2 (+11min)
Q3 (+15min)
Q4 (+16min) (+1bug)

賴床太久寫太慢好像就這樣
Q2 發現對 python 語法不太熟 (有內建的好用 queue 嗎)
馬上轉寫 c++

Q3 還是跟 python 語法不太熟 array of chars / string 搞好久

[比賽紀錄] Meteor Coding Cup Round #4

臨時被抓去打的，給高中生的競賽程式用的比賽。
題目我覺得給高中競賽現役玩挺好的，不過我太久沒碰競賽程式了打得很爛。
(搞不好對高中現役來說過簡單，我就不知道了)

https://colistar905208901.wordpress.com/2018/05/27/mcc-4/

以後搬到 WP 好了支援 latex / markdown 還是滿舒服的

2017年5月11日星期四

hihocoder 1517 模拟降水

有夠難寫的
先放草稿，有空或心情好再修

簡單將作法分為三個部分

第一步是要把可以接受雨量的區域橫向切成許多矩形，這邊用 Stack （堆疊）操作，並且要把實際上不能接水（碰到最左最右的）做標記

第二步是計算降水我們先處理比較簡單的case：一定只會從最左邊降水，那會發現會優先選擇從「右界較小」的矩形降水，右界相同時是「左界較大」，依序標上降水順序，一個一個填滿，將填滿後的資料記下來，會是一個個矩形，我們稱做降水矩形

不過注意這題降水點在中間這樣就是左右分別標好後取面積較小的先填滿不過這邊有個麻煩case是要處理橫跨自己的矩形。
事實上 case 是五個，依序是
1. 左右是同一塊，都是跨過降水點的矩形
2. 左邊跨過降水點右邊是正常，如此水會全部往右流
3. 和2.相反
4. 左右都正常，左邊較小，如此會花 w 將左邊填滿，同時 w 流向右邊
5. 和4.相反

第三步就是哪些被填滿多少後計算 T 那點的深度這點就簡單了。
事實上只需要把經過 T 的降水矩形高度加起來就好。
要求出全部也很簡單，對每個降水矩形用左界+h右界-h 左往右做總和序列就好了

http://ideone.com/vc74vJ

2012年10月3日星期三

NTUJ 1317 Another Easy but Not That Easy Problem

.
.

世界奇怪的題目耶，

Def f(a) = 1^x + 2^x + ... + a^x

可以知道f()應該是一個(x+1)次函式，

既然是(x+1)次咩，表示只要給定x+2個數字，就可以決定這個函式

這時候就用拉格朗日長直髮不對拉格朗日插值法，

而很巧妙的，如果我們帶的是f(1)~f(x+2)，盯著下面這個式子看

Σ bj * Π(a-ai)/(aj-ai)

會發現他變成

Σbj * [ (a-1)(a-2)...(a-(aj-1)) / (aj-1)! ] * [ (a-(aj+1))(a-(aj+2))...(a-(x+2)) / (x+2-aj)! ] * (-1)^(x+2-aj)

哇烏這不就

Σbj [C(a-1)取(aj-1)] * [C(a-aj-1)取(x+2-aj)] * (-1)^(x+2-aj)

輕鬆愉快

總複雜度O(x)

2012年9月7日星期五

NTUJ 1707 k-th number

恩沒錯，就是傳說中的經典的劃分樹。                                                                                                   .

其實超級好寫，只是兒子的區間要算好|||。

還有如果數字相同要處理一下，這個有點麻煩就是，還好這題保證沒有相同

網路上找得到許多教程，其實瞪著notonlysuccess的圖看幾秒就會領悟了

所以只是來備份代碼

#include <cstdio>
#include <cstring>
#include <algorithm>

#define MN 100010

int sorted[MN], val[20][MN], lcnt[20][MN];
int N, Q;

void build(int tl, int tr, int dep) {
   if(tl == tr) return ;
   int mid = (tl+tr)/2, pre = 0;
   int lc = tl, rc = mid+1;
   for(int i=tl; i<=tr; i++) {
       lcnt[dep][i] = pre;
       if(val[dep][i] <= sorted[mid]) {
           lcnt[dep][i] ++;
           val[dep+1][lc ++] = val[dep][i];
       }
       else val[dep+1][rc ++] = val[dep][i];
       pre = lcnt[dep][i];
   }
   build(tl, mid, dep+1);
   build(mid+1, tr, dep+1);
}

int query(int ql, int qr, int tl, int tr, int k, int dep) {
   if(tl == tr) return val[dep][tl];
   int mid = (tl+tr)/2, ql2L, qr2L, qinL;
   ql2L = lcnt[dep][ql] - (val[dep][ql]<=sorted[mid]);
   qr2L = lcnt[dep][qr];
   qinL = qr2L - ql2L;
   int newL, newR, newK;
   if(qinL >= k) {
       newL = tl + ql2L;
       newR = tl + qr2L - 1;
       newK = k;
       return query(newL, newR, tl, mid, newK, dep+1);
   }
   else {
       newL = mid + ql - tl - ql2L + 1;
       newR = mid + qr - tl - qr2L + 1;
       newK = k - qinL;
       return query(newL, newR, mid+1, tr, newK, dep+1);
   }

}

int main() {
   while(~scanf("%d%d", &N, &Q)) {
       for(int i=1; i<=N; i++) {
           scanf("%d", sorted+i);
           val[0][i] = sorted[i];
       }
       std::sort(sorted+1, sorted+1+N);
       build(1, N, 0);
       for(int i=1; i<=Q; i++) {
           int L, R, K;
           scanf("%d%d%d", &L, &R, &K);
           printf("%d\n", query(L, R, 1, N, K, 0));
       }
   }
}

2011年7月12日星期二

TIOJ 1100 C.畢業演奏 [DP]

我說這題好詭異……O(N*L)會過是毛啦orz
Nice Problem.只是我想了太久XDrz

要先有一個概念：如果最後有合奏的學姐序列依照合奏時間用S1~Sk表示。

那麼對任意i，一定有Si的編號 < S(i+1)的編號。

也就是不會有a區間比b區間前面但是a學姐比b學姐晚合奏完的情況。

怎麼證明呢？假設最佳序列是S'1~S'k而且其中存在一個i，S'i的編號 > S'(i+1)的編號

但經過一點點的小證明可以發現，把這兩個學姐交換順序也一定存在一個合法的合奏方案。

//因為區間有非嚴格遞增性才會合理。

所以我們可以用DP[i][j]表示做完前i個學姐，取了j個學姐時最右界的位置。

每個轉移O(1)，總複雜度O(N^2)

2011年6月20日星期一

UVa 506 System Dependencies

,

,

,

,

,

Link

===簡單的翻譯(不逐字翻了...字好多)

安裝軟體有很多依存關係，例如說你沒有TCPIP你就裝不起來TELNET。

所以如果明確(explicity)要裝TELNET，你會附帶地把TCPIP裝起來。

等你下次裝FTP(也需要TCPIP)時，就不用重裝一遍TCPIP。

但同樣的，在TELNET還裝著的情況下你不能把TCPIP移除。

有時候我們需要移除一些程式。為了省出更多空間，我們在移除某些程式時會把一些

只為了這個程式能正常運行才附帶安裝的檔案一起移除。

例如說如果我們為了裝TELNET而把TCPIP附帶裝起來，之後我們移除TELNET時發現，

TCPIP只是為了讓TELNET能正常運作而附帶安裝，TELNET移除後TCPIP將沒有存在的必要

便會順便將TCPIP解除安裝。

已經裝上的軟體不會再被安裝一遍(因為附帶而安裝的軟體不會因為再被安裝一遍而

變成明確要安裝的軟體)、已經移除的軟體也不能再被移除。

===

寫這題用到一堆C++的技巧xD

#include <cstdio>

#include <cstdlib>

#include <cstring>

#include <iostream>

#include <sstream>

#include <list>

#include <vector>

#include <string>

#include <map>

#define MAX 2510

//Converter

std::map<std::string, int> conv;

std::string rconv[MAX];

int ccnt;

//Answer List

std::list<int> ans;

std::list<int>::iterator it;

//Graph

std::vector<int> re[MAX], ee[MAX];

//DAG DP

int chneed[MAX], vst[MAX], ins[MAX], im[MAX];

//Parser

std::stringstream sin;

std::string buf;

inline int getno(std::string&b) {

int rtn = conv[b];

if(rtn == 0) {

  ccnt ++;

  conv[b] = ccnt;

  rconv[ccnt] = b;

  rtn = ccnt;

}

return rtn;

}

inline void insert(int np) {

ans.push_back(np);

ins[np] = true;

std::cout << "   Installing " << rconv[np] << '\n';

}

void dfsI(int now) {

chneed[now] ++;

vst[now] ++;

for(int i=re[now].size()-1,nxt; i>=0; i--) {

  nxt = re[now][i];

  if(vst[nxt]) continue;

  dfsI(nxt);

}

if(!ins[now]) {

  ins[now] = true;

  insert(now);

}

}

inline void remove(int np) {

ans.remove(np);

ins[np] = im[np] = false;

std::cout << "   Removing " << rconv[np] << '\n';

}

void dfsR1(int now, int need) {

vst[now] = true;

chneed[now] -= need;

for(int i=re[now].size()-1,nxt; i>=0; i--) {

  nxt = re[now][i];

  if(vst[nxt]) continue;

  dfsR1(nxt, need);

}

}

void dfsR2(int now) {

if(chneed[now]) return;

int can = true;

for(int i=ee[now].size()-1,nxt; i>=0; i--) {

  nxt = ee[now][i];

  if(ins[nxt]) {

   can = false;

   break;

  }

}

if(!can) return;

remove(now);

for(int i=re[now].size()-1,nxt; i>=0; i--) {

  nxt = re[now][i];

  if(!ins[nxt]) continue;

  dfsR2(nxt);

}

}

int main() {

while(true) {

  getline(std::cin, buf);

  std::cout << buf << '\n';

  sin.clear();

  sin.str(buf);

  sin >> buf;

  std::string ch, fa;

  int nch, nfa;

  switch(buf[0]) {

   case 'D':

    sin >> ch;

    nch = getno(ch);

    while(sin >> fa) {

     nfa = getno(fa);

     re[nch].push_back(nfa);

     ee[nfa].push_back(nch);

    }

   break;

   case 'I':

    sin >> ch;

    nch = getno(ch);

    if(ins[nch]) {

     std::cout << "   " << ch <<  " is already installed.\n";

    }

    else {

     memset(vst, 0, sizeof(vst));

     im[nch] = true;

     dfsI(nch);

    }

   break;

   case 'R':

    sin >> ch;

    nch = getno(ch);

    if(!ins[nch]) {

     std::cout << "   " << ch << " is not installed.\n";

    }

    else {

     if(chneed[nch]>1 || (chneed[nch]==1 && !im[nch])) {

      std::cout << "   " << ch << " is still needed.\n";

     }

     else {

      memset(vst, 0, sizeof(vst));

      dfsR1(nch, im[nch]);

      dfsR2(nch);

     }

    }

   break;

   case 'L':

    for(it=ans.begin(); it!=ans.end(); it++) {

     std::cout << "   " << rconv[*it] << '\n';

    }

   break;

   case 'E':

    exit(0);

   break;

  }

}

}

//8966453  506  System Dependencies  Accepted  C++  0.024  2011-06-19 06:57:53

訂閱：文章 (Atom)

2018年5月26日 星期六