Div1 https://community.topcoder.com/stat?c=round_overview&rd=16880
問題
Div1 Easy. ConsecutiveOnes
整数N,Kがあり、以下の性質を満たす最小のmを答えよ。
1. N ≦ m
2. mを2進数にすると少なくともK個連続した1がある
Div1 https://community.topcoder.com/stat?c=round_overview&rd=16880
整数N,Kがあり、以下の性質を満たす最小のmを答えよ。
1. N ≦ m
2. mを2進数にすると少なくともK個連続した1がある
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
http://codeforces.com/contest/786
http://codeforces.com/contest/787
http://codeforces.com/contest/787/problem/A
t回目にAさんはb+ta秒に叫び、Bさんはd+tc秒後に叫ぶ。
同時に叫ぶのは最短で何秒後か。
http://codeforces.com/contest/787/problem/B
N宇宙からAさん,Bさんがそれぞれ来る。
それぞれ、どちらかが嘘つきでどちらかが正直者である。
Mグループあり、全員が嘘つきになりうるグループがあるなら"YES"、無いなら"NO"
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(最適に動かすと勝敗がつかない)のどれかを答えよ。
ゲームは以下のように進行する
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を始点として各点の最短距離を求めよ
http://codeforces.com/contest/787/problem/E
http://codeforces.com/contest/786/problem/C
N要素の配列Aがある。
これを連続する要素毎にグループ分けすることを考える。
各グループ最大でもK種類の数を含むことができるようにして分けるとして、最小何グループに分割できるか。
K=1...N全ての場合について答えよ。
http://judge.u-aizu.ac.jp/onlinejudge/contest_problem.jsp?id=RitsCamp17Day1
本物の解説はこっちです。
Day1の解説スライドです https://t.co/wa3pgp7mgS ジャッジ解はこちら https://t.co/ESSECDeZDi #rupc2017
— tubo28 (@tubo28) 2017年3月24日
以下、解説
続きを読むセグメントツリーや累積和
行列累乗
分割統治
CHT
http://codeforces.com/blog/entry/8219
http://arc070.contest.atcoder.jp/tasks/arc070_c
http://pekempey.hatenablog.com/archive/category/Convex%20Hull%20Trick
MongeDP
インラインDP
きたまさ法
(あんまり関係ないけど)遷移が限られる関係で最適化できる動的計画法問題
https://www.hackerrank.com/contests/w30/challenges/candy-replenishing-robot
カップ内のボールの数をb個とする。最初はb=N。
これについて以下の操作をT回する。
1. C[i]個のボールを取り除く。つまり、b=b-C[i](各操作で取り除けることが保証される)
2. 残ったボール数が5個未満(b < 5)ならば、カップ内のボールの数をN個にするように(N-b)個を足す
操作2で足されたボールの総和は?
https://www.hackerrank.com/contests/w30/challenges/find-the-minimum-number
2つのint,intの最小値 -> min(int, int)
3つのint,int,intの最小値 -> min(int, min(int, int))
4つのint,int,int,intの最小値 -> min(int, min(int, min(int, int)))
となるとき、Nつのintの最小値の文字列は?
https://www.hackerrank.com/contests/w30/challenges/melodious-password
N文字の以下のルールを満たす文字列を全て出力せよ。
https://www.hackerrank.com/contests/w30/challenges/poles
N本の電柱をK本にまとめる。
電柱には重さW[i]と高度X[i]がある。
ある電柱は低い高度へ動かすことしかできず、コストW[i]*dXだけかかる。
コストの総和の最小値は?
https://www.hackerrank.com/contests/w30/challenges/range-modular-queries
N個の数列Aがある。
Q個の「[left, right]の範囲でxを法にした時にyとなる要素数を答える」クエリに答える。
https://www.hackerrank.com/contests/w30/challenges/a-graph-problem
N頂点の無向グラフGがある。
この点誘導部分グラフG'のうち、(G'の三角数)÷(G'の頂点数)が最大となるグラフの点集合を出力せよ。
三角数とはグラフの点集合のうち、(a,b),(b,c),(c,a)に頂点がある三点(a,b,c)の組となる数のこと。
https://www.hackerrank.com/contests/w30/challenges/substring-queries
N個の文字列がある。
この文字列に対してQ個のF(S[x], S[y])のクエリに答えよ。
F(s, ss) := 文字列sと文字列ssでそれぞれ連続する部分文字列を取った時の最大の長さ。