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

hamayanhamayan's blog

CSAcademy #22 問題と解説

競技プログラミング

https://csacademy.com/contest/round-22/

問題

Triangle Count

N本の棒があり、長さが分かっている。
この中から任意の3本を選んで三角形が作れる組合せは何通り？

Frequency Exception

N要素の配列がある。
この中で配列の中に現れる回数が他と異なる要素が1つある。
それを探せ。

Black Shapes

H(=N)行W(=M)列のマス目がある。
それぞれ白(=0),黒(=1)で塗られている。
マス目の中の白マスをどれか1つだけ黒に塗って、黒を最も多く隣接させる。
最大、何個黒を隣接させられるか。

Distinct Rotations

0と1と?から成る文字列がある。
?に0か1を入れて回転させた時の周期が最小になるものを答えよ。
例）010010ならば 010010 -> 100100 -> 001001 -> 010010なので周期3

Limited Swaps

要素数Nの配列Aが与えられる。
この配列の隣接している要素を最大K回スワップして、辞書順最大となる配列A'は？

以下、解説

続きを読む

Educational Codeforces Round 18 問題と解説

競技プログラミング

http://codeforces.com/contest/792

問題

A. New Bus Route

N点の座標が与えられる。
任意の2つの座標の最短距離とその最短距離となる2つの座標のペアの組合せを求めよ。

B. Counting-out Rhyme

N人が円状に昇順で並んでいる。最初リーダーを1さんとし、以下の操作をK回行う。
1. 現在のリーダーの次のK番目の人を削除する
2. 削除した次の人をリーダーにする
i回目に削除した人をすべて答えよ。

C. Divide by Three

ある数Nが与えられる。
その数の任意の位を削除することでリーディング0でない3の倍数を作る。
削除すべき位を最小化したときの答えは？
3の倍数にできないならば-1

D. Paths in a Complete Binary Tree

N頂点の完全二分木がある。
この木は「左のノードが全てラベル付けされたら自分をラベル付けして右のノードをラベル付けする」
というルールで頂点が割り当てられている。
これに対し、Q個の以下のクエリを答えよ

  • 初期頂点uがある
  • 操作Sがあり、'U'は親ノードへの移動、'L'は左側の子ノードへの移動、'R'は右側の子ノードへの移動を指す
  • 移動後の頂点を答えよ
E. Colored Balls

N種類の色の箱がある。
各箱には同色のボールがA[i]個入っている。
以下の条件をみたすようにボールをグループ分けするときのグループ数の最小値は？
1. 1つのグループには1色のボールしか入らない
2. 任意の2つのグループのサイズの差は1以下である

以下、解説

続きを読む

Topcoder SRM 711 問題と解説

競技プログラミング

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

問題

Div1 Easy. ConsecutiveOnes

整数N,Kがあり、以下の性質を満たす最小のmを答えよ。
1. N ≦ m
2. mを２進数にすると少なくともK個連続した1がある

Div1 Med. OrderedProduct

素数を昇順で格納した配列Pがある。P[0]=2,P[1]=3,...
個数Nの配列Aが与えられる。
X = P[0]^A[0] * P[1]^A[1] * ... * P[N-1]^A[N-1]とする。
Xを因数分解して列とするときの組合せは何通りか(mod10^9+7)
例）X=12なら(2,6),(3,4),(4,3),(6,2)の4通り

以下、解説

続きを読む

競技プログラミングにおける文字列アルゴリズム問題まとめ [ローリングハッシュ,Suffix Array,LCP,KMP,Aho-Corasick,Z-algorithm,Palindromic Tree, Manacher, Suffix Tree]

競技プログラミング

文字列アルゴリズム

  • Suffix Array
    • 接尾辞配列
    • 全文探索、パターンマッチングに使える
  • LCP
    • ある2つの文字列について接頭語がどれだけ一致しているか
    • 複数文字列があるとき、ある任意の2つのLCPを求めたい場合は、「1.文字列を昇順ソート」「2.隣り合う文字列でLCPを計算」「3.ある任意の2つの間のLCPの中で最小のLCPがその2つの文字列のLCP」参考
  • Trie, Aho-Corasick
    • Trie : 複数文字列から作った木
    • Aho-Corasick法 : 複数文字列のマッチングアルゴリズム 資料
    • Aho-Corasick法で作った木に対してDPする典型がある
  • Z-algorithm
    • z[i] := S[0..]とS[i..]の文字列での共通文字数
    • O(N)で構築できる
    • 覚書
    • 動的に作れるみたい 問題 実装？
  • Palindromic Tree, eertree
    • 回文にまつわる色々なことができる木
    • 数え上げ問題に使える。（最大最小でも使える？）
    • 参考1 参考2 参考3
  • Suffix Automaton
  • Manacher
    • 参考
    • A[i] := i番目を中心としたときの最長回分の半径。半径とは(全長+1)/2のこと
    • O(|S|)

問題

SuffixArray,LCP

（未解決）
https://kimiyuki.net/categories/suffix-array/
http://kenkoooo.hatenablog.com/entry/2016/11/17/201707
http://www.prefield.com/algorithm/string/suffix_array.html
　
KMP,Aho-Corasick

KMP法で最短周期を取得する問題

Trie

Trie上でのdfs

Aho-Corasickで作った木上でのDP

Palindromic Tree

Manacher

Suffix Tree

z-algorithm

Codeforces Round #406 問題と解説

競技プログラミング

http://codeforces.com/contest/786
http://codeforces.com/contest/787

A. The Monster

http://codeforces.com/contest/787/problem/A
t回目にAさんはb+ta秒に叫び、Bさんはd+tc秒後に叫ぶ。
同時に叫ぶのは最短で何秒後か。

B. Not Afraid

http://codeforces.com/contest/787/problem/B
N宇宙からAさん,Bさんがそれぞれ来る。
それぞれ、どちらかが嘘つきでどちらかが正直者である。
Mグループあり、全員が嘘つきになりうるグループがあるなら"YES"、無いなら"NO"

C. Berzerk / A. Berzerk

http://codeforces.com/contest/787/problem/C
http://codeforces.com/contest/786/problem/A
2人でゲームをする。
それぞれ使えるカードが決まっており何回でも使える。
0～N-1個の数字が昇順に円状に並んでいる。
AさんBさんのどちらかが先攻で、初期位置が1～N-1の全てのパターンについて、先攻がWin, Lose, Loop（最適に動かすと勝敗がつかない）のどれかを答えよ。
ゲームは以下のように進行する

  • 位置がxであるとする
  • (自分の手持ちのカードのある数 + x) % Nへ移動可能
  • x==0へ移動させることが出来たプレイヤーが勝ち
D. Legacy / B. Legacy

http://codeforces.com/contest/787/problem/D
http://codeforces.com/contest/786/problem/B
1～Nの頂点があり、以下のクエリに従って有向辺を付けていく
1. 頂点vから頂点uへコストw
2. 頂点vから頂点[l,r]へコストw
3. 頂点[l,r]から頂点vへコストw
頂点Sを始点として各点の最短距離を求めよ

E. Till I Collapse / C. Till I Collapse

http://codeforces.com/contest/787/problem/E
http://codeforces.com/contest/786/problem/C
N要素の配列Aがある。
これを連続する要素毎にグループ分けすることを考える。
各グループ最大でもK種類の数を含むことができるようにして分けるとして、最小何グループに分割できるか。
K=1...N全ての場合について答えよ。

続きを読む