Codeforces

Codeforces Round #344 (Div. 2): D. Messenger

https://codeforces.com/problemset/problem/631/D 問題概要 文字列S, Tが与えられる。SがTを部分文字列として何個含むか求めよ。ただしS, Tは(回数, 文字)というタプルの列として与えられる。これはその文字が何回連続するかを表した形式で、例えば(3, a)(2…

Codeforces Round #259 (Div. 1): B. Little Pony and Harmony Chest

https://codeforces.com/problemset/problem/453/B 問題概要 N要素の正整数列Aが与えられる。すべての相異なる2要素が互いに素であるようなN要素の正整数列であって、Σ(abs(A[i]-B[i])) が最小となるような数列Bを構成せよ。 N <= 100 Ai <= 30 解法 相異な…

Codeforces Round #562 (Div. 1) : B. Good Triple

https://codeforces.com/contest/1168/problem/B 問題概要 各文字が0または1のどちらかからなる長さNの文字列Sが与えられる。1 <= l <= r <= N を満たす整数の組(l, r)のうち、Sの区間[l, r]の中に同じ文字が3文字以上等間隔で並んでいるものの数を求めよ。 …

Educational Codeforces Round 64: D. 0-1-Tree

https://codeforces.com/problemset/problem/1156/D 問題概要 N頂点の木が与えられる。木の各辺は0または1のコストを持つ。単純パスで、かつ辺が「0個以上の0コスト辺」→「0個以上の1コスト辺」の順序で並んでいるパスをvalidと呼ぶ。頂点x->yへの単純パスが…

Codeforces Hello 2019: D. Makoto and a Blackboard

https://codeforces.com/contest/1097/problem/D 問題概要 整数N, Kが与えられる。Nの約数のうちひとつを等確率で選び、それでNを割る、という操作をK回繰り返すとき、最終的なNの値の期待値を求めよ。 N <= 1015 K <= 104 解法 Nの約数の数は最大ケースで30…

Codeforces Round #499 (Div. 1): D. Mars rover

http://codeforces.com/contest/1010/problem/D 問題概要 N頂点の根付き木が与えられる。すべての葉にはあらかじめ1か0の入力が与えられており、葉以外の頂点はすべて「子から来たビットを入力として論理演算をし、その出力を親に送る」機能を持っている。演…

Codeforces Round #433 Div.2 D / Div.1 B - Jury Meeting

http://codeforces.com/contest/854/problem/D 問題概要 (N+1)個の町があり、1~Nの町に一人ずつ人が住んでいる。また 町0 → 町(1~Nのどれか) に飛ぶ飛行機と、町(1~Nのどれか) → 町0 に飛ぶ飛行機の2種類がある。飛行機を使って1~Nの町の人を全員町0に呼…

Codeforces Round #432 Div.2 E / Div.1 C - Arpa and a game with Mojtaba

http://codeforces.com/contest/850/problem/C 問題概要 先手と後手に分かれて以下のような2人ゲームを行う。まずN要素の数列Aが与えられる。プレイヤーは手番ごとに素数pと正整数kを選び、数列のうちpkで割り切れる要素をpkで割る。ただしどの要素も割り切…

Codeforces Round #432 Div.2 D / Div.1 B - Arpa and a list of numbers

http://codeforces.com/contest/850/problem/B 問題概要 N要素の数列Aが与えられる。以下の操作を好きなだけ繰り返して、数列の全要素のGCDが1でなくなるようにしたい。目的を達成する最小のコストを求めよ。 操作1. コストxで数列から任意の1要素を取り除く…

Codeforces Round #432 Div.2 C / Div.1 A - Five Dimensional Points

http://codeforces.com/contest/850/problem/A 問題概要 5次元空間上のN個点が与えられる。この中のある点aについて、異なる点b, cを取ってきたときにab, acのなす角が90度未満となるb, cが存在するとき、aを悪い点と呼び、そうでない場合良い点と呼ぶ。良い…

Codeforces Round #429 Div.2 D / Div.1 B - Leha and another game about graph

http://codeforces.com/contest/840/problem/B 問題概要 N頂点M辺の連結な無向グラフGと、N要素の数列Dが与えられる。数列Dの要素は-1, 0, 1のいずれかである。Gから任意の辺集合を選び、選ばれた辺以外を削除するとき、以下の条件を満たすことができるか判…

Codeforces Round #428 Div.2 D - Winter is here

http://codeforces.com/contest/839/problem/D 問題概要 N要素の数列Aが与えられる。Aの部分集合Sに対して、strength(S) = |S|・gcd(S) と定義する。gcd(S) > 1 なるすべての部分集合Sに対するstrengthの総和を求めよ。 N <= 2 * 105, max(A) <= 106 解法 一…

Codeforces Round #427 Div. 2 E - The penguin's game

http://codeforces.com/contest/835/problem/E 問題概要 N要素の数列があり、そのうち2要素はYで残りの要素はXである。質問クエリとして数列のインデックスの部分集合を指定すると、それらの値のXORを知ることができる。19回以内の質問クエリで値Yを持つ2要…

Codeforces Round #427 Div. 2 D - Palindromic characteristics

http://codeforces.com/problemset/problem/835/D 問題概要 ある文字列に対して以下のようにk-palindromesが定義される。 文字列が回文ならば、その文字列は 1-palindrome である k > 1 のとき、文字列の左半分と右半分が等しく、かつ左半分が (k-1)-palindr…