olpheの競プロ帖

競プロ問やアルゴリズム等の考察します

Codeforces

Codeforces Round #581 (Div. 2)D-Kirk and a Binary String

問題概要 長さNの01からなる文字列がs与えられる。次の条件を満たすの文字列tを見つけたい。 長さがN 任意のについて、のLISとのLISの長さが同じ tに含まれる0の数が上二つの条件を満たす中で最大 メモ1 まず、先頭と末尾以外の文字について、文字を変更でき…

Codeforces Round #576 (Div. 1)C-Matching vs Independent Set

問題概要 3N頂点M辺の単純無向グラフがある。このグラフから次のどちらかを取り出したい。 ・互いに辺で結ばれていないサイズNの頂点集合 ・互いに頂点を共有していないサイズNの辺集合 解法 全ての辺を好きな順番で見ていき、これまでに辺集合に追加し…

Codeforces Round #450 (Div. 2) D問題

和がNで数列の全要素のGCDが1となる数列の数を求めたい。 a(n) = sum_{d|n} mu(n/d)*2^(d-1) この式で表せるらしいが全然意味が分からなかったのでメモしておく。 d | n……dはnの約数という意味。 sum_{ }……{ }内のすべての要素について何か処理をする。 mu()…

Codeforces Round #435 (Div. 2)

ABDの3完で239位 A問題 数字の数と作りたいMEX,N個の数が与えられる。数字を出現させたり消したりしてMEXを指定の数にしたい。 配列を用意して舐めてあげればよいです。 http://codeforces.com/contest/862/submission/30502250 B問題 木が与えられる。二部…

  Codeforces Round #434 (Div. 1, based on Technocup 2018 Elimination Round 1)

3完99位 Unratedめ… A問題 文字列が与えられる。その中に2種類以上の子音が3個並んでいたら切る問題。 切る回数を最小にしたい。 前から貪欲に調べていって条件を満たし次第切ればよい。 貪欲なのでO(N) http://codeforces.com/contest/860/submission/30422…

Codeforces(MemSQL Start[c]UP 3.0 - Round 1)

5完122位でした!すごい!Round2も頑張るぞ! A問題 本選に25人参加できるコンテストがあり、それらの参加者のうち何人かの予選での順位が与えられる。本選参加を辞退した人は最小で何人かな? http://codeforces.com/contest/859/submission/30389464 B問題…

CodeForces433(div1)

A 現在の時刻よりも早く出発すべきだった便のうち遅延コストのでかいものから飛ばしていく。自明。 1958->1910 こどふぉ、レート上げるの難しすぎるなあ