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

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

問題 B: 交点 - 東京大学プログラミングコンテスト2014 | AtCoder コード #include <bits/stdc++.h> using namespace std; typedef long long ll; int main() { cin.tie(0); ios::sync_with_stdio(false); double X, Y; cin >> X >> Y; int cnt = 0; for (int x = floor(X) </bits/stdc++.h>…

問題 C: 席替え - AtCoder Regular Contest 018 | AtCoder 解法 重要な制約として"p a%p!=0 の時、すべての生徒の成績は異なるため、各々が前から何行目に来るかが定まる。各生徒を自分がいるべき行まで移動させる。この時、列は移動させないため、重なる生…

問題 AIZU ONLINE JUDGE 解法 回転と回転の間には移動を挟まなそう、みたいな適当な気持ちで適当に書いたら通ってしまった。 コード #include <bits/stdc++.h> using namespace std; typedef long long ll; template <typename T> std::ostream &operator<<(std::ostream &out, const st</typename></bits/stdc++.h>…

問題 abc034.contest.atcoder.jp コード #include <bits/stdc++.h> using namespace std; typedef long long ll; template <typename T> std::ostream &operator<<(std::ostream &out, const std::vector<T> &v) { if (!v.empty()) { out << '['; std::copy(v.begin(), v.end(), std::ostre</t></typename></bits/stdc++.h>…

問題 AIZU ONLINE JUDGE 解法 答えるべき情報は対応する配列の値が全て同じか否かだけなので、保存する情報は S[i] と S[N-1-i] の差だけで良い。この差が全てのiについて0になれば左右対称であると言える。このことから、右半分は左半分との差分だけ保存し…

問題 AIZU ONLINE JUDGE 解法 各クエリについて、 l, r, M が来るが、先に文字列の Suffix Array を作っていて、Mを含む upper_bound と lower_bound を求めると、「各クエリについて、文字列で[l, r]の範囲で SA で[lower_bound, upper_bound)の範囲に入っ…

立命館大学競技プログラミング合宿2016とは atnd.org 社会人は言質をとる @kenkoooo はい、参加可能です。ぜひご参加ください！— RiPPro (@PJ_RiPPro) February 16, 2016 1日目 pakapa104.hatenablog.com tookunn.hatenablog.com 2日目 yazaten.hatenablog.c…

問題 C: データ構造 - AtCoder Regular Contest 033 | AtCoder 解法 @kenkoooo BITには二分探索というテクがあるそうです(受け売りhttps://t.co/VM8Y0DxGUz— CodeVS本戦通過ラインの境界 (@btk15049) 2016, 3月 8lower_bound() 搭載 Binary Indexed Tree (BI…

kenkoooo.hatenablog.com kenkoooo.hatenablog.comkawatea さんが使ってた強めのsetをコピペした。 コード #include <bits/stdc++.h> using namespace std; typedef long long ll; template <typename T> std::ostream &operator<<(std::ostream &out, const std::vector<T> &v) { if (!v.e</t></typename></bits/stdc++.h>…

これの高速化ver kenkoooo.hatenablog.com 解法 BIT で抜けた数を持っておき、「今残っている数の中でmid番目」を当てる二分探索をする。 コード #include <bits/stdc++.h> using namespace std; typedef long long ll; template <typename T> std::ostream &operator<<(std::ostream &o</typename></bits/stdc++.h>…

問題 AIZU ONLINE JUDGE 解法 vector::erase() が速いこと、 vector::erase() を落とすテストケースが用意されていないこと、AOJが速いこと、N*2 クエリ用の時間のうちNクエリ分を計算時間として使えること等の様々な要因から、O(N^2)解法が通る。 コード #i…

問題 AIZU ONLINE JUDGE 解法 最小費用流やるだけ。フローを1ずつ流して良い。 コード #include <bits/stdc++.h> using namespace std; typedef long long ll; template <typename T> std::ostream &operator<<(std::ostream &out, const std::vector<T> &v) { if (!v.empty()) { out << '[</t></typename></bits/stdc++.h>…

kenkoooo.hatenablog.comhirokazu さんの SA-IS ライブラリをコピペさせてもらった。 コード #include <bits/stdc++.h> using namespace std; typedef long long ll; template <typename T> std::ostream &operator<<(std::ostream &out, const std::vector<T> &v) { if (!v.empty()) { out </t></typename></bits/stdc++.h>…

問題 RUPC 2016 の時に @public_sate さんに教えてもらった。F: Longest Match - Japan Alumni Group Summer Camp 2014 Day 4 | AtCoder 解法 コード #include <bits/stdc++.h> using namespace std; typedef long long ll; template <typename T> std::ostream &operator<<(std::ostrea</typename></bits/stdc++.h>…

問題 AIZU ONLINE JUDGE 解法 それぞれの線を引いた時に行き来できる星たちを列挙しておく。後はどのワープを使うかをDPしていけば良い。 コード #include <bits/stdc++.h> using namespace std; typedef long long ll; template <typename T> std::ostream& operator<<(std::ostream& o</typename></bits/stdc++.h>…

問題 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>…

問題 I: 支配と友好 - 東京大学プログラミングコンテスト2013 | AtCoder 解法 2回オイラーツアーするだけ。勝手に根が0だと思い込んで（しかもサンプルがそれで合う）メッチャハマった。 コード #include <bits/stdc++.h> using namespace std; typedef long long ll; const</bits/stdc++.h>…

問題 AIZU ONLINE JUDGE 解法 愚直DP コード #include <bits/stdc++.h> using namespace std; typedef long long ll; int main() { cin.tie(0); ios::sync_with_stdio(false); ll N; cin >> N; vector<int> T(N); T.resize(N); for (int i = 0; i < N; ++i) cin >> T[i]; sort(T.</int></bits/stdc++.h>…

問題 AIZU ONLINE JUDGE コード #include <bits/stdc++.h> using namespace std; typedef long long ll; template <typename T> std::ostream& operator<<(std::ostream& out, const std::vector<T>& v) { if (!v.empty()) { out << '['; std::copy(v.begin(), v.end(), std::ostream_itera</t></typename></bits/stdc++.h>…

問題 AIZU ONLINE JUDGE コード #include <bits/stdc++.h> using namespace std; typedef long long ll; template <typename T> std::ostream& operator<<(std::ostream& out, const std::vector<T>& v) { if (!v.empty()) { out << '['; std::copy(v.begin(), v.end(), std::ostream_itera</t></typename></bits/stdc++.h>…

問題 D: たこ焼き屋とQ人の高橋君 - AtCoder Regular Contest 048 | AtCoder 解法 AtCoder Regular Contest 048 Submission #653842 - AtCoder Regular Contest 048 | AtCoder コード #include <bits/stdc++.h> using namespace std; typedef long long ll; struct HL { vec</bits/stdc++.h>…

問題 C: 足の多い高橋君 - AtCoder Regular Contest 048 | AtCoder 解法 AtCoder Regular Contest 048 コード #include <bits/stdc++.h> using namespace std; typedef long long ll; const int MOD = 1e9 + 7; ll gcd(ll x, ll y) { return y ? gcd(y, x % y) : x; } ll mo</bits/stdc++.h>…