ferinの競プロ帳

競プロについてのメモ

Codeforces

Codeforces Round #431 (Div. 2) D. Rooter's Song

問題ページ codeforces.com 解法 まず、各ダンサーが待つ時間をスタート位置を変えるという形で処理する。(p[i], 0)からスタートするダンサーであれば(p[i], -t[i])、(0, p[i])からスタートするダンサーであれば(-t[i], p[i])からスタートすると扱うことで全…

Codeforces Round #431 (Div. 2) C. From Y to Y

問題ページ codeforces.com 考えたこと 構成ゲーっぽい。適当な文字列についてcostがどのように求められるのか考えてみる。 まず、異なる文字種が影響し合うことはなさそう。ある文字種がN個存在するときについて考えると、costはN(N-1)/2になりそう。いくら…

Codeforces Round #431 (Div. 2) B. Tell Your World

問題ページ Problem - B - Codeforces 考えたこと 頂点を二つに分類してそれぞれの頂点群が直線上に乗っていて各直線が平行であるかを判定すればよさそう。 まず、頂点1とiを2頂点として選ぶ。この2頂点を通る直線を一本目として考える。この直線上にない頂…

Codeforces Round #431 (Div. 2) A. Odds and Ends

問題ページ Problem - A - Codeforces 考えたこと 問題を読むと普通に思い浮かばない。奇数が連続してるところで切れる(奇数個の要素になるところでしか切れないので嘘)のでその数を数えればいいという謎の思考をする。 終了30分前にhackされる。ちゃんと…

Codeforces Round #429 (Div. 2) 考察

コンテスト中に考えてたことをまとめてみることにした。解法解説とはちょっとちがうかも? 覚えてる範囲なので時間はずれてるかも? ~00:03 Aを読むと、各文字の出現頻度を数えてKと比べればよさそう。ささっと実装したらpretest通った~00:10 Bの読解が難…

Codeforces Round #429 (Div. 2) C. Leha and Function

問題ページ Problem - C - Codeforces 概要 関数 F(n, k)を次のように定める。 集合{1,2,…,n}からk要素を選んだ部分集合を全て列挙する。各部分集合の値をその部分集合の最小の要素の値とするとき、この値を平均をF(n, k)とする。 \sum F(a[i], b[i]) が最大…

Codeforces Round #429 (Div. 2) A. Generous Kefa

問題ページ Problem - A - Codeforces 概要 n個の風船をk人の子供に配る。同じ子供に同じ色の風船を二つ以上配らないように全部の風船を配ることが出来るか 解法 各色の出現数の最大がk以下ならYes, そうでないならNo

Codeforces Round #200 (Div. 1) D. Water Tree

問題ページ Problem - D - Codeforces 概要 頂点1が根のn頂点の木が与えられる。q個のクエリを処理する。 クエリ1 頂点vとvの子孫の頂点の値を1にする クエリ2 頂点vとvの先祖の頂点の値を0にする クエリ3 頂点vの値を出力する 解法 部分木に関するクエリな…

Educational Codeforces Round 6 E. New Year Tree

問題ページ Problem - E - Codeforces 概要 n要素の根が1の木が与えられる。m個のクエリを処理しろ。 クエリ1 頂点vの部分木の頂点の色をcに変更する。 クエリ2 頂点vの部分木に含まれる色の種類を求める 解法 部分木に関するクエリを処理するのにオイラーツ…

Croc Champ 2013 - Round 1 E. Copying Data

問題ページ Problem - E - Codeforces 問題概要 数列a, bが与えられる。次の2種類のクエリを処理する。 1. b[y+q] = a[x+q] ( 0 2. b[x]を表示する 解法 区間更新の遅延セグメントツリーを使う。遅延更新用の配列に更新する配列aのインデックスとの値の差を…

codeforces #261 div2 D. Pashmak and Parmida's problem

問題ページ Problem - D - Codeforces 概要 数列aが与えられる。f(l,r,x) を l 解法 まず、f(1, i, a[i])を計算する。それぞれの要素の個数を数える配列を用意して順に計算していけばよいが、a[i] b[i]>c[j]となるような(i,j)の組の個数を求めればいい。BIT…

codeforces #207 div1 A. Knight Tournament

問題ページ Problem - A - Codeforces 解法 [l_i, x_i)、(x_i、r_i]の区間でまだ誰にも負けていない兵士がいればその兵士はx_iに負けたとして更新していけばよさそう。すでに負けた、負けていないを管理するのが大変そうだったのでクエリを逆に読んで、管理…

cf #427 div2 D. Palindromic characteristics

問題ページ Problem - D - Codeforces 問題概要 k-palindromeを以下のように定義する。 文字列の左半分と右半分が空文字列ではなく一致している 左半分と右半分がともに(k-1)-palindromeである 1-palindromeは通常の回文と同様である。 文字列sが与えられる…

cf #427 div2 C. Star sky

問題ページ Problem - C - Codeforces 解法 t秒目での各星の明るさは(s[i]+t) % (c+1) で求められる。星の明るさは周期c+1で同じものが現れるのでc+1回分2次元累積和を取っておいて各クエリにO(1)で答える。同じ地点に複数の星が存在するケースがあることに…

cf #426 div2 C. The Meaningless Game

問題ページ Problem - C - Codeforces 考えたこと 色々数字をいじっていたらそれっぽい解法が思いついて投げたら通った。 gcdを求めたあと素因数分解をしたくなったが、a、bが大きな素数のときに計算時間が怖かったのでこの方針は捨てた。 立法数判定だけな…

cf #426 div2 B. The Festive Evening

問題ページ Problem - B - Codeforces 解法 各文字について最初に現れるタイミングと最後に現れるタイミングを調べてimosする。

cf #426 div2 A. The Useless Toy

問題ページ 解法 操作には周期4の周期性があるので周期性を使って判定する。

codeforces #393 div2 A, B, C

問題A 問題概要 解法 問題B 問題概要 解法 問題C 問題概要 解法 codeforces.com 問題A 問題概要 月とその月が何曜日から開始するかが与えられる。この月で1週間ごとに列が切り替わるカレンダーを作成する際、カレンダーは何列になるか。 解法 1, 3, 5, 7, 8,…

codeforces #403 Div2 A, B, C

A問題 問題概要 解法 B問題 問題概要 解法 C問題 問題概要 解法 codeforces.com A問題 問題概要 n組の靴下が袋の中に入っておりそれぞれペアごとに揃えたんすにしまいたい。袋の中から1つずつ取り出して机に並べる。そして、靴下が組になった時点でたんすに…

codeforces #402 div2 A, B, C, D

問題A 問題概要 解法 問題B 問題概要 解法 問題C 問題概要 解法 問題D 問題概要 解法 codeforces.com 問題A 問題概要 n人の生徒が属する2つのグループA, Bがある。各生徒は1から5の5段階の成績がつけられている。グループ間で生徒を交換することでそれぞれの…

Codeforces #401 A, B, C, D

A問題 問題概要 3個の箱の中にボールを隠しました。規則にもとづいて箱の位置を交換します。移動させた回数が奇数のときは左と真ん中の箱、偶数のときは右と真ん中の箱を入れ替えます。移動させた回数と最後にボールがあった場所から最初にボールがあった位…