AOJ

AOJ 2893: Balanced Edge Deletion

問題 http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=2893 解法 橋を全列挙し、それぞれについて削除したときの cost を求め、ソートすれば良い。具体的な実装としては、 橋を列挙する。 橋を含まない連結な部分グラフを潰して 1 つの頂点とし、…

AOJ 2891: Namo.. Cut

問題 http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=2891 解法 N 頂点 N 辺のグラフ(いわゆる「なもりグラフ」)は1つだけ閉路があり、その閉路に木がいくつか連結している形になる。各クエリの頂点の両方とも閉路に含まれている場合2本切断す…

AOJ 2900: Bumpy Array

問題 http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=2900 解法 と並んでいるのを としたいが、これが成り立っていないとする。 が成り立っている時、 となっているので、 を動かすことは得にならない。よって 以降について問題を解けば良い。が…

lowlink, 橋や関節点について練習

lowlink や橋や関節点について、いくつか問題を解いたのでリンクを貼っておく。 lowlink の説明 kagamiz.hatenablog.comkagamiz 先生による有名記事。大変わかりやすい。 関節点・橋の確認用問題 http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=…

AOJ 3022: Cluster Network

問題 http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=3022 解法 雰囲気から、関節点を求める機運が高まるが、実際の問題はその後に最後の答えを出力するパートである。http://web-ext.u-aizu.ac.jp/circles/acpc/commentary/ACPC2017Day2/J.pdf…

AOJ Largest Rectangle

問題 http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=DPL_3_B 解法 各列についてヒストグラムに内接する最大長方形を求める。 コード use std::cmp; use std::collections::VecDeque; trait TopQueue<T> { fn top(&self) -> &T; } impl<T> TopQueue<T> fo</t></t></t>…

AOJ 2829 Room Assignment

問題 http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=2829 解法 JAG の wiki に分かりやすい解説があります。2017/Practice/模擬国内予選/講評 - ACM-ICPC Japanese Alumni Group場合分けとしては以下の 3 つです 長さ 3 以上の閉路が存在する場…

AOJ 3019 Picnic

問題 Picnic | Aizu Online Judge 解法 ワーシャルフロイド→巡回セールスマン→半分全列挙→個数制約付きナップサック コード import java.util import scala.io.StdIn import scala.util.Try object Main extends App { val INF: Long = 1e15.toLong val (n, …

会津合宿 2017 2 日目 G : Picnic

問題 http://judge.u-aizu.ac.jp/onlinejudge/cdescription.jsp?cid=ACPC2017Day2&pid=G 解法 ワーシャルフロイドと巡回セールスマン問題の bit DP で、ある町の部分集合を回って戻ってくるのにかかるコストを前計算しておく。さらに、町の集合を の 2 つに…

会津合宿 2017 3 日目 E : Taiyaki-Master and Eater

問題 AIZU ONLINE JUDGE 解法 2次元のBITを貼る。 コード import java.util.Scanner import scala.collection.mutable.ArrayBuffer object Main extends App { val in = new Scanner(System.in) val H = in.nextInt() val W = in.nextInt() val T = in.nextI…

AOJ 2828: Matryoshka Doll

問題 Matryoshka Doll | Aizu Online Judge 解法 取り込まれた人形のコストを 0 として、取り込まれていない人形のコストはそのまま結果に加えるように、最小費用流のグラフを作る。 コード import java.util.Scanner import scala.collection.mutable impor…

AOJ 1163 Cards

http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=1163GCD + 二部マッチング import java.io.IOException; import java.io.InputStream; import java.io.PrintWriter; import java.util.ArrayDeque; import java.util.ArrayList; import java.util…

RUPC 2016 Day2 L: String in String

問題 http://judge.u-aizu.ac.jp/onlinejudge/cdescription.jsp?cid=RitsCamp16Day2&pid=L 解法 kenkoooo.hatenablog.com コード import java.io.IOException; import java.io.InputStream; import java.io.OutputStream; import java.io.PrintWriter; impor…

AOJ 2644 Longest Match

問題 Longest Match | Aizu Online Judge 解法 SuffixArray を作ると、Sに含まれる a の SuffixArray 上での lower_bound と upper_bound を求めることができます。その中で最も前のものを求めたいですが、これはRMQで持っておけば良いです。b については上…

ACPC2016 Day2 J : Char Swap

問題 http://judge.u-aizu.ac.jp/onlinejudge/cdescription.jsp?cid=ACPC2016Day2&pid=J 解法 J : 解説 from Takumi Yamashita www.slideshare.net元の文字列がアルファベット を 個含むとき、前半と後半に寄せて、 を 個ずつ含むようにします。(解説スライ…

ACPC2016 Day2 H : Hogemon Get

問題 http://judge.u-aizu.ac.jp/onlinejudge/cdescription.jsp?cid=ACPC2016Day2&pid=H 解法 ボールを獲得するたびに、(ボールを獲得した時刻, ボールを獲得した場所, 直前にボールを獲得した場所, 直前にボールを獲得した場所が再度利用可能になるまでの時…

ACPC2016 Day2 G : Star

問題 http://judge.u-aizu.ac.jp/onlinejudge/cdescription.jsp?cid=ACPC2016Day2&pid=G 解法 正 N 角形から小さい二等辺三角形を N 個除けば良い。 コード import java.io.IOException; import java.io.InputStream; import java.io.OutputStream; import j…

ACPC Day2 F : Curling Puzzle

問題 http://judge.u-aizu.ac.jp/onlinejudge/cdescription.jsp?cid=ACPC2016Day2&pid=F 解法 1 列だけのときは @ の片側にある @ から一番近いストーンの位置と、 @ の反対側にあるストーンの数を持てば解けます。それ以外の場合は↓F問題です。 pic.twitter…

ACPC Day2 D : One-Time Path

問題 http://judge.u-aizu.ac.jp/onlinejudge/cdescription.jsp?cid=ACPC2016Day2&pid=D 解法 N-1 に着く時刻を最大化したいだけで、それ以外の頂点に着く時刻は早ければ早いほど良いことに気づく。あとは一度見た辺を二度と見たくないという気持ちを込めな…

RUPC 2016 Day2 E: Rubik Dungeon

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

RUPC 2016 Day3 F: Kitsuchiri

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

RUPC 2016 Day2 L: String in String

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

RUPC 2016 Day3 D: Complex Oracle (O(N(logN)) 解法)

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

RUPC 2016 Day3 D: Complex Oracle (O(N(logN)^2) 解法)

これの高速化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>…

RUPC 2016 Day3 D: Complex Oracle (O(N^2) 解法)

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

RUPC 2016 Day3 E: Arai's

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

RUPC 2016 Day2 H: Reflection Warp Machine

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

RUPC 2016 Day1 D: Scanner

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

RUPC 2016 Day1 E: 28

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

RUPC 2016 Day1 C: AddMul

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