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

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 参考2
    • ラプラシアン行列の固有値0の個数は無向グラフでの連結成分の個数と同じ 解説
    • 行列木定理（ラプラシアン行列の任意の余因子は無向グラフの全域木の個数と等しい） 解説
    • 隣接行列の行列式の偶奇とそのグラフの完全マッチングの総数の偶奇が一致する 解説
  • ケイリーの公式 参考
    • n頂点のラベル付きの木の総数はn^(n-2)通りある
    • ラベル付きなので、木の形の組合せと木の頂点に数を割り当てる組合せを全て考慮した組み合わせ数
    • ケイリーの定理の問題は「行列木定理+多項式補間」の組合せでも解けるっぽい（かなり不確定）（HEのColorful Spanning Treesはこの組合せなのでケイリーの定理っぽくやっても解ける？）（Stranger Treesには「行列木定理+多項式補間」解法が存在する）

定理と問題

以下、工事中（たぶん一生工事中）

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

競技プログラミング

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

問題

AOJ Lowest Common Ancestor
ABC014 D.閉路
yukicoder No.898 tri-βutree 解説
yukicoder No.386 貪欲な領主
yukicoder No.901 K-ary εxtrεεmε 解説
JOI 国のお祭り事情 見応えのある解説
HR Bananas Multiplier (Hard)

【発展的話題】LCA木

  • LCA木、auxiliary tree
    • 木のある頂点集合から、その集合とそのLCAからなる頂点集合を得る方法がある
    • 木のある頂点集合の個数がKであれば、O(K)で構築でき、得られる頂点集合の個数もO(K)
  • 構築方法

1. dfsで木の頂点をpre-orderで番号付けする(オイラーツアー)
2. 木のある頂点集合をpre-order昇順でソート
3. 隣接する2頂点についてLCAを取って、それを頂点集合に追加する
4. (辺も構築するなら)追加された頂点も含めて、再度pre-order昇順でソートし、隣接する頂点(i,i+1)でLCAを取ると、LCAとi+1の間に辺を作れる

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の距離]を求めよ。



以下、解説

続きを読む