Codeforces
問題 Problem - D - Codeforcesmultiset に最初 0 が入っている。以下のような 3 種類のクエリが q 個くるので処理せよ。 x を 1 個 multiset に入れる。 x を 1 個 multiset から削除する。 multiset 内の各数字と x との xor をとった時の最大値を出力せよ…
問題 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…
問題 Problem - D - Codeforces長さ N の自然数の配列が与えられる。以下のような M 個のクエリに答えよ。 [l, r] の範囲にある整数のうち、偶数個登場したものだけを取り出し、それらの xor を出力せよ。 解法 Kmcode 先生のコードを見た。天才を感じた。[l…
問題 Problem - C - Codeforcesxy 平面上で (0, 0) にいて、(0, w) に行きたい。自分は y 軸方向に最大 u の速さで動くことができる。N この頂点を持つ凸多角形が x 軸方向に -v の速さで動く。多角形の最初の座標が与えられるので、多角形にぶつからずに（…
問題 Problem - E - CodeforcesN 個の頂点からなる木がある。2K個の大学があり、それぞれ異なる頂点上にある。K個のペアを作ってペア内の各2頂点の距離の合計を最大化せよ。 解法 ある辺を見た時、ペアの両端がそれぞれ辺の反対側にある方が良い。この考えに…
問題 http://codeforces.com/contest/699/problem/EN 個のビデオがあり、ビデオ i は の確率で選択される。キャッシュは最近選ばれたビデオを K 個まで記憶しておくことができ、K 個キャッシュした状態でキャッシュに含まれていないビデオが選択された時、キ…
問題 Problem - E - Codeforces3つのカップを1列に伏せて並べておき、真ん中のカップにコインを入れる。左右どちらかのカップをランダムに選んで真ん中のカップと交換するという操作をn回繰り返す。n は非常に大きい数なので、以下の式で与える。n 回目の操…
問題 Problem - E - CodeforcesN 枚のコインと K が与えられるので、Kを作れるコインの集合で作れる数字を列挙しろ。 解法 DP コード import java.io.IOException; import java.io.InputStream; import java.io.OutputStream; import java.io.PrintWriter; i…
問題 Problem - 686D - Codeforces頂点数 N の木が与えられる。頂点 v を根とする部分木を考えた時、その部分木に含まれる頂点の u うち、u を消去してできる残りの部分木が、いずれも元の部分木の半分以下のサイズになるような u を「v の centroid である…
問題 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…
問題 Problem - E - Codeforces平面上に、点がN個あり、どの3点を選んでも三角形を作っても面積がSを超えないように配置されている。このとき、N個の点とは別に3点選び、平面上に配置された全ての点を包含して、かつ、面積が4Sを超えないような三角形を作れ…
問題 Problem - D - Codeforces 解法 あるノード cur について考える。 cur および cur の子孫のうち、まだプレゼントを渡していない人がいるとする。この、「まだプレゼントを渡していない人」の中で cur に渡す人がいるなら、他の「まだプレゼントを渡して…
問題 Problem - E - Codeforces 解法 潰す範囲の正方形を愚直に全部試す。この時、正方形内部の管理を愚直にやると遅くなるので、しゃくとり法の要領で1列ずつやる。 コード #include <bits/stdc++.h> using namespace std; const int DX[] = {0, 0, 1, -1}; const int DY[]</bits/stdc++.h>…
問題 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>…
問題 Problem - E - Codeforces 解法 K=0 のときや、'?' が含まれるときは場合分けでなんとかなる。'?' が含まれず、Kが0でない時を考える。がx-kで割り切れるとき、f(k)=0 だから、 である。 よって、より はkの倍数である。 とおいて全体をkで割ると、 よ…
問題 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>…
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>…
C. Recycling Bottles Problem - C - Codeforces 問題 2次元平面で Adil が (ax, ay) に、Bera が (bx, by) にいる。ゴミ箱が (tx, ty) にあり、ゴミが散らばっている。2人は以下の操作を繰り返す。 落ちているゴミを選び、そこまで行く。 ゴミを拾い、ゴミ…
問題 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>…
問題 Problem - F - Codeforces 解法 含むべき部分文字列以外の部分は、残った数字でできるだけ小さい整数を作れば良い。求めるべき文字列は3つのうちのいずれかである。 含むべき部分文字列をTとすると、 Tを先頭に含むもの。 Tの1桁目の数字をqとした時に…
問題 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>…
問題 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>…
問題 Problem - C - Codeforces 解法 愚直にやると 150000 x 150000 かかるが、入れ替えなければならないの候補となる場所は 2箇所程度 * 3つ程度 なので、大雑把に20と見積もっても、 150000 x 20 程度で全通りswapを試すことが出来る。加えて、 nice かど…
問題 Problem - D - Codeforces 解法 最大フロー問題っぽい雰囲気を感じることができるが、単純にそのまま最大フローをしてもダメな理由は「クマが分裂できない」ためである。そこで、最大フローの各辺のcapacityにweightをそのまま代入するのではなく、「通…
問題 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.com 解法 内側の円は中心の点と最も近い線分との距離になる。外側の円は中心から最も遠い頂点との距離になる。 点と線分の距離を求めるライブラリ double distanceVertex(pair<double, double> p1, pair<double, double> p2) { double dx = p1.first - p2.first; double dy =</double,></double,>…
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.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>
問題 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.com 解法 y座標について Fenwick Tree を作りたいので、y 座標を座標圧縮する。 xを小さい方から順に見ていく。 xで始まる水平方向の区間があれば、それをBITに保存する。 x上にある垂直方向の区間を全て足し合わせる。ただし、水平方向と重…
