Codeforces

Codeforces Round #365 D. Mishka and Interesting sum

問題 Problem - D - Codeforces長さ N の自然数の配列が与えられる。以下のような M 個のクエリに答えよ。 [l, r] の範囲にある整数のうち、偶数個登場したものだけを取り出し、それらの xor を出力せよ。 解法 Kmcode 先生のコードを見た。天才を感じた。[l…

Codeforces Round #365 Div2 C: Chris and Road

問題 Problem - C - Codeforcesxy 平面上で (0, 0) にいて、(0, w) に行きたい。自分は y 軸方向に最大 u の速さで動くことができる。N この頂点を持つ凸多角形が x 軸方向に -v の速さで動く。多角形の最初の座標が与えられるので、多角形にぶつからずに(…

Codeforces Round #364 Div2 E. Connecting Universities

問題 Problem - E - CodeforcesN 個の頂点からなる木がある。2K個の大学があり、それぞれ異なる頂点上にある。K個のペアを作ってペア内の各2頂点の距離の合計を最大化せよ。 解法 ある辺を見た時、ペアの両端がそれぞれ辺の反対側にある方が良い。この考えに…

Codeforces Round #363 Div2 E: LRU

問題 http://codeforces.com/contest/699/problem/EN 個のビデオがあり、ビデオ i は の確率で選択される。キャッシュは最近選ばれたビデオを K 個まで記憶しておくことができ、K 個キャッシュした状態でキャッシュに含まれていないビデオが選択された時、キ…

Codeforces Round #362 (Div. 2) E. PLEASE

問題 Problem - E - Codeforces3つのカップを1列に伏せて並べておき、真ん中のカップにコインを入れる。左右どちらかのカップをランダムに選んで真ん中のカップと交換するという操作をn回繰り返す。n は非常に大きい数なので、以下の式で与える。n 回目の操…

Codeforces Round #360 Div2 E. The Values You Can Make

問題 Problem - E - CodeforcesN 枚のコインと K が与えられるので、Kを作れるコインの集合で作れる数字を列挙しろ。 解法 DP コード import java.io.IOException; import java.io.InputStream; import java.io.OutputStream; import java.io.PrintWriter; i…

Codeforces Round #359 Div2 D. Kay and Snowflake

問題 Problem - 686D - Codeforces頂点数 N の木が与えられる。頂点 v を根とする部分木を考えた時、その部分木に含まれる頂点の u うち、u を消去してできる残りの部分木が、いずれも元の部分木の半分以下のサイズになるような u を「v の centroid である…

Codeforces Round #359 Div2 C. Robbers' watch

問題 Problem - C - Codeforces 解法 よく考えると状態はくらいしかない。 コード import java.io.IOException; import java.io.InputStream; import java.io.OutputStream; import java.io.PrintWriter; import java.util.Arrays; import java.util.NoSuchE…

Codeforces Round #358 Div2 E - Alyona and Triangles

問題 Problem - E - Codeforces平面上に、点がN個あり、どの3点を選んでも三角形を作っても面積がSを超えないように配置されている。このとき、N個の点とは別に3点選び、平面上に配置された全ての点を包含して、かつ、面積が4Sを超えないような三角形を作れ…

Codeforces Round #357 Div2 D: Gifts by the List

問題 Problem - D - Codeforces 解法 あるノード cur について考える。 cur および cur の子孫のうち、まだプレゼントを渡していない人がいるとする。この、「まだプレゼントを渡していない人」の中で cur に渡す人がいるなら、他の「まだプレゼントを渡して…

Codeforces Round #356 Div2 E: Bear and Square Grid

問題 Problem - E - Codeforces 解法 潰す範囲の正方形を愚直に全部試す。この時、正方形内部の管理を愚直にやると遅くなるので、しゃくとり法の要領で1列ずつやる。 コード #include <bits/stdc++.h> using namespace std; const int DX[] = {0, 0, 1, -1}; const int DY[]</bits/stdc++.h>…

Codeforces Round #355 D. Vanya and Treasure

問題 Problem - D - Codeforces 解法 Codeforces Round #355 (Div. 2) Editorial - Codeforcesダイクストラと全列挙を使い分ける。 コード #include <bits/stdc++.h> using namespace std; typedef pair<int, int> P; typedef tuple<int, int, int> E; template <class T, class U> void chmin(T &t, U f) { if (t > f) </class></int,></int,></bits/stdc++.h>…

Codeforces Round #354 Div2 E. The Last Fight Between Human and AI

問題 Problem - E - Codeforces 解法 K=0 のときや、'?' が含まれるときは場合分けでなんとかなる。'?' が含まれず、Kが0でない時を考える。がx-kで割り切れるとき、f(k)=0 だから、 である。 よって、より はkの倍数である。 とおいて全体をkで割ると、 よ…

Codeforces Round #354 Div2 D: Theseus and labyrinth

問題 Problem - D - Codeforces 解法 筋肉ダイクストラ コード #include <bits/stdc++.h> using namespace std; template <class T, class U> void chmin(T &t, U f) { if (t > f) t = f; } typedef tuple<int, int, int, int> P; // dist, layer, h,w const int INF = 1e9, LAYERS = 4; const int RIGHT = 0, LEFT</int,></class></bits/stdc++.h>…

Codeforces Round #353 Div2 C, D

C. Money Transfers Problem - C - Codeforces 解法 合計すると0になる連続部分列をできるだけ多くすれば良い。 コード #include <bits/stdc++.h> using namespace std; template <class T, class U> void chmax(T &t, U f) { if (t < f) t = f; } int main() { cin.tie(0); ios::sync_with_st</class></bits/stdc++.h>…

Codeforces Round #352 Div2 C, D

C. Recycling Bottles Problem - C - Codeforces 問題 2次元平面で Adil が (ax, ay) に、Bera が (bx, by) にいる。ゴミ箱が (tx, ty) にあり、ゴミが散らばっている。2人は以下の操作を繰り返す。 落ちているゴミを選び、そこまで行く。 ゴミを拾い、ゴミ…

Codeforces Round #351 Div2 D: Bear and Two Paths

問題 Problem - D - Codeforces 解法 埋め込み コード #include <bits/stdc++.h> using namespace std; int main() { cin.tie(0); ios::sync_with_stdio(false); int N, K; cin >> N >> K; int a, b, c, d; cin >> a >> b >> c >> d; vector<bool> used(N + 1, false); used[a] = </bool></bits/stdc++.h>…

Codeforces Round #350 Div2 F: Restore a Number

問題 Problem - F - Codeforces 解法 含むべき部分文字列以外の部分は、残った数字でできるだけ小さい整数を作れば良い。求めるべき文字列は3つのうちのいずれかである。 含むべき部分文字列をTとすると、 Tを先頭に含むもの。 Tの1桁目の数字をqとした時に…

Codeforces Round #350 Div2 E: Correct Bracket Sequence Editor

問題 Problem - E - Codeforces 解法 愚直シミュレーション コード #include <bits/stdc++.h> using namespace std; string S; map<int, int> tree_map; int dfs(int pos) { if (pos == S.size()) return pos; if (S[pos] == '(') { int right = dfs(pos + 1); tree_map[pos] = right;</int,></bits/stdc++.h>…

Codeforces Round #348 Div2 E: Little Artem and Time Machine

問題 Problem - E - Codeforces 解法 各xについて独立に考えることができる。各xについてtを座標圧縮して、Fenwick Tree を使って管理する。 コード #include <bits/stdc++.h> using namespace std; template <typename T> void uniq(vector<T> &v) { v.erase(unique(v.begin(), v.end()), </t></typename></bits/stdc++.h>…

IndiaHacks 2016 C: Bear and Up-Down

問題 Problem - C - Codeforces 解法 愚直にやると 150000 x 150000 かかるが、入れ替えなければならないの候補となる場所は 2箇所程度 * 3つ程度 なので、大雑把に20と見積もっても、 150000 x 20 程度で全通りswapを試すことが出来る。加えて、 nice かど…

IndiaHacks 2016 D: Delivery Bears

問題 Problem - D - Codeforces 解法 最大フロー問題っぽい雰囲気を感じることができるが、単純にそのまま最大フローをしてもダメな理由は「クマが分裂できない」ためである。そこで、最大フローの各辺のcapacityにweightをそのまま代入するのではなく、「通…

Manthan, Codefest 16 C: Spy Syndrome 2

問題 Problem - C - Codeforces 解法 文字列の一致判定はローリングハッシュにしてもらって、メモ化再帰で計算量を減らす。 コード #include <bits/stdc++.h> using namespace std; typedef long long ll; struct ToLower { char operator()(char c) { return tolower(c); }</bits/stdc++.h>…

Codeforces Round #339 Div2 C: Peter and Snow Blower

問題 codeforces.com 解法 内側の円は中心の点と最も近い線分との距離になる。外側の円は中心から最も遠い頂点との距離になる。 点と線分の距離を求めるライブラリ double distanceVertex(pair<double, double> p1, pair<double, double> p2) { double dx = p1.first - p2.first; double dy =</double,></double,>…

Codeforces Good Bye 2015 D: New Year and Ancient Prophecy

kenkoooo.hatenablog.comrng_58 さんのコードを参考にした。 よく考えたら、ハッシュなんか使わなくても解けるんだよなあ #include <cstdio> #include <iostream> #include <sstream> #include <fstream> #include <iomanip> #include <algorithm> #include <cmath> #include <string> #include <vector> #include <list> #include <queue> #include <stack> #incl</stack></queue></list></vector></string></cmath></algorithm></iomanip></fstream></sstream></iostream></cstdio>…

Codeforces Good Bye 2015 D: New Year and Ancient Prophecy

問題 codeforces.com 解法 Rolling-Hashing で文字列の大小関係をO(log N)で求めようのコーナー kenkoooo.hatenablog.com コード #include <cstdio> #include <iostream> #include <sstream> #include <fstream> #include <iomanip> #include <algorithm> #include <cmath> #include <string> #include <vector> #include <list> #include <queue> #inc…</queue></list></vector></string></cmath></algorithm></iomanip></fstream></sstream></iostream></cstdio>

Codeforces Good Bye 2015 C: New Year and Domino

問題 http://codeforces.com/contest/611/problem/Ccodeforces.com 解法 2次元の累積和。kenkoooo.hatenablog.com コード #include <cstdio> #include <iostream> #include <sstream> #include <fstream> #include <iomanip> #include <algorithm> #include <cmath> #include <string> #include <vector> #include <list> #include </list></vector></string></cmath></algorithm></iomanip></fstream></sstream></iostream></cstdio>

Codeforces Round #337 Div2 D: Vika and Segments

問題 codeforces.com 解法 y座標について Fenwick Tree を作りたいので、y 座標を座標圧縮する。 xを小さい方から順に見ていく。 xで始まる水平方向の区間があれば、それをBITに保存する。 x上にある垂直方向の区間を全て足し合わせる。ただし、水平方向と重…

Codeforces Round #336 Div2 D: Zuma

問題 codeforces.com 解法 区間DP。@mayoko_ 申し訳ねぇ申し訳ねぇ… [l,r]で回文を挿入しまくって文字列を作りたいです. a[l]==a[i]のところがあったときそこを使うことにしたとき,[l+1,i-1]と[i+1,r]について考えればOKです 回文が始まるのは長さ1か長さ2…

Codeforces Round #323 Div2 D: Once Again...

問題 codeforces.com 解法 増加列に含まれる値の種類は多くてN種類なので、T>Nならば、最も多い種類の点の数を (T-N) 回足せば良い。 コード import java.util.ArrayList; import java.util.Arrays; import java.util.Collections; import java.util.Scanner…