Takefumi Yamamura's blog

This blog is for my memorandum about programming and English.

Happy Coding

This blog is for my memorandum

KSI vs LOGAN PAUL (YouTube Detention) youtube#2

KSI vs LOGAN PAUL (YouTube Detention)

youtu.be

words

Words, or phrase https://www.youtube.com/watch?v=fdibwIkjVZE
dirty mind いやらしい
numbnuts ばかやろうども
I'm doing me 自分のためにやってる
you do me 余計よせわてきな??
you do you the act of doing what one believes is the right decision, being oneself
detention 拘留所 いのこり部屋
at some point そのうち
i'm goona beat your ass at some point in the future そのうちおまえにいっぱいくらわせてやるよ
make up for 補う
logistics the detailed coordination of a complex operation involving many people, facilities, or supplies. 物流管理
impressionable easily influenced because of a lack of critical ability.
okay guys come on, don't you think it's wrong to teach your young impressionable fans to settle all their disagreements by punching each other in the face? わかったわかった、きいてくれ。影響をうけやすいお前らのファンに、顔面を殴って争いを解決することを教えるのは間違いじゃないかい?
lit いけてるやん
bump on a log いつもそこにいるだけの人
fluorescent light 蛍光灯の光
aight all right

How to cover up a murder youtube#1

story

Here's a some simple way of getting away with murder.

youtu.be

word list

Words, or phrase Translation
the clock is ticking used for saying that someone must do something quickly because there will soon be no more time left
throw the cops off 警察を混乱させる
lame ださい A characteristic describing someone who is just not cool
tie up any loose ends 仕上げる 細々としたことを片付ける
frame up the act of framing someone, that is, providing false evidence or false testimony in order to falsely prove someone guilty of a crime. 罪をきせる
slammer 刑務所
turn yourself in 自白する
tamper with the evidence 証拠を改ざんする
fatality 偶然の死 an occurrence of death by accident, in war, or from disease.
ampit haire 脇毛

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 高橋君と禁断の書

問題

arc029.contest.atcoder.jp

解き方

二分探索するまえに(A ≤ C かつ B ≤ D)もしくは(A ≤ D かつ B ≤ C)を満たせば"YES"。 満たさなければ、角度で二分探索する。 このとき、中の本を傾けて行って、傾けたときの片方の長さのみに注目して2分探索する。 指定回数分二分探索して見つからなかったら"NO"。

計算量

二分探索の繰り返し回数をkとすると O(kn)

code