ferinの競プロ帳

競プロについてのメモ

Codeforces

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