POJ.3709 K-Anonymous Sequence

1.Problem
3709 -- K-Anonymous Sequence (poj.org)

2.Idea
Deque

3.Source

 int n, k;  
 Int a[N];  
 Int dp[N], S[N];  
 int deq[N];  
 Int f(int j, int x)  
 {  
      return -a[j] * x + dp[j] - S[j] + a[j] * j;  
 }  
 bool check(int f1, int f2, int f3)  
 {  
      Int a1 = -a[f1], b1 = dp[f1] - S[f1] + a[f1] * f1;  
      Int a2 = -a[f2], b2 = dp[f2] - S[f2] + a[f2] * f2;  
      Int a3 = -a[f3], b3 = dp[f3] - S[f3] + a[f3] * f3;  
      return (a2 - a1) * (b3 - b2) >= (b2 - b1) * (a3 - a2);  
 }  
 void solve()  
 {  
      int t; cin >> t;  
      while (t--) {  
           scanf("%d%d", &n, &k);  
           for (int i = 0; i < n; i++) {  
                scanf("%d", &a[i]);  
           }  
           for (int i = 0; i < n; i++) {  
                S[i + 1] = S[i] + a[i];  
           }  
           int s = 0, t = 1;  
           deq[0] = 0;  
           dp[0] = 0;  
           for (int i = k; i <= n; i++) {  
                if (i - k >= k) {  
                     while (s + 1 < t && check(deq[t - 2], deq[t - 1], i - k)) t--;  
                     deq[t++] = i - k;  
                }  
                while (s + 1 < t && f(deq[s], i) >= f(deq[s + 1], i)) s++;  
                dp[i] = S[i] + f(deq[s], i);  
           }  
           printf("%lld\n", dp[n]);  
      }  
 }  

LeetCode.472 Concatenated Words

1.Problem
Concatenated Words - LeetCode

2.Idea
Trie + DFS

3.Source

 class TrieNode {  
   public:  
   bool isKey = false;  
   TrieNode* child[26];  
 };  
 class Solution {  
 public:  
   TrieNode* root = new TrieNode();  
   void addWord(string word) {  
     TrieNode* curr = root;  
     for(char c : word) {  
       if(!curr->child[c - 'a'])  
         curr->child[c - 'a'] = new TrieNode();  
       curr = curr->child[c - 'a'];  
     }  
     curr->isKey = true;  
   }  
   bool search(string word, int index, int count) {  
     if(index >= word.size()) return count >= 2;  
     TrieNode* curr = root;  
     for(int i= index; i < word.size(); i++) {  
       char c = word[i];  
       if(!curr->child[c - 'a'])  
         return false;  
       curr = curr->child[c - 'a'];  
       if(curr->isKey) {  
         if(search(word, i+1, count + 1))  
           return true;  
       }  
     }  
     return false;  
   }  
   vector<string> findAllConcatenatedWordsInADict(vector<string>& words) {  
     vector<string> res;  
     if(words.size() == 0) return res;  
     for(string s : words)   
       addWord(s);  
     for(string s : words) {  
       if(search(s, 0, 0))  
         res.push_back(s);  
     }  
     return res;  
   }  
 };  

POJ.2082 Terrible Sets

1.Problem
2082 -- Terrible Sets (poj.org)

2.Idea
Description is terrible but it was just simple max rectangle in histogram problem.

3.Source

 int n;  
 int h[N];  
 int st[N], L[N], R[N], sum[N];  
 int maxRec() {  
      //L   
      int t = 0;  
      for (int i = 0; i < n; i++) {  
           while (t > 0 && h[st[t - 1]] >= h[i]) t--;  
           L[i] = (t == 0 ? 0 : (st[t - 1] + 1));  
           st[t++] = i;  
      }  
      //R   
      t = 0;  
      for (int i = n - 1; i >= 0; i--) {  
           while (t > 0 && h[st[t - 1]] >= h[i]) t--;  
           R[i] = (t == 0 ? n : st[t - 1]);  
           st[t++] = i;  
      }  
      int res = 0;  
      for (int i = 0; i < n; i++) {  
           res = max(res, h[i] * (sum[R[i]] - sum[L[i]]));  
      }  
      return res;  
 }  
 void solve()  
 {  
      while (cin >> n) {  
           if (n < 0) break;  
           for (int i = 0; i < n; i++) {  
                scanf("%d%d", &sum[i + 1], &h[i]);  
           }  
           for (int i = 0; i < n; i++)   
                sum[i + 1] += sum[i];  
           printf("%d\n", maxRec());  
      }  
 }  

POJ.3250 Bad Hair Day

1.Problem
3250 -- Bad Hair Day (poj.org)

2.Idea
Use monoton stack

3.Source

 int n;  
 Int h[80200];  
 void solve()  
 {       
      int n; cin >> n;  
      for (int i = 0; i < n; i++) {  
           scanf("%d", &h[i]);  
      }  
      h[n] = MOD;  
      Int ans = 0;  
      stack<int> st;//monoton stack  
      for (int i = 0; i <= n; i++) {  
           if (st.empty() || h[st.top()] > h[i])  
                st.push(i);  
           else {  
                while (!st.empty() && h[st.top()] <= h[i]) {  
                     int tmp = st.top(); st.pop();  
                     ans += (Int)(i - tmp - 1);  
                }  
                st.push(i);  
           }  
      }  
      printf("%lld\n", ans);  
 }  

POJ.3494 Largest Submatrix of All 1’s

1.Problem
3494 -- Largest Submatrix of All 1’s (poj.org)

2.Idea
Apply the max rectangle in histogram problem.

3.Source

 int m, n;  
 int h[2200];  
 int st[2200], L[2200], R[2200];  
 int maxRec() {  
      //L  
      int t = 0;  
      for (int i = 0; i < n; i++) {  
           while (t > 0 && h[st[t - 1]] >= h[i]) t--;  
           L[i] = (t == 0 ? 0 : (st[t - 1] + 1));  
           st[t++] = i;  
      }  
      //R  
      t = 0;  
      for (int i = n - 1; i >= 0; i--) {  
           while (t > 0 && h[st[t - 1]] >= h[i]) t--;  
           R[i] = (t == 0 ? n : st[t - 1]);  
           st[t++] = i;  
      }  
      int res = 0;  
      for (int i = 0; i < n; i++) {  
           res = max(res, h[i] * (R[i] - L[i]));  
      }  
      return res;  
 }  
 void solve()  
 {       
      while (cin >> m >> n) {  
           memset(h, 0, sizeof h);  
           int ans = 0;  
           for (int i = 0; i < n; i++) {  
                for (int j = 0; j < m; j++) {  
                     int t; scanf("%d", &t);  
                     h[j] = t ? h[j] + 1 : 0;  
                }  
                ans = max(ans, maxRec());  
           }  
           printf("%d\n", ans);  
      }  
 }  

POJ.2559 Largest Rectangle in a Histogram

1.Problem
2559 -- Largest Rectangle in a Histogram (poj.org)

2.Idea
Using stack

3.Source

 int n;  
 int h[N];  
 int L[N], R[N], st[N];  
 void solve()  
 {       
      while (scanf("%d", &n), n) {  
           REP(i, n) scanf("%d", &h[i]);  
           //L  
           int t = 0;  
           for (int i = 0; i < n; i++) {  
                while (t > 0 && h[st[t - 1]] >= h[i]) t--;  
                L[i] = (t == 0 ? 0 : (st[t - 1] + 1));  
                st[t++] = i;  
           }  
           //R  
           t = 0;  
           for (int i = n - 1; i >= 0; i--) {  
                while (t > 0 && h[st[t - 1]] >= h[i]) t--;  
                R[i] = (t == 0 ? n : st[t - 1]);  
                st[t++] = i;  
           }  
           long long res = 0;  
           for (int i = 0; i < n; i++) {  
                res = max(res, (long long)h[i] * (R[i] - L[i]));  
           }  
           printf("%lld\n", res);  
      }  
 }  

POJ.3729 Facer’s string

1.Problem
3729 -- Facer’s string (poj.org)

2.Idea
Suffix Array
Longest Common Prefix Array

3.Source Code

 const int MAXN = 50010;  
 int n, N, M, k, K;  
 int Rank[MAXN * 2];  
 int tmp[MAXN * 2];  
 int sa[MAXN * 2];  
 int lcp[MAXN * 2];  
 int s[MAXN * 2];  
 bool compare_sa(const int& i, const int& j) {  
      if (Rank[i] != Rank[j])return Rank[i] < Rank[j];  
      else {  
           int ri = i + k <= n ? Rank[i + k] : -1;  
           int rj = j + k <= n ? Rank[j + k] : -1;  
           return ri < rj;  
      }  
 }  
 void construct_sa(const int *S, int *sa) {  
      for (int i = 0; i <= n; i++) {  
           sa[i] = i;  
           Rank[i] = i < n ? S[i] : -1;  
      }  
      for (k = 1; k <= n; k *= 2) {  
           sort(sa, sa + n + 1, compare_sa);  
           tmp[sa[0]] = 0;  
           for (int i = 1; i <= n; i++) {  
                tmp[sa[i]] = tmp[sa[i - 1]] + (compare_sa(sa[i - 1], sa[i]) ? 1 : 0);  
           }  
           for (int i = 0; i <= n; i++) {  
                Rank[i] = tmp[i];  
           }  
      }  
 }  
 void construct_lcp(const int *S, int *sa, int *lcp) {  
      memset(lcp, 0, sizeof(lcp));  
      for (int i = 0; i <= n; i++)Rank[sa[i]] = i;  
      int h = 0;  
      lcp[0] = 0;  
      for (int i = 0; i < n; i++) {  
           int j = sa[Rank[i] - 1];  
           if (h > 0)h--;  
           for (; j + h < n&&i + h < n; h++) {  
                if (S[j + h] != S[i + h])break;  
           }  
           lcp[Rank[i] - 1] = h;  
      }  
 }  
 long long calc(int K) {  
      int A = 0, B = 0;  
      long long res = 0;  
      for (int i = 0; i < n; i++) {  
           if (lcp[i] < K) {  
                if (B > 0)res += A;  
                A = 0; B = 0;  
           }  
           if (sa[i + 1] < N)A++;  
           if (sa[i + 1] > N) B++;  
      }  
      return res;  
 }  
 void solve()  
 {       
      while (scanf("%d%d%d\n", &N, &M, &K) != EOF) {  
           for (int i = 0; i < N; i++) {  
                scanf("%d", &s[i]);  
                s[i]++;  
           }  
           s[N] = '$';  
           for (int i = N + 1; i < N + M + 1; i++) {  
                scanf("%d", &s[i]);  
                s[i]++;  
           }  
           n = N + M + 1;  
           s[n] = 0;  
           construct_sa(s, sa);  
           construct_lcp(s, sa, lcp);  
           printf("%lld\n", calc(K) - calc(K+1));  
      }  
 }  

POJ.3415 Common Substrings

1.Problem
3415 -- Common Substrings (poj.org)

2.Idea
Suffix Array
Monotonic Stack

3.Source

 const int MAX_L = 100000 + 1;  
 const int MAX_N = 2 * MAX_L + 1;  
 std::string S;  
 int n, k;  
 int sa[MAX_N + 1], lcp[MAX_N + 1];   
 int Rank[MAX_N + 1], tmp[MAX_N + 1];  
 bool compare_sa(const int i, const int j)  
 {  
      if (Rank[i] != Rank[j])  
      {  
           return Rank[i] < Rank[j];  
      }  
      return (i + k <= n ? Rank[i + k] : -1) < (j + k <= n ? Rank[j + k] : -1);  
 }  
 void construct_sa()  
 {  
      for (int i = 0; i <= n; i++)  
      {  
           sa[i] = i;  
           Rank[i] = i < n ? S[i] : -1;  
      }  
      for (k = 1; k <= n; k <<= 1)  
      {  
           std::sort(sa, sa + n + 1, compare_sa);  
           tmp[sa[0]] = 0;  
           for (int i = 1; i <= n; i++)  
           {  
                tmp[sa[i]] = tmp[sa[i - 1]] + (compare_sa(sa[i - 1], sa[i]) ? 1 : 0);  
           }  
           for (int i = 0; i <= n; i++)  
           {  
                Rank[i] = tmp[i];  
           }  
      }  
 }  
 void construct_lcp()  
 {  
      memset(lcp, 0, sizeof(lcp));  
      for (int i = 0; i <= n; i++)  
      {  
           Rank[sa[i]] = i;  
      }  
      int h = 0;  
      lcp[0] = 0;  
      for (int i = 0; i < n; i++)  
      {  
           int j = sa[Rank[i] - 1];  
           if (h > 0)  
           {  
                h--;  
           }  
           for (; i + h < n && j + h < n && S[i + h] == S[j + h]; h++);  
           lcp[Rank[i] - 1] = h;  
      }  
 }  
 int Stack[MAX_N][2];  
 long long contribution, top;  
 using namespace std;  
 long long calc(int K, int l1, bool is_s1)  
 {  
      long long ans = 0;  
      for (int i = 0; i < n; i++) {  
           if (lcp[i] < K) {  
                top = contribution = 0;  
           }  
           else {  
                int size = 0;  
                if ((is_s1 && sa[i] < l1) || (!is_s1 && sa[i] > l1)) {  
                     ++size;  
                     contribution += lcp[i] - K + 1;  
                }  
                while (top > 0 && lcp[i] <= Stack[top - 1][0]) {  
                     --top;  
                     contribution -= Stack[top][1] * (Stack[top][0] - lcp[i]);  
                     size += Stack[top][1];  
                }  
                if (size) {  
                     Stack[top][0] = lcp[i];  
                     Stack[top][1] = size;  
                     ++top;  
                }  
                if ((is_s1 && sa[i + 1] > l1) || (!is_s1 && sa[i + 1] < l1)) {  
                     ans += contribution;  
                }  
           }  
      }  
      return ans;  
 }  
 void solve()  
 {  
      int k;  
      while (scanf("%d", &k), k) {  
           string s1, s2;  
           cin >> s1 >> s2;  
           int l1 = s1.length();  
           int l2 = s2.length();  
           S = s1 + "$" + s2;  
           n = l1 + l2 + 1;  
           construct_sa();  
           construct_lcp();  
           printf("%lld\n", calc(k, l1, true) + calc(k, l1, false));  
      }  
 }  
 int main() {  
      ios_base::sync_with_stdio(0); cin.tie(0); cout << fixed << setprecision(13);  
      solve();  
      return 0;  
 }  

POJ.1509 Glass Beads

1.Problem
1509 -- Glass Beads (poj.org)

2.Idea
Suffix Array

3.Source Code

 const int MAXN = 20010;  
 int Rank[MAXN], tmp[MAXN];  
 int n, k;  
 int sa[MAXN];  
 bool compare_sa(int i, int j) {  
      if (Rank[i] != Rank[j]) return Rank[i] < Rank[j];  
      int ri = (i + k <= n) ? Rank[i + k] : -1;  
      int rj = (j + k <= n) ? Rank[j + k] : -1;  
      return ri < rj;  
 }  
 void createSA(const string& s, int* sa) {  
      n = s.size();  
      for (int i = 0; i <= n; i++) {  
           sa[i] = i;  
           Rank[i] = i < n ? s[i] : -1;  
      }  
      for (k = 1; k <= n; k *= 2) {  
           sort(sa, sa + n + 1, compare_sa);  
           tmp[sa[0]] = 0;  
           for (int i = 1; i <= n; i++) {  
                tmp[sa[i]] = tmp[sa[i - 1]] + (compare_sa(sa[i - 1], sa[i]) ? 1 : 0);  
           }  
           for (int i = 0; i <= n; i++) Rank[i] = tmp[i];  
      }  
 }  
 char str[MAXN];  
 void getInput(string& s) {  
      fgets(str, MAXN, stdin);  
      strtok(str, "\n\0");  
      s = str;  
 }  
 void solve()  
 {  
      int t;  
      scanf("%d\n", &t);  
      while (t--) {  
           string S;  
           getInput(S);  
           createSA(S + S + (char)('z' + 1), sa);  
           int ans = -1;  
           for (int i = 0; i <= n; i++) {  
                if (sa[i] < S.length()) {  
                     ans = sa[i] + 1;  
                     break;  
                }  
           }  
           printf("%d\n", ans);  
      }  
 }  
 int main() {  
      ios_base::sync_with_stdio(0); cin.tie(0); cout << fixed << setprecision(13);  
      solve();  
      return 0;  
 }  

POJ.2217 Secretary

1.Problem
2217 -- Secretary (poj.org)

2.Idea
Suffix Array
Longest Common Prefix Array

3. Source Code

 const int MAXN = 20010;  
 namespace SA {  
      int rank[MAXN], tmp[MAXN];  
      int n, k;  
      bool compare_sa(int i, int j) {  
           if (rank[i] != rank[j]) return rank[i] < rank[j];  
           int ri = (i + k <= n) ? rank[i + k] : -1;  
           int rj = (j + k <= n) ? rank[j + k] : -1;  
           return ri < rj;  
      }  
      void createSA(const string& s, int* sa) {  
           n = s.size();  
           for (int i = 0; i <= n; i++) {  
                sa[i] = i;  
                rank[i] = i < n ? s[i] : -1;  
           }  
           for (k = 1; k <= n; k *= 2) {  
                sort(sa, sa + n + 1, compare_sa);  
                tmp[sa[0]] = 0;  
                for (int i = 1; i <= n; i++) {  
                     tmp[sa[i]] = tmp[sa[i - 1]] + (compare_sa(sa[i - 1], sa[i]) ? 1 : 0);  
                }  
                for (int i = 0; i <= n; i++) rank[i] = tmp[i];  
           }  
      }  
      namespace LCP {  
           int rank[MAXN];  
           void createLCP(const string& s, const int* sa, int* lcp) {  
                int n = s.size();  
                for (int i = 0; i <= n; i++) rank[sa[i]] = i;  
                int h = 0;  
                lcp[0] = 0;  
                for (int i = 0; i < n; i++) {  
                     int j = sa[rank[i] - 1];  
                     h = max(0, h - 1);  
                     for (; j + h < n && i + h < n; h++) {  
                          if (s[j + h] != s[i + h]) break;  
                     }  
                     lcp[rank[i] - 1] = h;  
                }  
           }  
      } // namespace LCP  
 } // namespace SA  
 char str[MAXN];  
 void getInput(string& s) {  
      fgets(str, MAXN, stdin);  
      strtok(str, "\n\0");  
      s = str;  
 }  
 int sa[MAXN], lcp[MAXN];  
 void solve()  
 {  
      int t;  
      scanf("%d\n", &t);  
      while (t--) {  
           string S, T;  
           getInput(S); getInput(T);  
           int n = S.size(), m = T.size();  
           S += '\n';  
           S += T;  
           SA::createSA(S, sa);  
           SA::LCP::createLCP(S, sa, lcp);  
           int nm = S.size(), ans = 0;  
           for (int i = 0; i < nm; i++) {  
                if (sa[i] < n && sa[i + 1] < n) continue;  
                if (sa[i] > n && sa[i + 1] > n) continue;  
                ans = max(ans, lcp[i]);  
           }  
           printf("Nejdelsi spolecny retezec ma delku %d.\n", ans);  
      }  
 }  
 int main() {  
      ios_base::sync_with_stdio(0); cin.tie(0); cout << fixed << setprecision(13);  
      solve();  
      return 0;  
 }  

POJ.3581 Sequence

1.Problem
http://poj.org/problem?id=3581

2.Idea
Suffix Array

3.Source

 const int MAXN = 20010;  
 namespace SA {  
      int rank[2 * MAXN], tmp[2 * MAXN];  
      int n, k;  
      bool compare_sa(int i, int j) {  
           if (rank[i] != rank[j]) return rank[i] < rank[j];  
           int ri = (i + k <= n) ? rank[i + k] : -1;  
           int rj = (j + k <= n) ? rank[j + k] : -1;  
           return ri < rj;  
      }  
      void createSA(const int* s, int N, int* sa) {  
           n = N;  
           for (int i = 0; i <= n; i++) {  
                sa[i] = i;  
                rank[i] = i < n ? s[i] : -1;  
           }  
           for (k = 1; k <= n; k *= 2) {  
                sort(sa, sa + n + 1, compare_sa);  
                tmp[sa[0]] = 0;  
                for (int i = 1; i <= n; i++) {  
                     tmp[sa[i]] = tmp[sa[i - 1]] + (compare_sa(sa[i - 1], sa[i]) ? 1 : 0);  
                }  
                for (int i = 0; i <= n; i++) rank[i] = tmp[i];  
           }  
      }  
 }  
 int N, A[MAXN], rev[2 * MAXN], sa[2 * MAXN];  
 void solve()  
 {  
      cin >> N;  
      for (int i = 0; i < N; i++) scanf("%d", A + i);  
      reverse_copy(A, A + N, rev);  
      SA::createSA(rev, N, sa);  
      int p1, p2;  
      for (int i = 0; i <= N; i++) {  
           p1 = N - sa[i];  
           if (p1 > 0 && N - p1 >= 2) break;  
      }  
      int m = N - p1;  
      reverse_copy(A + p1, A + N, rev);  
      reverse_copy(A + p1, A + N, rev + m);  
      SA::createSA(rev, 2 * m, sa);  
      for (int i = 0; i <= 2 * m; i++) {  
           p2 = m - sa[i];  
           if (p2 > 0 && m - p2 >= 1) break;  
      }  
      for (int i = p1 - 1; i >= 0; i--) printf("%d\n", A[i]);  
      for (int i = p1 + p2 - 1; i >= p1; i--) printf("%d\n", A[i]);  
      for (int i = N - 1; i >= p1 + p2; i--) printf("%d\n", A[i]);  
 }  
 int main() {  
      //ios_base::sync_with_stdio(0); cin.tie(0); cout << fixed << setprecision(13);  
      solve();  
      return 0;  
 }  

POJ.3690 Constellations

1.Problem
http://poj.org/problem?id=3690

2.Idea
Rolling Hash D2

3.Source Code

 typedef unsigned long long ull;  
 int N, M, T, P, Q;  
 char field[1100][1100];  
 char patterns[110][1100][1100];  
 ull Hash[1100][1100], tmp[1100][1100];  
 void compute_hash(char a[1100][1100], int n, int m)  
 {  
      const ull B1 = 9973;  
      const ull B2 = 1000000007;  
      ull t1 = 1;  
      for (int j = 0; j < Q; j++) t1 *= B1;  
      for (int i = 0; i < n; i++) {  
           ull e = 0;  
           for (int j = 0; j < Q; j++) {  
                e = e * B1 + a[i][j];  
           }  
           for (int j = 0; j + Q <= m; j++) {  
                tmp[i][j] = e;  
                if (j + Q < m) e = e * B1 - t1 * a[i][j] + a[i][j + Q];  
           }  
      }  
      ull t2 = 1;  
      for (int i = 0; i < P; i++) t2 *= B2;  
      for (int j = 0; j + Q <= m; j++) {  
           ull e = 0;  
           for (int i = 0; i < P; i++) {  
                e = e * B2 + tmp[i][j];  
           }  
           for (int i = 0; i + P <= n; i++) {  
                Hash[i][j] = e;  
                if (i + P < n) e = e * B2 - t2 * tmp[i][j] + tmp[i + P][j];  
           }  
      }  
 }  
 void solve()  
 {  
      int cnt = 0;  
      while (true) {  
           scanf("%d%d%d%d%d", &N, &M, &T, &P, &Q);  
           if (N + M + T + P + Q == 0) break;  
           cnt++;  
           for (int i = 0; i < N; ++i) {  
                scanf("%s", field[i]);  
           }  
           for (int t = 0; t < T; ++t) {  
                for (int i = 0; i < P; ++i) {  
                     scanf("%s", patterns[t][i]);  
                }  
           }  
           multiset<ull> unseen;  
           for (int k = 0; k < T; k++) {  
                compute_hash(patterns[k], P, Q);  
                unseen.insert(Hash[0][0]);  
           }  
           compute_hash(field, N, M);  
           for (int i = 0; i + P <= N; i++) {  
                for (int j = 0; j + Q <= M; j++) {  
                     unseen.erase(Hash[i][j]);  
                }  
           }  
           printf("Case %d: %d\n", cnt, T - unseen.size());  
      }  
 }  
 int main() {  
      ios_base::sync_with_stdio(0); cin.tie(0); cout << fixed << setprecision(13);  
      solve();  
      return 0;  
 }  

POJ. 3691 DNA repair

1.Problem
http://poj.org/problem?id=3691

2.Idea
Here

3.Source

 const int MAXK = 1000;  
 const int MAXLEN = 1010;  
 const string AGCT = "AGCT";  
 int nextState[MAXK][4];  
 bool ng[MAXK];  
 int dp[MAXLEN][MAXK];  
 int solve(const vector<string>& ngWords, const string& init) {  
      vector<string> pfx;  
      int n = ngWords.size();  
      // 状態の列挙  
      for (int i = 0; i < n; i++) {  
           string s = ngWords[i];  
           for (int j = 0; j <= (int)s.size(); j++) {  
                pfx.push_back(s.substr(0, j));  
           }  
      }  
      sort(pfx.begin(), pfx.end());  
      pfx.erase(unique(pfx.begin(), pfx.end()), pfx.end());  
      int K = pfx.size();  
      // 状態の遷移  
      for (int i = 0; i < K; i++) {  
           for (int j = 0; j < 4; j++) {  
                string s = pfx[i] + AGCT.substr(j, 1);  
                while (1) {  
                     int nk = lower_bound(pfx.begin(), pfx.end(), s) - pfx.begin();  
                     if (nk < K && pfx[nk] == s) {  
                          nextState[i][j] = nk;  
                          break;  
                     }  
                     s = s.substr(1);  
                }  
           }  
      }  
      // 状態がngかどうか  
      for (int i = 0; i < K; i++) {  
           ng[i] = false;  
           int sl = pfx[i].size();  
           for (int j = 0; j < n; j++) {  
                int wl = ngWords[j].size();  
                if (sl < wl) continue;  
                if (pfx[i].substr(sl - wl) == ngWords[j]) {  
                     ng[i] = true;  
                     break;  
                }  
           }  
      }  
      // dp  
      int length = init.size();  
      for (int i = 0; i <= length; i++) for (int k = 0; k < K; k++) {  
           dp[i][k] = INF;  
      }  
      dp[0][0] = 0;  
      for (int l = 0; l < length; l++) for (int k = 0; k < K; k++) {  
           if (dp[l][k] == INF) continue;  
           if (ng[k]) continue;  
           for (int j = 0; j < 4; j++) {  
                int plus = (init[l] == AGCT[j]) ? 0 : 1;  
                int ns = nextState[k][j];  
                if (ng[ns]) continue;  
                dp[l + 1][ns] = min(dp[l][k] + plus, dp[l + 1][ns]);  
           }  
      }  
      int ans = INF;  
      for (int k = 0; k < K; k++) {  
           if (ng[k]) continue;  
           ans = min(ans, dp[length][k]);  
      }  
      if (ans == INF) ans = -1;  
      return ans;  
 }  
 int main() {  
      cin.tie(0);  
      ios::sync_with_stdio(false);  
      int T = 0;  
      int n;  
      while (cin >> n) {  
           if (n == 0) break;  
           T++;  
           vector<string> ngWords;  
           for (int i = 0; i < n; i++) {  
                string s;  
                cin >> s;  
                ngWords.push_back(s);  
           }  
           string init;  
           cin >> init;  
           printf("Case %d: %d\n", T, solve(ngWords, init));  
      }  
      return 0;  
 }  

POJ.3537 Crosses and Crosses

1.Problem
http://poj.org/problem?id=3537

2.Idea
Calc grundy

3.Source

 int dp[2001];  
 int grundy(int n) {  
      if (n <= 0) return 0;  
      if (~dp[n]) return dp[n];  
      vector<int> vis(1 << 11);  
      for (int i = 1; i <= n; ++i) {  
           vis[grundy(i - 1 - 2) ^ grundy(n - i - 2)] = 1;  
      }  
      for (int i = 0; ; ++i) {  
           if (!vis[i]) return dp[n] = i;  
      }  
 }  
 void solve()  
 {  
      std::memset(dp, 0xff, sizeof(dp));  
      int n;  
      cin >> n;  
      cout << (grundy(n) ? 1 : 2) << endl;  
 }  

POJ.2975 Nim

1.Problem
http://poj.org/problem?id=2975

2.Idea
Calculate Nim.

3.Source

 int n;  
 int a[1100];  
 void solve()  
 {  
      while (scanf("%d", &n)) {  
           if (n == 0) break;  
           int x = 0;  
           REP(i, n) {  
                scanf("%d", &a[i]);  
                x ^= a[i];  
           }  
           int ans = 0;  
           if (x > 0) {  
                REP(i, n) {  
                     int tmp = x ^ a[i];  
                     if (tmp <= a[i]) ans++;  
                }  
           }  
           printf("%d\n", ans);  
      }  
 }  

POJ.1704 Georgia and Bob

 1.Problem
http://poj.org/problem?id=1704

2.Idea
Using Nim

3.Source

 int n;  
 int p[N];  
 void solve()  
 {  
      int t;  
      cin >> t;  
      while (t--) {  
           cin >> n;  
           REP(i, n) cin >> p[i];  
           if (n % 2) p[n++] = 0;  
           sort(p, p + n);  
           int x = 0;  
           for (int i = 0; i + 1 < n; i += 2) {  
                x ^= (p[i + 1] - p[i] - 1);  
           }  
           if (x == 0) cout << "Bob will win" << endl;  
           else cout << "Georgia will win" << endl;  
      }  
 }  
 int main() {  
      ios_base::sync_with_stdio(0); cin.tie(0); cout << fixed << setprecision(13);  
      solve();  
      return 0;  
 }  

POJ.2311 Cutting Game

 1.Problem

http://poj.org/problem?id=2311

2.Idea

Using Grundy number

3.Source

 int W, H;  
 int mem[220][220];  
 int grundy(int w, int h)  
 {  
      if (mem[w][h] != -1) return mem[w][h];  
      set<int> s;  
      for (int i = 2; w - i >= 2; i++) {  
           s.insert(grundy(i, h) ^ grundy(w - i, h));  
      }  
      for (int i = 2; h - i >= 2; i++) {  
           s.insert(grundy(w, i) ^ grundy(w, h - i));  
      }  
      int res = 0;  
      while (s.count(res)) res++;  
      return mem[w][h] = res;  
 }  
 void solve()  
 {  
      memset(mem, -1, sizeof mem);  
      while (scanf("%i%i", &W, &H) > 0) {  
           if (grundy(W, H) != 0) puts("WIN");  
           else puts("LOSE");  
      }  
 }  
 int main() {  
      ios_base::sync_with_stdio(0); cin.tie(0); cout << fixed << setprecision(13);  
      solve();  
      return 0;  
 }  

POJ.2348 Euclid's Game

1.Problem
http://poj.org/problem?id=2348

2.Idea
Euclid's

3.Source

 void solve()  
 {  
      while (1) {  
           int a, b;  
           cin >> a >> b;  
           if (a == 0 && b == 0) break;  
           bool f = true;  
           while (1) {  
                if (a > b) swap(a, b);  
                if (b%a == 0) break;  
                if (b - a > a) break;  
                b -= a;  
                f = !f;  
           }  
           if (f) puts("Stan wins");  
           else puts("Ollie wins");  
      }  
 }  
 int main() {  
      ios_base::sync_with_stdio(0); cin.tie(0); cout << fixed << setprecision(13);  
      solve();  
      return 0;  
 }  

POJ.2409 Let it Bead

1.Problem
http://poj.org/problem?id=2409

2.Idea
Polya's theorem.

3.Source

 int gcd(int a, int b)  
 {  
      return b == 0 ? a : gcd(b, a%b);  
 }  
 int power(int p, int n)  
 {  
      int ans = 1;  
      while (n)  
      {  
           if (n & 1)  
                ans *= p;  
           p *= p;  
           n /= 2;  
      }  
      return ans;  
 }  
 void solve()  
 {  
      while (1) {  
           int c, s, ans = 0;  
           cin >> c >> s;  
           if (c == 0 && s == 0) break;  
           for (int i = 1; i <= s; i++)  
                ans += power(c, gcd(s, i));  
           if (s & 1)   
                ans += s*power(c, s / 2 + 1);  
           else  
                ans += (power(c, s / 2 + 1) + power(c, s / 2))*(s / 2);  
           ans /= 2 * s;  
           cout << ans << endl;  
      }  
 }  

POJ.1286 Necklace of Beads

1.Problem
http://poj.org/problem?id=1286

2.Idea
Polya's theorem.

3.Source

 Int p[110], ans, n;  
 Int gcd(Int a, Int b)  
 {  
      if (!(a%b)) return b;  
      return gcd(b, a%b);  
 }  
 void solve()  
 {  
      int i, j;  
      while (1) {  
           cin >> n;  
           if (n == 0) {  
                cout << 0 << endl;  
                continue;  
           }  
           if (n == -1) return;  
           p[0] = 1;  
           for (int i = 0; i < n; i++) p[i + 1] = p[i] * 3;  
           if (!(n % 2)) ans = (n / 2) * (p[n / 2 + 1] + p[n / 2]);  
           else ans = n * p[n / 2 + 1];  
           for (int i = 1; i <= n; i++) ans += p[gcd(i, n)];  
           ans /= 2 * n;  
           cout << ans << endl;  
      }  
 }  

POJ.2407 Relatives

1.Problem
http://poj.org/problem?id=2407

2.Idea
Prime Factorization + Inclusion-exclusion principle

3.Source

 vector<int> a;  
 int n, m;  
 Int gcd(const Int a, const Int b)  
 {  
      if (b == 0) return a;  
      return gcd(b, a%b);  
 }  
 void pFac(Int H)  
 {  
      for (Int i = 2; i*i <= H; i++) {  
           int cnt = 0;  
           while (H%i == 0) {  
                cnt++;  
                H /= i;  
           }  
           if (cnt > 0) {  
                a.push_back(i);  
           }  
      }  
      if (H > 1) {  
           a.push_back(H);  
      }  
      m = a.size();  
 }  
 void solve()  
 {  
      while (1) {  
           scanf("%lld", &n);  
           if (n == 0) break;  
           a.clear();  
           pFac(n);  
           Int res = 0;  
           for (int i = 1; i < (1 << m); i++) {  
                int num = 0;  
                for (int j = i; j != 0; j >>= 1) {  
                     num += j & 1;  
                }  
                Int lcm = 1;  
                for (int j = 0; j < m; j++) {  
                     if (i >> j & 1) {  
                          lcm = lcm / gcd(lcm, a[j]) * a[j];  
                          if (lcm > n) break;  
                     }  
                }  
                if (num % 2 == 0) res -= n / lcm;  
                else res += n / lcm;  
           }  
           printf("%d\n", n - res);  
      }  
 }  

POJ.3532 Resistance

1.Problem
http://poj.org/problem?id=3532

2.Idea
See this blog.

3.Source

 typedef vector<double> vec;  
 typedef vector<vec> mat;  
 double resistor[MAX_N][MAX_N];    
 int N, M;  
 vec gauss(const mat&A, const vec&b) {  
   int n = A.size();//!!!!  
   mat B(n, vec(n + 1));  
   for (int i = 0; i < n; i++)  
     for (int j = 0; j < n; j++)B[i][j] = A[i][j];  
   for (int i = 0; i < n; i++)B[i][n] = b[i];  
   for (int i = 0; i < n; i++) {  
     int pivot = i;  
     for (int j = i; j < n; j++) {  
       if (abs(B[j][i]) > abs(B[pivot][i])) {//!!!  
         pivot = j;  
       }  
     }  
     swap(B[i], B[pivot]);  
     if (abs(B[i][i]) < EPS)return vec(); 
     for (int j = i + 1; j <= n; j++) {  
       B[i][j] /= B[i][i];  
     }  
     for (int j = 0; j < n; j++) {  
       if (i != j) {  
         for (int k = i + 1; k <= n; k++) {  
           B[j][k] -= B[j][i] * B[i][k];  
         }  
       }  
     }  
   }  
   vec x(n);  
   for (int i = 0; i < n; i++) {  
     x[i] = B[i][n];  
   }  
   return x;  
 }  
 int main() {  
   while (scanf("%d%d", &N, &M) != EOF) {  
     memset(resistor, 0, sizeof(resistor));  
     for (int i = 0; i < M; i++) {  
       int from, to;  
       double R;  
       scanf("%d%d%lf", &from, &to, &R);  
       if (R == 0)continue;  
       from--, to--;  
       resistor[from][to] += 1 / R;  
       resistor[to][from] += 1 / R;  
     }  
     for (int i = 0; i < N; i++) {  
       for (int j = 0; j < N; j++) {  
         resistor[i][j] = 1.0 / resistor[i][j];  
       }  
     }  
     mat A(N, vec(N, 0));  
     vec b(N, 0);  
     b[0] = 1.0;  
     b[N - 1] = 0.0;  
     A[0][0] = 1, A[N - 1][N - 1] = 1;  
     for (int i = 1; i < N - 1; i++) {  
       for (int j = 0; j < N; j++) {  
         if (resistor[i][j] > 0) {  
           double I = 1.0 / resistor[i][j];  
           A[i][i] -= I;  
           A[i][j] += I;  
         }  
       }  
     }  
     vec voltage = gauss(A, b);  
     double current = 0;  
     for (int i = 0; i < N; i++) {  
       if (resistor[0][i] > 0) {  
         current += (voltage[0] - voltage[i]) / resistor[0][i];  
       }  
     }  
     printf("%.2f\n", 1.0 / current);  
   }  
   return 0;  
 }  

POJ.2345 Central heating

1.Problem
http://poj.org/problem?id=2345

2.Idea
Solve the linear equation by Gaussian method.

3.Source

typedef vector vec;
typedef vector mat;
vec gauss(const mat &A, const vec &b)  
 {  
      int n = A.size();  
      mat B(n, vec(n + 1));  
      for (int i = 0; i < n; i++)  
           for (int j = 0; j < n; j++)B[i][j] = A[i][j];  
      for (int i = 0; i < n; i++)B[i][n] = b[i];  
      for (int i = 0; i < n; i++) {  
           int pivot = i;  
           for (int j = i; j < n; j++) {  
                if (B[j][i] > B[pivot][i]) {//!!!  
                     pivot = j;  
                }  
           }  
           swap(B[i], B[pivot]);  
           if (B[i][i] < EPS)return vec();  
           for (int j = 0; j < n; j++) {  
                if (i != j) {  
                     for (int k = i + 1; k <= n; k++) {  
                          B[j][k] ^= B[j][i] & B[i][k];  
                     }  
                }  
           }  
      }  
      vec x(n);  
      for (int i = 0; i < n; i++) {  
           x[i] = B[i][n];  
      }  
      return x;  
 }  
 int n;  
 void solve()  
 {  
      while (scanf("%d", &n) != EOF) {  
           vec b(n);  
           mat A(n, vec(n));  
           for (int i = 0; i < n; i++) {  
                b[i] = 1;  
           }  
           for (int i = 0; i < n; i++) {  
                while (1) {  
                     int a;  
                     scanf("%d", &a);  
                     if (a == -1) break;  
                     a--;  
                     A[a][i] = 1;  
                }  
           }  
           vec x = gauss(A, b);  
           bool flag = 0;  
           for (int i = 0; i < x.size(); i++) {  
                if (x[i]) {  
                     if (!flag) {  
                          flag = 1;  
                          printf("%d", i + 1);  
                     }  
                     else {  
                          printf(" %d", i + 1);  
                     }  
                }  
           }  
           puts("");  
      }  
 }  

Dynamic Problems list in AtCoder:

1.Linear DP / １次元状態DP
https://atcoder.jp/contests/abc004/tasks/abc004_4
https://atcoder.jp/contests/abc104/tasks/abc104_d
https://atcoder.jp/contests/abc162/tasks/abc162_f

https://atcoder.jp/contests/arc071/tasks/arc071_d

https://atcoder.jp/contests/agc031/tasks/agc031_b

https://atcoder.jp/contests/arc032/tasks/arc032_3

https://atcoder.jp/contests/dwacon2017-prelims/tasks/dwango2017qual_b

https://atcoder.jp/contests/dp/tasks/dp_a

https://atcoder.jp/contests/dp/tasks/dp_b

https://atcoder.jp/contests/dp/tasks/dp_k

https://atcoder.jp/contests/tdpc/tasks/tdpc_contest

https://atcoder.jp/contests/joi2020yo2/tasks/joi2020_yo2_c

https://atcoder.jp/contests/soundhound2018-summer-final/tasks/soundhound2018_summer_final_b

https://atcoder.jp/contests/joi2016ho/tasks/joi2016ho_a

https://atcoder.jp/contests/past202005-open/tasks/past202005_h

C - Neq Min (atcoder.jp)

B - Colorful Slimes (atcoder.jp)

D - Logical Expression (atcoder.jp)

B - スタンプラリー ２ (Collecting Stamps 2) (atcoder.jp)

C - Fair Elevator (atcoder.jp)

E - 車の乗り継ぎ (atcoder.jp)

2.Knapsack&Index DP / ナップサック・インデックスDP
https://atcoder.jp/contests/arc042/tasks/arc042_c
https://atcoder.jp/contests/abc159/tasks/abc159_f
https://atcoder.jp/contests/abc032/tasks/abc032_d
https://atcoder.jp/contests/exawizards2019/tasks/exawizards2019_d

https://atcoder.jp/contests/arc057/tasks/arc057_b

https://atcoder.jp/contests/agc020/tasks/agc020_c
https://atcoder.jp/contests/abc153/tasks/abc153_e

https://atcoder.jp/contests/abc145/tasks/abc145_e

https://atcoder.jp/contests/abc054/tasks/abc054_d

https://atcoder.jp/contests/diverta2019-2/tasks/diverta2019_2_d

https://atcoder.jp/contests/kupc2019/tasks/kupc2019_b

https://atcoder.jp/contests/dp/tasks/dp_d

https://atcoder.jp/contests/dp/tasks/dp_e

https://atcoder.jp/contests/dp/tasks/dp_m

https://atcoder.jp/contests/dp/tasks/dp_x

https://atcoder.jp/contests/tdpc/tasks/tdpc_knapsack

https://atcoder.jp/contests/joi2012yo/tasks/joi2012yo_c

https://atcoder.jp/contests/maximum-cup-2018/tasks/maximum_cup_2018_d

https://atcoder.jp/contests/joi2011ho/tasks/joi2011ho2

F - Limited Xor Subset (atcoder.jp)

F - Potion (atcoder.jp) (mod)

B - IOI饅頭（IOI Manju） (atcoder.jp)

3.Multi-dimension / DP多次元状態DP
https://atcoder.jp/contests/abc145/tasks/abc145_f
https://atcoder.jp/contests/arc067/tasks/arc067_c
https://atcoder.jp/contests/tenka1-2019-beginner/tasks/tenka1_2019_d

https://atcoder.jp/contests/abc008/tasks/abc008_4

https://atcoder.jp/contests/abc082/tasks/arc087_b

https://atcoder.jp/contests/abc113/tasks/abc113_d

https://atcoder.jp/contests/joi2013yo/tasks/joi2013yo_d

https://atcoder.jp/contests/joi2011yo/tasks/joi2011yo_d

https://atcoder.jp/contests/joi2015yo/tasks/joi2015yo_d

https://atcoder.jp/contests/joi2012yo/tasks/joi2012yo_d

https://atcoder.jp/contests/dp/tasks/dp_c

https://atcoder.jp/contests/indeednow-finala-open/tasks/indeednow_2015_finala_c

https://atcoder.jp/contests/tdpc/tasks/tdpc_semiexp

https://atcoder.jp/contests/tdpc/tasks/tdpc_cat

https://atcoder.jp/contests/tdpc/tasks/tdpc_game

https://atcoder.jp/contests/past202004-open/tasks/past202004_k (*)

https://atcoder.jp/contests/pakencamp-2019-day3/tasks/pakencamp_2019_day3_d

https://atcoder.jp/contests/wupc2012/tasks/wupc2012_4

https://atcoder.jp/contests/joi2013ho/tasks/joi2013ho2

G - 友達以上恋人以下 (atcoder.jp)

E - Union (atcoder.jp)

D - テンキー (Tenkey) (atcoder.jp)

D - Friction (atcoder.jp)

C - ビーム (atcoder.jp) (Manhattan Distance)

nile - ナイルドットコム (Nile.Com) (atcoder.jp)

4.Interval DP / 区間DP
https://atcoder.jp/contests/agc021/tasks

https://atcoder.jp/contests/dp/tasks/dp_l

https://atcoder.jp/contests/dp/tasks/dp_n

B - ケーキの切り分け２ (Cake 2) (atcoder.jp)

B - Three Coins (atcoder.jp)

5.bit DP / ビットDP
https://atcoder.jp/contests/arc056/tasks/arc056_c

https://atcoder.jp/contests/abc142/tasks/abc142_e

https://atcoder.jp/contests/abc041/tasks/abc041_d

https://atcoder.jp/contests/keyence2020/tasks/keyence2020_d

https://atcoder.jp/contests/tenka1-2014-quala/tasks/tenka1_2014_qualA_c

https://atcoder.jp/contests/past201912-open/tasks/past201912_i
https://atcoder.jp/contests/dp/tasks/dp_o

https://atcoder.jp/contests/dp/tasks/dp_u

https://atcoder.jp/contests/joi2014yo/tasks/joi2014yo_d

https://atcoder.jp/contests/joi2017yo/tasks/joi2017yo_d

E - Traveling Salesman among Aerial Cities (atcoder.jp)

G - Revenge of Traveling Salesman Problem (atcoder.jp)

E - Magical Ornament (atcoder.jp)

D - ディスクの節約 (atcoder.jp)

G - Teishoku (atcoder.jp)

F - Coprime Present (atcoder.jp)

E - Permutation (atcoder.jp)

6.Digit DP / 桁DP
https://atcoder.jp/contests/abc007/tasks/abc007_4
https://atcoder.jp/contests/dp/tasks/dp_s
https://atcoder.jp/contests/code-formula-2014-qualb/tasks/code_formula_2014_qualB_d

https://atcoder.jp/contests/arc052/tasks/arc052_d

https://atcoder.jp/contests/abc138/tasks/abc138_f

https://atcoder.jp/contests/code-festival-2014-quala/tasks/code_festival_qualA_d

https://atcoder.jp/contests/abc155/tasks/abc155_e

https://atcoder.jp/contests/dp/tasks/dp_s

https://atcoder.jp/contests/tdpc/tasks/tdpc_number

C - 半分 (atcoder.jp)

F - Valid payments (atcoder.jp)

F - Digits Paradise in Hexadecimal (atcoder.jp)

E - Digit Products (atcoder.jp)

7.DP on Trees / 木DP
- Simple
https://atcoder.jp/contests/arc028/tasks/arc028_3

https://atcoder.jp/contests/apc001/tasks/apc001_e

https://atcoder.jp/contests/agc010/tasks/agc010_c

https://atcoder.jp/contests/agc009/tasks/agc009_b

https://atcoder.jp/contests/dp/tasks/dp_p

https://atcoder.jp/contests/tdpc/tasks/tdpc_tree

E - Peddler (atcoder.jp)

C - DFS Game (atcoder.jp)

D - Teleporter (atcoder.jp)

committee - 委員会 (Committee) (atcoder.jp)

Problem - E - Codeforces (Merge technique)

- Square DP on Tree
https://atcoder.jp/contests/discovery2016-final/tasks/discovery_2016_final_c
https://atcoder.jp/contests/arc083/tasks/arc083_c

-All-round DP on Tree
https://atcoder.jp/contests/abc160/tasks/abc160_f
https://atcoder.jp/contests/dp/tasks/dp_v

https://atcoder.jp/contests/tdpc/tasks/tdpc_eel

8.Matrix Power / 行列累乗
https://atcoder.jp/contests/abc009/tasks/abc009_4
https://atcoder.jp/contests/dp/tasks/dp_r

https://atcoder.jp/contests/tdpc/tasks/tdpc_fibonacci

https://atcoder.jp/contests/tdpc/tasks/tdpc_house

D - DISCO! (atcoder.jp)

9.String DP / 文字列DP
https://atcoder.jp/contests/arc081/tasks/arc081_c
https://atcoder.jp/contests/tdpc/tasks/tdpc_lexicographical
https://atcoder.jp/contests/code-festival-2017-qualc/tasks/code_festival_2017_qualc_d

https://atcoder.jp/contests/tdpc/tasks/tdpc_string

https://atcoder.jp/contests/tdpc/tasks/tdpc_concatenation

https://atcoder.jp/contests/tdpc/tasks/tdpc_iwi

A - YahooYahooYahoo (atcoder.jp)

10.Probability DP / 確率DP

https://atcoder.jp/contests/dp/tasks/dp_i

https://atcoder.jp/contests/tdpc/tasks/tdpc_dice

https://atcoder.jp/contests/tdpc/tasks/tdpc_tournament

11.Expectation DP / 期待値DP
https://atcoder.jp/contests/dp/tasks/dp_j

https://atcoder.jp/contests/tdpc/tasks/tdpc_ball

D - increment of coins (atcoder.jp)

D - 無刻印キーボード (atcoder.jp)

F - Fork in the Road (atcoder.jp)

F - Sugoroku2 (atcoder.jp)

C - ソーシャルゲーム (atcoder.jp)

12.Classic DP / 典型的DP
  -LIS:最長増加部分列
https://atcoder.jp/contests/abc006/tasks/abc006_4
https://atcoder.jp/contests/abc038/tasks/abc038_d

https://atcoder.jp/contests/tdpc/tasks/tdpc_target

https://atcoder.jp/contests/joisc2007/tasks/joisc2007_buildi

L - 長方形 β (atcoder.jp)

F - LIS on Tree (atcoder.jp)

  -LCS:最長共通部分列

https://atcoder.jp/contests/dp/tasks/dp_f

https://atcoder.jp/contests/iroha2019-day2/tasks/iroha2019_day2_a

https://atcoder.jp/contests/joi2008ho/tasks/joi2008ho_b

E - Sequence Matching (atcoder.jp)

E - Common Subsequence (atcoder.jp)

  -Cadane's Algorithm (Consecutive SubArray):部分和

  -Hashmap (Consecutive SubArray):部分和

  -Brackets Editing: 括弧対応

B - 天下一魔力発電 (atcoder.jp)

 -2D Grid Traversal / グリッド探索

https://atcoder.jp/contests/abc175/tasks/abc175_e

https://atcoder.jp/contests/abc147/tasks/abc147_e

https://atcoder.jp/contests/agc046/tasks/agc046_b

https://atcoder.jp/contests/dp/tasks/dp_h

https://atcoder.jp/contests/tdpc/tasks/tdpc_grid

https://atcoder.jp/contests/joi2007yo/tasks/joi2007yo_f

https://atcoder.jp/contests/kupc2018/tasks/kupc2018_b

https://atcoder.jp/contests/joi2010yo/tasks/joi2010yo_e

E - Queen on Grid (atcoder.jp)

C - Infinite Grid (atcoder.jp)

C - Robot on Grid (atcoder.jp)

E - 森林伐採（Deforestation） (atcoder.jp) (Dijkstra like)

 - Cumulative Sum / 累積和

13.SOS DP / 耳DP
https://atcoder.jp/contests/yahoo-procon2019-qual/tasks/yahoo_procon2019_qual_d

14. DP + Alpha (Tricks/Data Structures)
https://atcoder.jp/contests/abc017/tasks/abc017_4
https://atcoder.jp/contests/abc158/tasks/abc158_f
https://atcoder.jp/contests/abc056/tasks/arc070_b
https://atcoder.jp/contests/abc132/tasks/abc132_f
https://atcoder.jp/contests/code-festival-2014-morning-middle/tasks/code_festival_morning_med_d
https://atcoder.jp/contests/arc097/tasks/arc097_c
https://atcoder.jp/contests/abc146/tasks/abc146_f

https://atcoder.jp/contests/dp/tasks/dp_q (BIT)

https://atcoder.jp/contests/dp/tasks/dp_z (CHull)

D - Leaping Tak (atcoder.jp) (imos)

B - Numbers on Papers (atcoder.jp) (PrefixSum, Lower_Bound)

D - Number of Multisets (atcoder.jp)

stairs - 階段 (Stairs) (atcoder.jp) (Lower_Bound)

D - Multiset Mean (atcoder.jp) (Mean Convert)

D - Shortest Path on a Line (atcoder.jp) (Segment Tree)

C - 蛍光灯 (atcoder.jp) (Segment Tree)

E - イルミネーション (Illumination) (atcoder.jp) (Imos, Multiset, Segment Tree)

15. Both Ends DP / 両端DP
https://atcoder.jp/contests/abc163/tasks/abc163_e

E - Traveler (atcoder.jp)

16.Insertion DP / 挿入DP
https://atcoder.jp/contests/dp/tasks/dp_t

17.Graph DP / グラフ関連

https://atcoder.jp/contests/agc012/tasks/agc012_b (Bubble DP)

https://atcoder.jp/contests/dp/tasks/dp_g (Longest Path)

https://atcoder.jp/contests/tdpc/tasks/tdpc_graph

E - Independence (atcoder.jp)

I - 避難計画 (atcoder.jp)

18.Combinatorics / 数え上げ
https://atcoder.jp/contests/dp/tasks/dp_y

F - チーム分け (atcoder.jp)

C - Kill/Death (atcoder.jp) (Partition Number)

E - LEQ and NEQ (atcoder.jp) (包除原理)

19.Inline DP / インラインDP

https://atcoder.jp/contests/dp/tasks/dp_w (Seg)

20.Memoization / メモ化再帰

E - 尾根 (Ridge) (atcoder.jp)

21. Binary Lifting / ダブリング

22. Math / 数学

23. Monge-DP

24. Alien-DP

25. Game Theory

D - Game in Momotetsu World (atcoder.jp)

POJ.2115 C Looooops

1.Problem
http://poj.org/problem?id=2115

2.Idea
ext gcd

3.Source

 Int a, b, c, k;  
 Int m;  
 // a x + b y = gcd(a, b)  
 Int extgcd(Int a, Int b, Int &x, Int &y) {  
      Int g = a; x = 1; y = 0;  
      if (b != 0) g = extgcd(b, a % b, y, x), y -= (a / b) * x;  
      return g;  
 }  
 void solve()  
 {  
      while (scanf("%lld%lld%lld%lld", &a, &b, &c, &k) > 0) {  
           if (a == 0 && b == 0 && c == 0 && k == 0) {  
                break;  
           }  
           Int m = (Int)1 << k, x, y;  
           Int g = extgcd(c, m, x, y);  
           if ((b - a) % g) {  
                printf("FOREVER\n");  
           }  
           else {  
                x = (x*((b - a) / g) % (m / g) + (m / g)) % (m / g);  
                printf("%lld\n", x);  
           }  
      }  
 }  
 int main() {  
      ios_base::sync_with_stdio(0); cin.tie(0); cout << fixed << setprecision(13);  
      solve();  
      return 0;  
 }  

LeetCode.1488 Avoid Flood in The City

1.Problem
https://leetcode.com/contest/weekly-contest-194/problems/avoid-flood-in-the-city/

2.Idea
set lower bound

3.Source

 class Solution {  
 public:  
      vector<int> avoidFlood(vector<int>& rains) {  
           int n = rains.size();  
           vector<int> emt, ans;  
           if (n == 0) return emt;  
           set<int> st;  
           map<int, int> mp;  
           ans.resize(n, -1);  
           for (int i = 0; i < n; i++) {  
                if (rains[i] == 0) {  
                     st.insert(i);  
                }  
                else {  
                     int cur = rains[i];  
                     if (mp.find(cur) == mp.end()) {  
                          mp[cur] = i;  
                     }  
                     else {  
                          if (st.size() == 0) return emt;  
                          set<int>::iterator it = st.lower_bound(mp[cur]);  
                          if (it == st.end()) return emt;  
                          else {  
                               ans[*it] = cur;  
                               st.erase(*it);  
                               mp[cur] = i;  
                          }  
                     }  
                }  
           }  
           for (int i = 0; i < n; i++) {  
                if (rains[i] > 0) ans[i] = -1;  
                else if (ans[i] == -1) ans[i] = 1;  
           }  
           return ans;  
      }  
 };  

POJ.1284 Primitive Roots

1.Problem
http://poj.org/problem?id=1284

2.Idea
Primitive roots, Euler function

3.Source

 int euler[N];  
 void solve()  
 {  
      for (int i = 0; i < N; i++) euler[i] = i;  
      for (int i = 2; i < N; i++) {  
           if (euler[i] == i) {  
                for (int j = i; j < N; j += i) {  
                     euler[j] = euler[j] / i * (i - 1);  
                }  
           }  
      }  
      int p;  
      while (scanf("%d", &p)>0) {  
           printf("%d\n", euler[p - 1]);  
      }  
 }  
 int main() {  
      ios_base::sync_with_stdio(0); cin.tie(0); cout << fixed << setprecision(13);  
      solve();  
      return 0;  
 }  

Codeforces.1359E Modular Stability

1.Problem
https://codeforces.com/contest/1359/problem/E

2.Idea
a1 must be a divisor of a2..aN.

3.Source

 Int fact[N], invfact[N], inv[N];  
 void init()  
 {  
      fact[0] = 1;  
      for (int i = 1; i < N; i++) {  
           fact[i] = fact[i - 1] * i % MOD;  
      }  
      inv[1] = 1;  
      for (int i = 2; i < N; i++) {  
           inv[i] = -inv[MOD%i] * (MOD / i) % MOD;  
           if (inv[i] < 0) inv[i] += MOD;  
      }  
      invfact[0] = 1;  
      for (int i = 1; i < N; i++) {  
           invfact[i] = invfact[i - 1] * inv[i] % MOD;  
      }  
 }  
 Int nCk(Int n, Int k)  
 {  
      return fact[n] * invfact[k] % MOD * invfact[n - k] % MOD;  
 }  
 Int nPk(Int n, Int k)  
 {  
      return fact[n] * invfact[n - k] % MOD;  
 }  
 Int n, k;  
 int main()  
 {  
      cin >> n >> k;  
      init();  
      Int ans = 0;  
      for (int i = 1; i <= n; i++) {  
           int num = (n / i);  
           if (num >= k) {  
                ans = (ans + nCk(num - 1, k - 1)) % MOD;  
           }  
      }  
      cout << ans << endl;  
      return 0;  
 }  

POJ.3214 Heap

1.Problem
http://poj.org/problem?id=3214

2.Idea
Post-Order traversal and LIS.

3.Source

 #include<iostream>  
 #include<cstdio>  
 #include<algorithm>  
 #include<queue>  
 #define maxn 0x7fffffff  
 using namespace std;  
 const int N=2e6;  
 int a[N];  
 int n,x=0;  
 int st[N];  
 vector<int>v;  
 void solve(int k,int& d){  
   if(2*k<=x) solve(k<<1,d);  
   if(2*k+1<=x) solve((k<<1)+1,++d);  
   v.push_back(a[k]-d);  
 }  
 int main()  
 {  
   scanf("%d",&n);  
   while(scanf("%d",&a[++x])!=EOF);  
   int d=0;  
   x--;  
   solve(1,d);  
   st[0]=-maxn;  
   int top=0;  
   for(int i=0,len=v.size();i<len;i++){  
     if(v[i]>=st[top])  
       st[++top]=v[i];  
     else{  
       int k=upper_bound(st,st+top+1,v[i])-st;  
       st[k]=v[i];  
     }  
   }  
   printf("%d\n",x-top);  
   return 0;  
 }  

POJ.1145 Tree Summing

1.Problem
http://poj.org/problem?id=1145

2.Idea
Tree pre-order traversing

3.Source

 int tree_sum(int n)  
 {  
      int ans = 0, m;  
      if (scanf(" (%d", &m)) {  
           ans = tree_sum(n - m) + tree_sum(n - m);  
           if (ans < 2) ans = 0;  
      }  
      else  
           ans = !n;  
      scanf(" )");  
      return ans;  
 }  
 int main()  
 {  
      int n;  
      while (scanf("%d", &n) != EOF) {  
           if (tree_sum(n)) printf("yes\n");  
           else printf("no\n");  
      }  
      return 0;  
 }  

POJ.3321 Apple Tree

1.Problme
http://poj.org/problem?id=3321

2.Idea
A good editorail using BIT.

3.Source

 const int MAX_N = 100009;  
 int table[MAX_N+1];  
 int BIT[MAX_N+1];  
 int tos[MAX_N+1];  
 int idx[MAX_N+1];  
 bool noApple[MAX_N+1];  
 vector<int> G[MAX_N+1];  
 int N, counter;  
 inline int readint(){  
   int ret = 0, x;  
   while(x=getchar(), !('0'<=x&&x<='9'));  
   ret = (x&15);  
   while(x=getchar(), '0'<=x&&x<='9') ret = (ret<<3) + (ret<<1) + (x&15);  
   return ret;  
 }  
 inline int sum(int n){int _R=0;for(;n;n-=n&-n)_R+=BIT[n];return _R;}  
 inline int sum(int from, int to){return sum(to-1)-sum(from-1);}  
 inline void add(int n, int x){for(;n<=N;n+=n&-n)BIT[n]+=x;}  
 inline void dfs(int v){  
      int gv = G[v].size();  
      table[v] = counter++;  
      for(int i=0; i<gv; i++){  
           if(!table[G[v][i]]) dfs(G[v][i]);  
      }  
      tos[table[v]] = counter;  
 }  
 int main(){  
      N = readint();  
      for(int i=0, x, y; i<N-1; i++){  
           x = readint(), y = readint();  
           G[x].push_back(y); G[y].push_back(x);  
      }  
      counter = 1;  
      dfs(1);  
      int M = readint();  
      for(int i=0, x; i<M; i++){  
           char op;  
           scanf(" %c ",&op);  
           x = table[readint()];  
           if(op=='Q'){  
                printf("%d\n", tos[x]-x-sum(x,tos[x]));  
           }  
           else{  
                noApple[x] = !noApple[x];  
                add(x,noApple[x]?1:-1);  
           }  
      }  
      return 0;  
 }  

POJ.1330 Nearest Common Ancestors

1.Problem
http://poj.org/problem?id=1330

2.Idea
while(x!=y) {
     if(depth x < depth y) y = parent of y;
     else  x = parent of x;
}

3.Source

 const int N = 10000;  
 vector<int> a[N]; // multiple linked list, the list of children for node i is a vector  
 int f[N], r[N]; // representations of parents and hierarchy, the parent and hierarchy for node i is f[i] and r[i]  
 void DFS(int u, int dep) // Pre-order Traversal from node u  
 {  
      r[u] = dep; // node u is at hierarchy dep  
      for (vector<int>::iterator it = a[u].begin(); it != a[u].end(); ++it)  
           DFS(*it, dep + 1);// Recursion for every child of u  
 }  
 int main()  
 {  
      int casenum, num, n, i, x, y;  
      scanf("%d", &casenum); // number of test cases  
      for (num = 0; num < casenum; num++)  
      {  
           scanf("%d", &n); // number of nodes  
           for (i = 0; i < n; i++) a[i].clear(); //initialization  
           memset(f, 255, sizeof(f));  
           for (i = 0; i < n - 1; i++)  
           {  
                scanf("%d %d", &x, &y); // edge (x, y)  
                a[x - 1].push_back(y - 1); // push node (y-1) into the list of (x - 1)’s children  
                f[y - 1] = x - 1; //node(y-1)’s parent is (x-1)  
           }  
           for (i = 0; f[i] >= 0; i++); // search the root i  
           DFS(i, 0); // calculate every nodes’ hierarchy from the root  
           scanf("%d %d", &x, &y); // a pair of nodes  
           x--; y--;  
           while (x != y) // to find the Nearest Common Ancestors  
           {  
                if (r[x]>r[y]) x = f[x];  
                else y = f[y];  
           }  
           printf("%d\n", x + 1);// Output  
      }  
      return 0;  
 }  

LeetCode.402 Remove K Digits

1.Problem
https://leetcode.com/problems/remove-k-digits/

2.Idea
Keep deleting first x such is *xy*, x > y.

3.Source

 string removeKdigits(string num, int k) {  
      string ans = "";  
      for (int i = 0; i < num.size(); i++) {  
           while (ans.size() && ans.back() > num[i] && k) {  
                ans.pop_back();  
                k--;  
           }  
           if (ans.length() || num[i] != '0')  
                ans.push_back(num[i]);  
      }  
      while (ans.size() && k) {  
           ans.pop_back();  
           k--;  
      }  
      return ans == "" ? "0" : ans;  
 }  

Codeforces.1349B Orac and Medians

1.Problem
https://codeforces.com/problemset/problem/1349/B

2.Idea
Prime Factorization

3.Source

 int n;  
 ll a[N];  
 map<ll, vector<int>> mp;  
 void pFac(ll H)  
 {  
      for (ll i = 2; i*i <= H; i++) {  
           int cnt = 0;  
           while (H%i == 0) {  
                cnt++;  
                H /= i;  
           }  
           if (cnt > 0) {  
                mp[i].push_back(cnt);  
           }  
      }  
      if (H > 1) {  
           mp[H].push_back(1);  
      }  
 }  
 ll gcd(const ll a, const ll b)  
 {  
      if (b == 0) return a;  
      return gcd(b, a%b);  
 }  
 int main() {  
      scanf("%d\n", &n);  
      for (int i = 0; i < n; i++) {  
           scanf("%d", &a[i]);  
           pFac(a[i]);  
      }  
      if (n == 2) {  
           cout << a[0] * a[1] / gcd(a[0] , a[1]) << endl;  
           return 0;  
      }  
      ll ans = 1;  
      for (auto itr = mp.begin(); itr != mp.end(); itr++) {  
           int p = itr->first;  
           vector<int> v = itr->second;  
           int k = 0;  
           if (v.size() + 2 <= n) continue;  
           sort(v.begin(), v.end());  
           if (v.size() + 1 == n) {  
                k = v[0];  
           }  
           else {  
                k = v[1];  
           }  
           int t = (int)pow(1.0 * p, 1.0 * k);  
           ans = ans * (ll)t;  
      }  
      printf("%d\n", ans);  
      return 0;  
 }  

POJ.1012 Joseph

1.Problem
http://poj.org/problem?id=1012

2.Idea
https://en.wikipedia.org/wiki/Josephus_problem

3.Source

 int Joseph[15];  
 int k;  
 int main()  
 {  
      while (scanf("%d", &k) && k) {  
           if (Joseph[k]) {  
                printf("%d\n", Joseph[k]);  
                continue;  
           }  
           int n = 2 * k, m = 1;  
           int flag[30] = { 0 };  
           for (int i = 1; i <= k; i++) {  
                flag[i] = (flag[i - 1] + m - 1) % (n - i + 1);  
                if (flag[i] < k) {  
                     i = 0;  
                     m++;  
                }  
           }  
           Joseph[k] = m;  
           printf("%d\n", m);  
      }  
      return 0;  
 }  

LeetCode.1439 Find the Kth Smallest Sum of a Matrix With Sorted Rows

1.Problem
https://leetcode.com/problems/find-the-kth-smallest-sum-of-a-matrix-with-sorted-rows/

2.Idea
Divide & Conquer. Process by 2 rows from top.

3.Source

 class Solution {  
 public:  
      int kthSmallest(vector<vector<int>>& mat, int k) {  
           vector<int> ans = mat[0];  
           int n = mat.size();  
           int m = mat[0].size();  
           for (int i = 1; i < n; i++) {  
                vector<int> tmp;  
                for (int j = 0; j < ans.size(); j++) {  
                     for (int l = 0; l < m; l++) {  
                          tmp.push_back(ans[j] + mat[i][l]);  
                     }  
                }  
                sort(tmp.begin(), tmp.end());  
                ans.clear();  
                for (int i = 0; i < min(k, (int)tmp.size()); i++) {  
         ans.push_back(tmp[i]);  
       }  
           }  
           return ans[k - 1];  
      }  
 };  

LeetCode.1438 Longest Continuous Subarray With Absolute Diff Less Than or Equal to Limit

1.Problem
https://leetcode.com/problems/longest-continuous-subarray-with-absolute-diff-less-than-or-equal-to-limit/

2.Idea
MaxMinQueue + 2 Pointers method

3.Source

 class MaxMinQueue {  
 public:  
      MaxMinQueue() {}  
      bool empty() { return elements.empty(); }  
      int size() { return elements.size(); }  
      void push(int val) {  
           elements.push(val);  
           while (!maxElements.empty() && val > maxElements.back()) maxElements.pop_back();  
           maxElements.push_back(val);  
           while (!minElements.empty() && val < minElements.back()) minElements.pop_back();  
           minElements.push_back(val);  
      }  
      int pop() {  
           int val = elements.front();  
           elements.pop();  
           if (val == maxElements.front()) maxElements.pop_front();  
           if (val == minElements.front()) minElements.pop_front();  
           return val;  
      }  
      int peekMax() {  
           return maxElements.front();  
      }  
      int peekMin() {  
           return minElements.front();  
      }  
 private:  
      queue<int> elements;  
      deque<int> maxElements;  
      deque<int> minElements;  
 };  
 class Solution {  
 public:  
      MaxMinQueue q;  
      int longestSubarray(vector<int>& nums, int limit) {  
           int n = nums.size();  
           int ans = 0;  
           int p1 = 0;  
           while (p1 < n) {  
                q.push(nums[p1]);  
                while(q.size() > 0 && (q.peekMax() - q.peekMin() > limit)) {  
                     q.pop();  
                }  
                ans = max(ans, q.size());  
                p1++;  
           }  
           return ans;  
      }  
 };  
 int main()  
 {  
      Solution obj;  
      vector<int> in = { 8,2,4,7 };  
      obj.longestSubarray(in, 4);  
      return 0;  
 }  

POJ.2413 How many Fibs?

1.Problem
http://poj.org/problem?id=2413

2.Idea
Enumerating first 500 fibs numbers.

3.Source

 string add(string a, string b)  
 {  
      if (a == "") return b;  
      if (b == "") return a;  
      if (a.length() < b.length()) swap(a, b);  
      int d = a.length() - b.length();  
      for (int i = 0; i < d; i++) {  
           b = "0" + b;  
      }  
      int car = 0;  
      int n = a.length();  
      for (int i = n - 1; i >= 0; i--) {  
           int tmp = car + a[i] + b[i] - '0' - '0';  
           a[i] = '0' + (tmp % 10);  
           car = tmp / 10;  
      }  
      if (car > 0) return "1" + a;  
      else return a;  
 }  
 bool isNotSmaller(string a, string b) // a <= b -> true  
 {  
      if (a == b) return true;  
      if (a.length() < b.length()) return true;  
      if (a.length() == b.length() && a <= b) return true;  
      return false;  
 }  
 bool isNotGreater(string a, string b) // a >= b -> true  
 {  
      if (a == b) return true;  
      if (a.length() > b.length()) return true;  
      if (a.length() == b.length() && a >= b) return true;  
      return false;  
 }  
 vector<string> fibs;  
 int main()  
 {  
      fibs.push_back("1");  
      fibs.push_back("1");  
      for (int i = 2; i < 500; i++) {  
           string tmp = add(fibs[i - 1], fibs[i - 2]);  
           fibs.push_back(tmp);  
      }  
      while (true) {  
           string a, b;  
           cin >> a >> b;  
           if (a == "0" && b == "0") break;  
           int cnt = 0;  
           for (int i = 1; i < 500; i++) {  
                if (isNotSmaller(a, fibs[i]) && isNotGreater(b, fibs[i])) cnt++;  
           }  
           cout << cnt << endl;  
      }  
      return 0;  
 }  

POJ.1598 Excuses, Excuses!

1.Problem
http://poj.org/problem?id=1598

2.Idea
KMP string matching

3.Source

 int nextarray[1000006];  
 void getnext(string s)  
 {  
      memset(nextarray, 0, sizeof(nextarray));  
      int j = -1, k = 0;  
      nextarray[0] = -1;  
      while (k < s.size())  
      {  
           if (j == -1 || s[j] == s[k])  
                nextarray[++k] = ++j;  
           else  
                j = nextarray[j];  
      }  
 }  
 int kmp(string &a, string &b)  
 {  
      int i = 0, j = 0, ans = 0;  
      while (i < a.size())  
      {  
           if (j == -1 || a[i] == b[j])  
                ++i, ++j;  
           else  
                j = nextarray[j];  
           if (j == b.size())  
                ++ans, j = nextarray[j];  
      }  
      return ans;  
 }  
 int k, e;  
 string kw[100], es[100];  
 int score[100];  
 int main()  
 {  
      int t = 1;  
      while (scanf("%d%d\n", &k, &e) != EOF) {  
           for (int i = 0; i < k; i++) {  
                cin >> kw[i];  
           }  
           for (int i = 0; i < e; i++) {  
                getline(cin, es[i]);  
                transform(es[i].begin(), es[i].end(), es[i].begin(), ::tolower);  
           }  
           memset(score, 0, sizeof score);  
           int mx = -1;  
           for (int i = 0; i < e; i++) {  
                for (int j = 0; j < k; j++) {  
                     getnext(kw[j]);  
                     score[i] += kmp(es[i], kw[j]);  
                }  
                mx = max(mx, score[i]);  
           }  
           cout << "Excuse Set #" << t++ << endl;  
           for (int i = 0; i < e; i++) {  
                if (score[i] == mx) {  
                     cout << es[i] << endl;  
                }  
           }  
           cout << endl;  
      }  
      return 0;  
 }