leetcode 718. Maximum Length of Repeated Subarray
Question
Given two integer arrays A and B, return the maximum length of an subarray that appears in both arrays. https://leetcode.com/problems/maximum-length-of-repeated-subarray/
Code
class Solution { public: int findLength(vector<int>& A, vector<int>& B) { // dp[i][j] will be the maximum length of subarray which ends with A[i] and B[j] // ex) // A: [1,2,3,2,1] // B: [3,2,1,4,7] // dp [4][1] = 2; // if A[i+1] == B[j+1] dp[i+1][j+1] = dp[i][j] + 1 // else dp[i+1][j+1] = 0; // Time O(mn); // Space O(mn); vector<vector<int> > dp = vector<vector<int> >(A.size() + 1, vector<int>(B.size() + 1, 0)); int ans = 0; for(int i = 0; i < A.size(); i++) { for(int j = 0; j < B.size(); j++) { if(A[i] == B[j]) { if(i - 1 < 0 || j - 1 < 0 ) { dp[i][j] = 1; } else { dp[i][j] = dp[i-1][j-1] + 1; } } else { dp[i][j] = 0; } ans = max(dp[i][j], ans); } } return ans; } };
AtCoder Beginner Contest 010 D - 浮気予防
problem
D: 浮気予防 - AtCoder Beginner Contest 010 | AtCoder
how to solve
This problem can be reduced to the maximum matching problems. This means that Ford-Fulkerson is among the good way to solve this problem.We have to take care that this graph is undirected so we have to prepare two edges for solving flow problems. The following link is very helpful to understand.
http://hidollara.hatenablog.com/entry/2017/07/29/165951
code
#include <iostream> #include <vector> using namespace std; #define INF (1<<15) class Solver { private: int n, g, e; vector<vector<int> > adj; vector<bool> visited; public: Solver(){ cin >> n >> g >> e; adj = vector<vector<int> >(n + 1, vector<int>(n + 1, 0)); for (int i = 0; i < g; ++i) { int mark; cin >> mark; adj[mark][n] = 1; // adj[n][mark] = 1; } for (int i = 0; i < e; ++i) { int a, b; cin >> a >> b; adj[a][b] = 1; adj[b][a] = 1; } } int dfs(int from, int goal, int min_cost) { if(from == goal) return min_cost; visited[from] = true; for (int to = 0; to < n + 1; ++to) { if(adj[from][to] == 0 || visited[to]) continue; int flow = dfs(to, goal, min(min_cost, adj[from][to])); if(flow != 0) { adj[from][to] -= flow; adj[to][from] += flow; return flow; } } return 0; } void exec(){ int sum_flow = 0; while(true) { visited = vector<bool>(n + 1, false); int flow = dfs(0, n, INF); if(flow == 0) { cout << sum_flow << endl; return; } sum_flow += flow; } } }; int main(){ Solver s = Solver(); s.exec(); }
Network Flow - Maximum Flow
problem
Maximum Flow | Aizu Online Judge
code
#include <iostream> #include <vector> #define INF (1<<15) using namespace std; struct edge{ int to; int cap; int rev_id; }; class FordFulkerson { private: vector<vector<edge> > adj; int v; int e; vector<bool> visited; public: FordFulkerson() { cin >> v; cin >> e; adj.resize(v); for (int i = 0; i < e; ++i) { int u; int v; int c; cin >> u >> v >> c; adj[u].push_back((edge){v, c, adj[v].size()}); adj[v].push_back((edge){u, 0, adj[u].size() - 1}); } } int dfs(int from, int goal, int flow) { if(from == goal) return flow; visited[from] = true; for (int i = 0; i < adj[from].size(); ++i) { edge &e = adj[from][i]; if(!visited[e.to] && e.cap > 0) { int d = dfs(e.to, goal, min(e.cap, flow)); if(d > 0) { adj[from][i].cap -= d; adj[e.to][e.rev_id].cap += d; return d; } } } return 0; } void exec() { int flow_sum = 0; while(true) { visited = vector<bool>(v, false); int flow = dfs(0, v - 1, INF); if(flow == 0) { cout << flow_sum << endl; return; } flow_sum += flow; } } }; int main() { FordFulkerson ff = FordFulkerson(); ff.exec(); }
Family Guy season9 1-2 And Then There Were Fewer
Plot
One day, Peter who is a father like a kind of homer in Simpsons is invited to the party by an anonymous guest. Also other families in his town are invited to this. When the party is about to started, one of the guest is shooted by someone.
vocabulary list
| word | explanation | example |
|---|---|---|
| let up | 嵐がやむ | before the storms lets up |
| skin(v) | 動物の皮を剥ぐ | |
| unconscious | 無意識 | |
| hot chicks | 魅力的な女性 | |
| gasp | はっという | |
| stay up | 遅くまで起きる or どどまる | |
| huddle up | to gather or crowd together in a close mass | |
| scrutinize | examine or inspect closely and thoroughly. | |
| nocturnal | 夜行性の | |
| intruder | 侵入者 | |
| crawl | はう、よつんばいになってはう | |
| podunk | A piece of shit, redneck, small-town | |
| slippery | difficult to hold firmly or stand on because it is smooth, wet, or slimy.つるつる、するする | 追いかけてる人がなかなか捕まらない時とかにつかう |
| i’m managing | なんとかやってるよ(how are you?とかの返し) | |
| for the time being | しばらくね | |
| He dumped me | 彼は私を振ったの | |
| crumble | 崩れる | I watched my career and my love life crumble |
| seize | にぎる つかまえる | チャンスをつかんだ I seized the moment |
| seduce | 誘惑する | |
| reel him | つる | |
| pay her off | 彼女に復讐する | |
| instill | 思い込ませる | |
| hysterical | ヒステリックに |
CUDA まとめ
CUDAのメモリについて
グローバルメモリはGPU上どこからでも見えるがメモリアドレスが低速なメモリ
シェアードメモリは同一ブロックからしかみえないが高速に読み書きができるメモリ
コンスタントメモリは読み込み専用だがグラオーバルメモリと同様のスレッドから見える高速なメモリ。
CUDAの性能劣化をひきおこす特徴
warp divergence
実際のcudaスレッドの処理は連続したIDを持つ32スレッドを1グループ(ワープと呼ぶ)とし、ワープ単位で同一命令を実行するGPUの特徴により発生するオーバーヘッドである。同一ワープ内のスレッドが異なる命令を実行することをワープダイバージェンスと呼ぶ。
coalesed memory access
スレッドIDとアクセスするメモリアドレスが不連続な場合に負荷が発生する。特に連続したIDを持つスレッドが連続したメモリ番地へアクセスすることで、高速なデータ転送が実行できる。
AtCoder Regular Contest 029 B 高橋君と禁断の書
問題
解き方
二分探索するまえに(A ≤ C かつ B ≤ D)もしくは(A ≤ D かつ B ≤ C)を満たせば"YES"。 満たさなければ、角度で二分探索する。 このとき、中の本を傾けて行って、傾けたときの片方の長さのみに注目して2分探索する。 指定回数分二分探索して見つからなかったら"NO"。
計算量
二分探索の繰り返し回数をkとすると O(kn)
