読者です 読者をやめる 読者になる 読者になる

はまやんはまやんはまやん

hamayanhamayan's blog

Topcoder SRM 714 問題と解説

Div1 https://community.topcoder.com/stat?c=round_overview&rd=16883

Div1 Easy. ParenthesisRemoval

()から成る文字列が与えられる。

  • ()は良い文字列
  • X,Yが良い文字列ならばXYも良い文字列
  • Xが良い文字列ならば(X)も良い文字列

最も左の"("を1つ選んで、ある1つの")"を選んで消す。
この時、")"を消した後に良い文字列が保たれるように消す。
何通りの")"の選び方があるか(mod10^9+7)。

Div1 Med. NAddOdd

f(x) := x/2(xが偶数), x+K(xが奇数)
g(x) := xを関数xに通して何回目でK以下となるか、その回数
と定めるとき、sum{x=L...R}g(x)を求めよ


以下、解説

続きを読む

競技プログラミングにおける高度なグラフ理論問題まとめ

スペクトルグラフ理論

問題化されている(のを探せた)理論

1. ラプラシアン行列の固有値0の個数は無向グラフでの連結成分の個数と同じ 解説
2. (行列木定理)ラプラシアン行列の任意の余因子は無向グラフの全域木の個数と等しい 解説
3. 隣接行列の行列式の偶奇とそのグラフの完全マッチングの総数の偶奇が一致する 解説
4. 余因子の値は逆行列から得られる 参考

サイクルの偶奇による分類

  • 偶数長サイクルだけのグラフは二部グラフである
  • 奇数長サイクルだけのグラフはcactusといい、全ての二重頂点連結成分は橋かサイクルになる 解説と問題

AtCoder Grand Contest 014 解説

http://agc014.contest.atcoder.jp

以下、解説

続きを読む

yukicoder contest 第163回 解説

http://yukicoder.me/contests/165

以下、解説

続きを読む

競技プログラミングにおけるLCA問題まとめ

LCA

  • Lowest Common Ancestor
  • 根付き木のある2頂点u,vの共通祖先で最も根から遠い頂点を高速に見つけること
  • yukicoder上でのantaさんの解説
  • アルゴリズムはいくつかある「ダブリング」「HL分解」「RMQ使用」RMQが最速っぽいけど、体感HL分解の方が早いような…
  • LCA+根からある頂点への情報(深さとかコスト和とか)を使う解法が多い

例) 頂点aから頂点bへの距離はdist(根,a) + dist(根,b) - 2*dist(根,lca(a,b))となる

  • LCAは単体では余り使われないので、これだけ知っててもしょうがなかったりするが、無いと解けない問題はある

【発展的話題】木のある頂点集合から、その集合とそのLCAからなる頂点集合を得るには

この問題で出てきた

1. dfsで木の頂点をpost-orderで番号付けする

int tout[301010], dep[301010], k;
void dfs(int cu, int pa = -1) {
    for (int to : E[cu]) if (to != pa) {
        dep[to] = dep[cu] + 1;
        dfs(to, cu);
    }
    tout[cu] = k; // ← ここ!
    k++;
}

2. 木のある頂点集合をpost-order昇順でソートするが、頂点集合に番兵として根も追加しておく

v.push_back(0);
sort(v.begin(), v.end(), [&](int a, int b) { return tout[a] < tout[b]; });

こうすることで深い所から順に処理できる。

3. 隣り合う二頂点についてLCAをとって、それを頂点集合にまとめると完成

int n = v.size();
rep(i, 0, n - 1) {
    int l = lca(v[i], v[i + 1]);
    v.push_back(l);
}
sort(v.begin(), v.end(), [&](int a, int b) { return tout[a] < tout[b]; });
v.resize(unique(v.begin(), v.end()) - v.begin());

ちなみに、この頂点集合間である頂点とその親について下から処理をしていきたい時は、以下のようにやる
(この問題ではimos方法的な手法で個数を上に伝搬させる必要があってやった)
v[i]の親はlca(v[i], v[i + 1])になるのを利用。
あと、番兵のお陰で一番最後は0となるので、これだけ別途で上手くやる。

rep(i, 0, v.size() - 1) {
    int l = lca(v[i], v[i + 1]);
    imos[l] += imos[v[i]];
    ans[imos[v[i]]] += dep[v[i]] - dep[l];
}
ans[imos[0]]++;

作った解法はこれです

HackerRank HourRank 20 問題と解説

https://www.hackerrank.com/contests/hourrank-20/challenges

Hot and Cold

4人が部屋の温度の条件を言っている。

  • AさんはC[0]度以上がいい
  • BさんはC[1]度以上がいい
  • CさんはC[2]度以下がいい
  • DさんはC[3]度以下がいい

4人の条件を満たす温度にできるか

Counting Perfect Subsequences

abcdからなる文字列がある。
この文字列の部分文字列のうち、aとbの個数が同じでcとdの個数が同じ部分文字列は何通りあるか(mod10^9+7)

Birjik and Nicole's Tree Game

N頂点の根付き木がある。
これに対して、Q個のクエリについて考える。
各クエリではK個の頂点が与えられて、その頂点のみ黒色で他は白色に塗る。
これに対して、「c[i] := その頂点を根とした部分木の黒頂点の数がi個である頂点の数」を求めて答える。

以下、解説

続きを読む

HackerRank World CodeSprint 10 問題と解説

https://www.hackerrank.com/contests/world-codesprint-10/challenges

問題

Reward Points

1回スワイプすると10ポイント貯まる。
一ヶ月に最大100ポイント貯められる。
三ヶ月間のスワイプ回数が与えられるので、何ポイント貯まったか答えよ。

Zigzag Array

N個の配列Aがある。
この配列をジグザグ配列にする為に、最小何個の要素を消せばよいか。
※ジグザグ配列 : 任意の連続する3要素を取った時に単調増加または単調減少にならない配列

Maximal AND Subsequences

N要素の配列Aがある。
ここからK個取り出してAND計算をした時の最大値とその最大値を作るK個の取り出す組合せを答えよ。

Permutation Happiness

Q個のクエリがある。
各クエリでは、N個の順列の任意の順番に対し、左右どちらかの要素がその要素よりも大きくなる(happyである)要素数が少なくともK個以上ある、順番の組合せを答えよ。

Maximum Disjoint Subtree Product

N頂点の木がある。
頂点にはコストW[i]がついている。
ここから互いに素な連結な頂点の集合を2つ取り、2つの集合それぞれについて総和を取った積の最大値を答えよ。

Node-Point Mappings

N頂点の木とN個の座標がある。
木のノードと座標を1つずつマッピングしていく。
木上でノード間に辺があるなら、xy平面上でノードに対応する座標を端点とする線分が引かれる。
適切にマッピングして、xy平面上で線分が公差しないようにせよ。

Interoffice Travel

N頂点の木がある。
N個の配列Wがある。
全ての頂点iについて、sum{j=0...N-1} W[頂点iと頂点jの距離]を求めよ。



以下、解説

続きを読む