Codeforces

AIM Tech Round 4 (Div. 1) D. Dynamic Shortest Path

問題 http://codeforces.com/contest/843/problem/D 解法 最初にダイクストラで距離を求めておき、各クエリごとにダイクストラで追加で増えた分の距離を計算して加算していく。各クエリごとに距離は 1 しか増えないので、キューを距離の数だけ用意すれば、ク…

Codeforces Round #411 (Div. 1) C. Ice cream coloring

問題 http://codeforces.com/contest/804/problem/Cn 頂点のツリー T と m 種類のアイスクリームがあります。T の各頂点はアイスクリームの集合をもっています。あるアイスクリーム i をもつ頂点同士は、連結なサブグラフになっています。m 頂点の無向重みな…

Codeforces Round #402 (Div. 2) E. Bitwise Formula

# 問題http://codeforces.com/contest/779/problem/EMビットからなる変数がN個与えられます。各変数は、代入か、異なる2つの変数の AND OR XOR のいずれかの結果です。すべての変数の合計値が最小になるような変数 '?' と最大になるような変数 '?' を求めて…

Codeforces Round #397 E. Tree Folding

問題 Problem - E - Codeforcesツリーがあって、ある頂点から同じ長さの枝が2本出ている時、そのうち1本を取り除くことが出来ます。この操作を繰り返してツリーを直線に出来る場合、その最小の長さを出力してください。 解法 葉から登っていき、自分より下方…

8VC Venture Cup 2017 - Elimination Round F. PolandBall and Gifts

問題 http://codeforces.com/contest/755/problem/Fプレゼント交換をします。iさんはp[i]さんにプレゼントを渡します。複数の人が同じ人にプレゼントを渡すことはありません。K人がプレゼントを忘れました。プレゼントを忘れた人はプレゼントを受け取れませ…

Codecraft-17 and Codeforces Round #391 (Div. 1 + Div. 2, combined) D. Felicity's Big Secret Revealed

問題 http://codeforces.com/contest/757/problem/D0と1からなるn文字の文字列が与えられます。この文字列の好きな位置(先頭や末尾も含むN+1個)に仕切りを入れることができます。仕切りはいくつ入れても構いませんが、同じ位置に2個以上入れることはできま…

Codeforces Round #390 (Div. 2) D. Fedor and coupons

問題 http://codeforces.com/contest/754/problem/D[l, r] のような範囲の組が N 個あります。このうちK個を選び、K個すべてが重なる範囲を最大にしたいです。最大値と、その時選ぶ範囲のidを出力してください。 解法 非想定解法っぽい Treap コード import …

2016-2017 ACM-ICPC Southwestern European Regional F Performance Review

問題 Attachments - 2016-2017 ACM-ICPC Southwestern European Regional Programming Contest (SWERC 2016) - Codeforces根つき木があって、各頂点にはランクとコストが定められています。各頂点について、その頂点の子孫であり、かつ、その頂点のランク未…

Codeforces Round #385 (Div. 1) B. Hongcow's Game

問題 http://codeforces.com/contest/744/problem/Bn x n の行列があります。行列の要素は全て非負整数で、対角成分はすべて0です。この行列に対して、n以下の自然数の集合Sをクエリとして投げると、各行についてとなる x 列目の要素のうち最小のものを返し…

Codeforces Round #381 (Div. 2) D. Alyona and a tree

問題 http://codeforces.com/contest/740/problem/Dツリーがあり、頂点1が根です。各頂点 u には数字が書き込まれています。各頂点 v について、v の部分木に含まれ、かつ を満たす頂点uの数を出力してください。 解法 DFS で辺の重みを BIT に持ちながら潜…

Codeforces Round #381 (Div. 2) E. Alyona and towers

問題 http://codeforces.com/contest/740/problem/EN 個の非負の数列{a}があります。クエリが M 個あり、各クエリでは、l 番目から r 番目までの数字にそれぞれ v を足し、数列に含まれる最大の hill の幅を答えてください。 ただし、hill とはを満たす部分…

Codeforces Round #379 (Div. 2) F. Anton and School

問題 http://codeforces.com/contest/734/problem/F 解法 Fはb_i+c_iを足すとなんとa_i*n+(sum a_j)になりそこからがんばる。あと検証もちゃんとする— 有為 (@uwitenpen) 2016年11月15日 コード import java.io.IOException; import java.io.InputStream; im…

Codeforces Round #379 (Div. 2) E. Anton and Tree

問題 http://codeforces.com/problemset/problem/734/EN頂点のツリーがあり、各頂点は白か黒で塗られています。1回の操作で同じ色の連結成分の色を全て塗り替えることができます。ツリーを全て同じ色にするための最小の操作回数を求めてください。 解法 連結…

Codeforces Round #364 (Div. 2) E. Connecting Universities

問題 http://codeforces.com/contest/701/problem/EN 頂点のツリー状に 2K 個の大学があります。これらの大学を K このペアに分割します。ペアとなっている大学間の距離の合計が最大となるようにペアを作るとき、その最大値を答えてください。 解法 辺 (v, p…

Codeforces Round #378 (Div. 2) E. Sleep in Class

問題 http://codeforces.com/contest/733/problem/EN 階建ての建物の中にいます。各階には 'U' または 'D' の文字が書かれています。 i 階にいて U と書かれているときは i+1 階へ、D と書かれているときは i-1 階へ移動します。移動すると、直前にいた階の…

Codeforces Round #377 (Div. 2) F. Tourist Reform

問題 http://codeforces.com/contest/732/problem/FN 頂点 M 辺の連結な無向グラフが与えられます。すべての辺の向きをそれぞれどちらか 1 方向に限定した時に頂点 i から到達可能な頂点の数を mi とします。mi の最小値を最大化するとき、その値と、その時…

Codeforces Round #377 (Div. 2) E. Sockets

問題 Problem - 732E - CodeforcesN 台のパソコンがあり、パソコン i の消費電力は Pi です。ソケットが M 個あり、ソケット j の供給電力は Sj です、消費電力と供給電力が等しいとき、パソコンをソケットに接続できます。1 つのソケットには 1 台のパソコ…

Intel Code Challenge Elimination Round D. Generating Sets

問題 Problem - D - Codeforces相異なる自然数を N 個もった集合 X があります。X の各要素 に対して、以下の操作を行うことができます。 を X から取り除き、 を X に加える。 を X から取り除き、 を X に加える。 集合 X に何回か操作を加えて Y にするこ…

Codeforces Round #364 (Div. 2) D. As Fast As Possible

問題 Problem - D - CodeforcesN 人の子供がいて、一度に K 人乗れるバスがあります。子供の速度が v1 , バスの速度が v2 である時、N 人全員が L 以上進むのに必要な時間を求めてください。 解法 全員が T だけバスに乗るとして、これを二分探索で求めます…

Codeforces Round #363 (Div. 2) DE

復習シリーズ D. Fix a Tree Problem - D - CodeforcesN 頂点の有向グラフがあり、頂点 i から頂点 a[i] に向かう辺があります。できるだけ少ない辺を張り替えてある1つの頂点に向かう有向木にしてください。 解法 連結成分内に閉路が含まれているとき、閉路…

Codeforces Round #373 (Div. 1) C. Sasha and Array

問題 http://codeforces.com/contest/718/problem/C下記の二種類のクエリを処理せよ。 数列 のlからrまでにvずつ足せ。 数列 のlからrまでの各 について を求め、その和を出力しろ。 解法 StarrySkyTree の各ノードに行列をもたせる。 コード import java.io…

Codeforces Round #373 (Div. 2) C. Efim and Strange Grade

問題 Problem - C - Codeforces小数がある。t 回任意のiについて、「小数点第i位で四捨五入する」という操作をする時、得られる最大の数を求めよ。 解法 小数点に出来るだけ近い位置で四捨五入するのが良い。 コード import java.io.IOException; import jav…

Codeforces Round #372 (Div. 2) D. Complete The Graph

問題 http://codeforces.com/contest/716/problem/DN 頂点で重み付き無向辺をM本持ったグラフが与えられる。辺のうちいくつかは重みが分からなくなっているが、正の整数だということは分かっている。このとき、s から t への最短距離がちょうど L となるよう…

Codeforces Round #369 Div2 E. ZS and The Birthday Paradox

問題 Problem - E - Codeforces1 年は 日であるとする。k 人の人に誕生日を聞いた時、誕生日が同じ人が入る確率を求めよ。 解法 http://mayokoex.hatenablog.com/entry/2016/08/30/083738 MOD 以上の連続した区間の総乗の剰余を取ると 0 になる。 を求めると…

Codeforces Round #369 Div2 D. Directed Roads

問題 Problem - D - CodeforcesN頂点N辺の有向グラフがある。頂点 i からは a_i への辺が出ている。好きなだけ辺の向きを変えることができるとき、有向閉路を持たないグラフは何通りできるか。 解法 長さ d の閉路の辺の組み合わせは 通りである。それ以外の…

Codeforces Beta Round #55 Div2 E. Shortest Path

問題 社内の勉強会で出題された。http://codeforces.com/contest/59/problem/EN 個の頂点と M 本の重み 1 の無向辺からなるグラフがある。K 個の (a, b, c) の組が与えられる。各 (a, b, c) について a, b, c の順で連続して頂点を通ることができないとした…

Codeforces Round #368 Div2 D. Persistent Bookcase

問題 Problem - D - CodeforcesN 行 M 列のビットがあり、最初は全て 0 である。以下の 4 種類のクエリが来るので、各クエリの操作後のビットの合計を出力せよ。 i 行 j 列のビットが0であれば1にする。1ならば何もしない。 i 行 j 列のビットが1であれば0に…

Codeforces Round #362 CDE

復習シリーズ C Problem - C - Codeforces二分木上で、以下の2種類のクエリを処理せよ。 u-v 間の最短経路の各辺に w の重みを追加する。 u-v 間の最短経路のコストを計算せよ。 解法 木の深さは高々 60 くらいにしかならないので、愚直にやって良い。 コー…

Codeforces Round #367 Div2 D. Vasiliy's Multiset

問題 Problem - D - Codeforcesmultiset に最初 0 が入っている。以下のような 3 種類のクエリが q 個くるので処理せよ。 x を 1 個 multiset に入れる。 x を 1 個 multiset から削除する。 multiset 内の各数字と x との xor をとった時の最大値を出力せよ…

Codeforces Round #366 C. Thor

問題 Problem - C - Codeforces コード import java.io.IOException; import java.io.InputStream; import java.io.OutputStream; import java.io.PrintWriter; import java.util.ArrayList; import java.util.Map; import java.util.NoSuchElementException…