matthew as a q.

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

根から辿る全探索

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

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全探索

競技プログラミング AtCoder

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版]　?問題解決のアルゴリズム活用力とコーディングテクニックを鍛える?

最強最速アルゴリズマー養成講座　プログラミングコンテストTopCoder攻略ガイド

最強最速アルゴリズマー養成講座　プログラミングコンテストTopCoder攻略ガイド

フェルマーの小定理を用いた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

atcoder しゃくとり法 abc

問題概要

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

解法

しゃくとり法。

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

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

提出

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

Submission #6141665 - AtCoder Beginner Contest 130

Atcoder Beginner Contest 131参加記

参加記 競技プログラミング atcoder C#

問題

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}

Diverta Programming Contest 2参加記

atcoder C#

問題総評

A

N-K

Submission #5920234 - diverta 2019 Programming Contest 2

B

一番多く存在する差の組み合わせの数を数えて、全体から引く。

Submission #5930048 - diverta 2019 Programming Contest 2

C

解説と他の方の提出を見ての理解。

ans = max - min + 残りの絶対値の和 ansを作るためには、minから0以上の値を引く操作をした結果と、maxから負の値を引く操作をした結果を出力すればよい。

Submission #5941282 - diverta 2019 Programming Contest 2

D

解説読みました。

ナップサック2回やる

未提出。

E, F

まだわかっていません。

tips

Tupleの比較

Tupleオブジェクト同士の==比較だと、同一インスタンスのときのみtrueとなる。 値が一致しているときにtrueとなるようにするには、以下のように要素同士を比較する。

var c = diffPairs.Where(e => e.Item1 == num.Item1 && e.Item2 == num.Item2);

特定の値のindexをArrayから取得する

IndexOf：最初から見ていったときに、最初に合致した値のIndexを返す LastIndexOf：最後から見ていったときに、最初に合致した値のIndexを返す

int maxIndex = Array.IndexOf(array, max);
int minIndex = Array.LastIndexOf(array, min);

出力の高速化

使えそうなので利用。 コードは以下より引用。 C#で競技プログラミングをし続ける人のためのTips - Qiita

var sw = new StreamWriter(Console.OpenStandardOutput()){AutoFlush = false};
Console.SetOut(sw);
/*何らかの出力処理*/
Console.Out.Flush();

Arrayをインデックス付きで走査

var others = numbers.Where((num, i) => i != maxIndex);

配列の絶対値の和をLinqで

int sum = array.Sum(Math.Abs)

計算量削減メモ

# 事前処理で定数時間化

 

## 題材

https://atcoder.jp/contests/abc129/tasks/abc129_d

 

## 具体的には

なりでは、各地点に対して上下左右の探索が必要で、O(HW(H+W))となり、H、Wが2000以下の正の整数のため、時間内に計算間に合わず。

 

各地点での上下左右の探索を予め実施して記録しておくことで、O(HW)に落とせる。