matthew as a q.

競技プログラミングメイン

12月前半に学んだ英語フレーズ

12/1

紅葉に感動した I was impressed with autumn leaves.

タスクを振られたら、より早めに手をつけるべき。 When you are assigned with some tasks, you should begin them at an earlier time.

期限までに終わらせてもらえますか? Can you finish your tasks on time?

たくさんの紙をシュレッダーにかけないといけないのは知っているけれども、あなたは既に30分もシュレッダーを使ってるよね。 I know that you have to shred a lot of papers, but you have been using machine for 30 minutes now. 私もすぐにこのドキュメントをシュレッダーにかける必要があるの、次の10分でミーティングに参加するために。 I also need to shred this documents immediately, so that I could attend meeting in the next 10 minutes. すぐに終わらせてもらえますか? Could you finished your tasks right away?

12/2

()内の表現の代わりに大文字の表現を使うほうがベター。 I went to (watch) SEE autumn leaves (to) IN the park near my house.

He talked WITH her in private.

I usually (hear) LISTEN to their situation first.

let off some steam: talk a lot to release their feeling of anger

ventilate: express; put into words (They just want to ventilate their feelings.)

12/8

プレゼンテーションにはこちらが適している。 This will suit for your presentation.

うるさい(の間接的な言い方) I'm getting ear pain.

12/9

(しゃべってると冠詞(article)忘れがち) He did not prepare THE agenda.

Not good: She felt anxiety. Better: She felt anxious.

(しゃべっていると途中で必要ないwould like toとかはさみがちなので注意) Could our boss and I would like to talk with you?

副詞 adverb

形容詞 adjective

12/11

The boss will describe the information of the project on our meeting

より詳細な情報を添えるべき Is Thursday, 10am or Friday, 11am good for you? Can we meet either on Wednesday afternoon at 3pm or Thursday afternoon at 4pm?

12/13

It is better to work overseas to get more salary.

高齢化が進んでる The number of the elderly is increasing every year

伝え方大事 The delivery of the message is as important as the message itself

12/16

I talked to him about my current situation and his

calm downは動詞 We should calm down ourselves

仕事が多いのに人員が足らない We are under staff.

イデアを勧めるときは、increase, decreaseする、くらいではなく、より具体的な効果を述べるべき。 またアイデア自体も具体的なアイデアを述べるべき。 We should hire 3 additional employees within this month. This will result in the reduction of 20%-30% of our tasks.

12/17

いまさらの自己紹介フレーズ I have been working in our company for about 5 years now.

賛同しかねるときのフレーズ I see what you mean but with lower corporate taxes, the government can't provide enough public services.

英語耳[改訂・新CD版] 発音ができるとリスニングができる

英語耳[改訂・新CD版] 発音ができるとリスニングができる

LAN内端末のIPを調べる

環境

リモートデスクトップ

接続するにはLAN内のプライベートIPアドレスが必要。

そこでLAN内(192.168.1.0/24)のIPアドレスすべてにpingを飛ばし、返答が返ってきた端末のIPアドレス一覧を表示する。 具体的には以下のコマンドを実行する。

echo 192.168.10.{1..254} | xargs -P256 -n1 ping -s1 -c1 -W1 | grep ttl

以下のようなイメージ。

f:id:takeknock:20191126232347p:plain

参考

LAN内で使われているIPアドレスを調べる6つの方法(Linux/Windows) | 俺的備忘録 〜なんかいろいろ〜

根から辿る全探索

木上の累積和で、根から足しこむところで詰まっていたので、そこ含めてメモとして記録。

memo

void dfs(int thisNode, int parent, vector<vector<int>>& graph, vector<int>& c) {
    for (auto nextNode : graph[thisNode]) {
        if (nextNode == parent) {
            continue;
        }
        c[nextNode] += c[thisNode];
        dfs(nextNode, thisNode, graph, c);
    }
}

int main()
{
    cin.tie(0);
    ios::sync_with_stdio(false);

    int n, q;
    cin >> n >> q;
    vector<vector<int>> graph(n, vector<int>());

    for (size_t i = 0; i < n - 1; i++)
    {
        int a, b;
        cin >> a >> b;
        a--; b--; // 0 indexed
        graph[a].emplace_back(b);
        graph[b].emplace_back(a);
    }

    vector<int> c(n, 0);
    for (size_t i = 0; i < q; i++)
    {
        int p, x;
        cin >> p >> x;
        p--; // 0 indexed

        c[p] += x;
    }

    // 根から足しこむ
    dfs(0, -1, graph, c);

    for (auto result : c) {
        cout << result << " ";
    }
    return 0;
}

bit全探索

memo

for (size_t bit = 0; bit < (1 << (s.size() - 1)); bit++)
    {
        for (size_t i = 0; i < s.size() - 1; i++)
        {
            if (bit & (1 << i)) {
                // bitが立っているとき
                // 数字の区切りでaccumulate等
            }
            else {
                // bitが立っていない場合
                // 位を挙げて今回の計算値を更新する等
            }
        }

Submission #7425849 - AtCoder Regular Contest 061 | AtCoder

参考

AtCoder 版!蟻本 (初級編) - Qiita

bit全探索について簡単にまとめる - Qiita

たくさんの数式 / Many Formulas [ARC 061, ABC 045 C] - はまやんはまやんはまやん

プログラミングコンテストチャレンジブック [第2版] ?問題解決のアルゴリズム活用力とコーディングテクニックを鍛える?

プログラミングコンテストチャレンジブック [第2版] ?問題解決のアルゴリズム活用力とコーディングテクニックを鍛える?

フェルマーの小定理を用いたmod p上の逆元

フェルマーの小定理

 p, aが互いに素な自然数のとき、  a^{p-1} \equiv 1\ \mathrm{mod}\ p

 a^{p-2} \times a \equiv 1\ \mathrm{mod}\ p

p上、a^{p-2}の逆元はa

参考

フェルマーの小定理の証明と例題 | 高校数学の美しい物語

Atcoder Beginner contest 130 E - Common Subsequence

問題概要

N個の整数列を与えられて、その部分列のうち、Kを超える部分列を数え上げる。

解法

しゃくとり法。

しゃくとり法解説記事 しゃくとり法 (尺取り法) の解説と、それを用いる問題のまとめ - Qiita

しゃくとり法のテンプレ書き方の参考

提出

今回のcur >= kのチェックは、rを進めた後、countを追加する前に実施。

Submission #6141665 - AtCoder Beginner Contest 130

Atcoder Beginner Contest 131参加記

問題

A - Security

連続してたらBad。

Submission #6056333 - AtCoder Beginner Contest 131

B - Bite Eating

味の絶対値の小さいものを食べる。

Submission #6060148 - AtCoder Beginner Contest 131

C - Anti-Division

all - (Cの倍数の数 + Dの倍数の数 - CとDの最小公倍数の倍数の数)

(かぶりが最小公倍数の倍数になることに気付かず。。。)

Submission #6103958 - AtCoder Beginner Contest 131

D - Megalomania

期限の近い順に貪欲。

Submission #6075069 - AtCoder Beginner Contest 131

納得感を持って投げるには証明したほうがよい。 (コンテスト中は見切りで投げても良いかも)

蟻本に区間スケジューリング問題が載っていて、その解法が期限近い順に貪欲だったのも、参考にした。

プログラミングコンテストチャレンジブック [第2版] ?問題解決のアルゴリズム活用力とコーディングテクニックを鍛える?

プログラミングコンテストチャレンジブック [第2版] ?問題解決のアルゴリズム活用力とコーディングテクニックを鍛える?

E - Friendships

グラフ苦手。方針たたず。。

コンテスト中

全探索ではありうる全辺の組み合わせで、ある点からある点までの最短経路を求め、条件を満たす場合に経路復元するのだと思うが、 Mを1つずつ増やして、その数でありうる辺の組み合わせを全探索する方法がわからず。。

解説読んだ後

スター(うに)グラフを起点に考えるらしい。 AtCoder ABC 131 E - Friendships (500 点) - けんちょんの競プロ精進記録

第一歩目としてグラフを解くときに手元で性質を見てみるの大事。 Submission #6105858 - AtCoder Beginner Contest 131

F - Must Be Rectangular!

たどりつけず。

解説読んだ後

drkenさんの解説をC#で焼き直しさせていただきました。 AtCoder ABC 131 F - Must Be Rectangular! (600 点) - けんちょんの競プロ精進記録

はじめてのUnionFind。はじめての二部グラフ。 Submission #6138324 - AtCoder Beginner Contest 131

2次元上の座標の問題が来たらこの問題を思い出したい。

Tips

LCMとGCDの関係

ある数a, bの最小公倍数lcmと最大公約数gcdの関係は以下となる。

 a \times b = \mathrm{lcm} \times \mathrm{gcd}