読者です 読者をやめる 読者になる 読者になる

pekempeyのブログ

競技プログラミングに関する話題を書いていきます。

TopCoder SRM 695 (Div. 2) Hard. BearUniqueDiameter

問題 木が与えられる。最遠点対が一意に決まるような部分木はいくつあるか。 1≦N≦300

TopCoder SRM 695 (Div. 1) Medium. BearKRoads

解法

TopCoder SRM 695 (Div. 1) Easy. BearPasswordLexic

問題 一種類の文字のみで構成された文字列を constant string と呼ぶ。 ある文字列 S の部分文字列のうち、長さ i でかつ constant string であるものの個数を x[i] とする。x が与えられるので S として考えられる辞書順最小のものを答えよ。もしないなら空…

TopCoder SRM 693 (Div. 1) BiconnectedDiv1

問題 i→i+1にコストw1[i]の辺を、i→i+2にコストw2[i]の辺を張ったグラフを考える。いくつかの辺を取り除いて作れる二重辺連結のグラフのうち、辺のコストの総和の最小値を求めよ。 二重辺連結とはどの辺を取り除いても連結なグラフのことである。 1≦n≦100

TopCoder 2016 TCO Algorithm Round 2C Easy. BearBall

問題 n個の点が与えられる。点iから点jへボールをパスしたい。ボールは真っ直ぐにしか飛ばせず、点aと点bの間に別の点があるときは点aから点bに直接ボールを投げることはできない。 点iから点jへのパスの最小回数をすべての(i,j)に対して計算し、その総和を…

TopCoder SRM 691 (Div. 1) Easy. Sunnygraphs

問題 n 頂点のグラフがある。各頂点 i に対して、 i から a[i] に辺を張る i から n に辺を張る のどちらかを選択できる。このようにして作られた 2n 通りのグラフのうち、0 と 1 が連結であるようなものの個数を求めよ。 1≦n≦50

TopCoder SRM 691 (Div. 2) Hard. Undiv2

問題 k の約数ではない 2 番目に小さい正の整数を S(k) とする。S(1)+S(2)+...+S(n) を求めよ。 1≦n≦109

TopCoder SRM 691 (Div. 2) Medium. Sunnygraphs2

問題 n 頂点のグラフがある。各頂点 i に対して、 i から a[i] に辺を張る i から n に辺を張る のどちらかを選択できる。このようにして作られた 2n 通りのグラフのうち、0..n-1 が連結であるようなものの個数を求めよ。 1≦n≦50

TopCoder Open 2016 Round 2B Easy. TriangleTriples

問題 辺の長さが 1≦a≦A, 1≦b≦B, 1≦c≦C であるような三角形 (a,b,c) の個数は何個あるか。

TCO 2016 Round 1C Hard. PrimeStrings

問題概要 整数 A を二進数で表した時、長さ L=max(1, |A|-k) である部分列のうち最も大きいものを f(A) とする。 f(A)≦y であるような x 以下の正の整数 A はいくつあるか。

TCO 2016 Round 1C Medium. ThreeProgrammers

問題概要 A,B,C で構成された文字列が与えられる。B 同士の距離が 2 以上、C 同士の距離が 3 以上になるように文字列を並び替えよ。

TopCoder SRM 688 (Div. 1) Easy. ParenthesesDiv1Easy

問題概要 括弧列が与えられる。ある区間を反転させ、さらに括弧の種類をトグルするという操作を 10 回まで行うことができる。対応のとれた括弧列に変える方法を示せ。

TopCoder SRM 688 (Div. 2) Hard. ParenthesesDiv2Hard

問題概要 括弧列 S といくつかの区間[Li, Ri]が与えられる。swap をすることにより全ての区間 [Li, Ri] に対し S[Li, Ri] が対応の取れた括弧列になるようにしたい。swap 回数の最小値を求めよ。もし不可能なら -1 を出力せよ。 なお、どの区間も重なってい…

TopCoder SRM 688 (Div. 2) Medium. ParenthesesDiv2Medium

問題概要 長さ n の括弧列が与えられる。高々 (n+1)/2 回括弧の種類をトグルして、対応の取れた括弧列に変えて欲しい。

TCO 2016 Round 1B Hard. SettingShield

三分探索したけど本当に正しいかは分からない。 問題概要 h 個の普通の区間 [left[i],right[i]] と全体を覆う特殊な区間がある。普通の区間に力 P を掛けるには P のコストが必要である。 一方で特殊な区間に力 P を掛けるには tP のコストが必要である。 位…

TCO 2016 Round 1B Medium. ReplacingDigit

問題概要 数列 A[N] が与えられる。好きな要素 A[i] を持ってきて、ある桁の数字を j に変えるという操作を各 j につき D[j] 回ずつできる。 この操作により A[n] の総和を最大化せよ。

TCO 2016 Round 1B Easy. ExploringNumbers

問題概要 数列 A[n] は以下のように定義される。 A[1]=n A[k+1]=A[k] を 10 進表記したときの各桁の数字を二乗してから足し合わせたもの この数列ではじめて素数が現れるのは何項目だろうか。もし現れないのであれば -1 と答えよ。

TopCoder SRM 687 (Div. 1) Easy. AlmostFibonacciKnapsack

問題概要 以下の漸化式で表される数列が与えられる。 A[1]=2 A[2]=3 A[n]=A[n-1]+A[n-2]-1 整数 x を異なる A[i] の和で表せるだろうか。表せるなら一例を示せ。

TopCoder SRM 687 (Div. 2) Hard. Queueing

2つほど解法を思いついたので両方書きます。 問題概要 2 つのレジがあり、レジ i には len[i] 人並んでいる。レジ i が一人を処理するのに掛かる時間は確率的に変化し、k 秒で処理する確率は (1/p)*(1-1/p)k-1 である。 レジ 1 の方が真に早くすべての人を処…

TopCoder SRM 687 (Div. 2) Medium. Quacking

問題概要 quack, quack と鳴く鳥が何匹かいて、その鳴き声を録音した結果が文字列 S として与えられる。 複数の鳥が同時に鳴いているため quqacukqauackck のように混ざった音として録音される。 録音している場所には少なくとも何匹の鳥がいるだろうか。

TopCoder SRM 686 (Div. 2) Hard. BracketSequenceDiv2

最初 Div 1 と同じ問題だと思ってスルーしそうになった。 問題概要 () で構成された文字列が与えられる。いくつかの文字を削除して作ることのできる正しい括弧列は何通りあるか。 Div 1 は文字の消去パターン数を求める問題だったのに対し、こちらは出来上が…

TopCoder SRM 686 (Div. 2) Medium. SegmentsAndPoints

問題概要 n 個の点と n 個の区間が与えられるので、区間とその区間に含まれる点をペアにする。n個すべてのペアを作ることはできるだろうか。

TopCoder SRM 686 (Div. 2) Easy. TreeAndVertex

問題概要 木が与えられる。頂点をひとつ削除したとき出来る連結成分は最大でいくつだろうか。

TopCoder SRM 686 (Div. 1) Easy. BracketSequenceDiv1

起床に失敗しました。 問題概要 ()[] で構成された文字列が与えられる。正しい括弧列にするような文字の削除方法は何通りあるだろうか。

2016 TCO Algorithm Hard. EllysTree

問題概要 木が与えられ、初期状態では Elly は頂点 0 にいる。Elly は先祖、子孫にジャンプすることができるが、過去に一度行ったことがある頂点にはジャンプできない。 Elly はすべての頂点を辿ることができるだろうか。辿ることができるなら、辿る順序のう…

2016 TCO Algorithm Medium. EllysSocks

問題文 数列 a が与えられ、P 個の独立したペアを作る。 できるだけ絶対値の最大値が小さくなるようにペアを構成したとき、差の絶対値の最大値はいくつになるだろうか。

TopCoder SRM 684 (Div. 2) Hard. Autohamil

(2016/03/10) TLE する可能性のあるコードだったため修正しました。 問題概要 状態数が N の有限オートマトンが与えられる。すべての状態に訪れるような入力が存在するか判定せよ。

TopCoder SRM 683 (Div. 2) Hard. SubtreesCounting

どことなく Codeforces を感じる。

TopCoder SRM 680 (Div. 2) Medium. BearChairs

問題概要 ※エスパーで問題を理解したので本来の問題と若干違うかもしれません。 このレストランには一直線上に椅子が並んでいる。 客 1 , ... , n が順番にやってきて、i 番目の客は atLeast[i] 番目以降の椅子に座らせなければならない。 また客同士の距離…

TopCoder SRM 680 (Div. 1) Easy. BearFair

DP 解は考えれば分かると思うので O(B) 解の方を書いておく。 SRM 680 Div1 Easy. BearFair 解法 以下の値を求める。 minEven := 偶奇を無視して要素を持ってくるとき、持ってこれる偶数の個数の最小値 maxEven := 偶奇を無視して要素を持ってくるとき、持っ…

TopCoder SRM 679 (Div. 1) Medium. RedAndBluePoints

※y 軸を下向きを正として取って説明しているので注意してください。 問題概要 2次元平面上に青い点と赤い点がいくつか存在する。 内部に赤い点を含まないように凸多角形を描くとき、多角形の内部にある青い点の個数の最大値を求めよ。ただし点や線分も多角形…

TopCoder SRM 679 (Div. 1) Hard. BagAndCards

解法 a=count[i], b=count[j], G を good number 全体を表す集合としたとき、ans[i][j] は次の値になる。 $$ a_0 \sum_{0 + j \in G} b_j + a_1 \sum_{1 + j \in G} b_j + \cdots +a_{m - 1} \sum_{m - 1 + j \in G} b_j $$ これはあらかじめ $ \sum_{i + j …

TopCoder SRM 673 (Div. 1) Easy. BearCavalry

問題概要 配列とが与えられ、の要素との要素をペアにしていく。 のペアをとするとき、になるような割り当ての方法は何通りあるか。 解法 とペアになる要素を先に決めておく。ペアの積をとしたとき、残りの配列でペアの積が未満になるような割り当て方が何通…