AOJ

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

AOJ DSL_2_B: Range Sum Query

問題 Range Sum Query | Aizu Online Judge 解法 Binary Indexed Tree (Fenwick Tree) ライブラリ確認用 コード #include <cstdio> #include <iostream> #include <sstream> #include <fstream> #include <iterator> #include <iomanip> #include <algorithm> #include <cmath> #include <string> #include <vector> #include <list> #incl…</list></vector></string></cmath></algorithm></iomanip></iterator></fstream></sstream></iostream></cstdio>

AOJ 1156: Twirling Robot

AOJ

問題 Twirling Robot | Aizu Online Judge 解法 位置・状態を頂点にしたグラフでダイクストラ。類題 kenkoooo.hatenablog.com コード #include <cstdio> #include <iostream> #include <sstream> #include <fstream> #include <iterator> #include <iomanip> #include <algorithm> #include <cmath> #include <string> #include <vector> #include <list> #…</list></vector></string></cmath></algorithm></iomanip></iterator></fstream></sstream></iostream></cstdio>

AOJ 2425: 全探索お姉さんの休日

問題 A Holiday of Miss Brute Force | Aizu Online Judge 解法 x, y, t mod 6によって方向は定まるので、これらの(x,y,t%6)を頂点とする有向グラフを作り、ダイクストラする。 コード import java.util.ArrayList; import java.util.Arrays; import java.ut…

AOJ 2426: 宝探し(2次元の累積和)

問題 Treasure Hunt | Aizu Online Judge 解法 フィールドは広いが宝物の数は高々5000なので、宝物に準拠した最大5001*5001のフィールドを作る。treasures[i][j]にかつにおける宝物の数を入れておくと、かつにおける宝物の数は、以下の式で表せるようになる…

AOJ 2320: Infinity Maze

問題 Infinity Maze | Aizu Online JudgeH*Wの迷路が与えられ、ロボットをL回移動させる。ロボットは壁や障害物にぶつかると右に90度回転する。この回転は移動回数にはカウントしない。L回移動させた後、ロボットはどこにいてどこを向いているか。 解法 だが…

AOJ 2301: Sleeping Time (二分木探索・幅優先探索)

問題 Sleeping Time | Aizu Online JudgeでTを目指してK回二分木探索するが、Pの確率で間違った方を選んでしまうとき、探索して見つけた値T'がを満たす確率を求めよ。 解法 二分木探索する(素直) コード import java.math.BigDecimal; import java.util.Ar…

AOJ 1280: Slim Span (最小全域木・クラスカル法)

問題 Slim Span | Aizu Online Judge無向グラフが与えられるので、エッジの最小コストと最大コストの差が最小になるように全域木を作る。作れる場合は最小コストを、無理なら-1を出力する。 解法 エッジを昇順に並べておき、エッジiより大きいコストの中で最…

AOJ 2426: 宝探し

問題 Treasure Hunt | Aizu Online Judge 解法 問題の条件的に愚直にやると最悪ケースで回くらいループを回すことになるから、累積和をとったりとか色々やらなきゃいけないはずなんだけど、なんか通っちゃった。 コード import java.io.IOException; import …

AOJ 2299: Tiles are Colorful

問題 Tiles are Colorful | Aizu Online Judge 解法 叩けるマスを探す→叩いてみる→ポイントになるなら消す→叩けるマスを探す→…の繰り返しでいけた。叩く順番は関係ない。 コード import java.util.PriorityQueue; import java.util.Scanner; public class Ma…

AOJ 2003: 線分の交差

問題 Railroad Conflict | Aizu Online Judge 解法 書くだけ。線分の交差とかはライブラリにしておくと便利っぽい。 コード import java.io.IOException; import java.util.ArrayList; import java.util.Collections; public class Main { public static voi…

AOJ 2332: 時空のスゴロク・ロード (幅優先探索)

問題 Space-Time Sugoroku Road | Aizu Online Judge 解法 幅優先探索。各マスに到達するのに必要な最小回数を更新した時だけキューに入れるようにすれば、ループを避けることが出来る。 コード import java.util.ArrayDeque; import java.util.Arrays; impo…

AOJ 1175: そして,いくつになった? (bitDP)

問題 And Then. How Many Are There? | Aizu Online Judge 解法 bitDP。円の個数は最大で24個しかないので、遷移の状態は最大16777216通りしかない。bitで管理するとどの円の上にどの円が載ってるかも楽に管理できる。 コード import java.io.IOException; p…

AOJ 2005: Water Pipe Construction (ワーシャルフロイト法)

問題 Water Pipe Construction | Aizu Online Judge 解法 ワーシャルフロイト法でそれぞれの基地間のコストを計算する。各基地について、水源からのコストと目的地までのコストを算出し、最も小さくなる時を出力すれば良い。 コード import java.util.Scanne…

AOJ 1347: Shopping

問題 Shopping | Aizu Online JudgeN個の店が等間隔に一直線に並んでいて、店に行く前に店に行かなければならないという制限がある時、最短で行くにはどのくらい歩けば良いか。 解法 1回しか通らない道と3回通る道があるので、それを個々の店の間について考…

AOJ 1326: Stylish

問題 Stylish | Aizu Online JudgeStylishという言語では、丸括弧()、カールしてる括弧{}、四角い括弧[]についてそれぞれインデント数が決まっている。これらをそれぞれR, C, Sとする。インデントはドットで表される。最初にStylishマスターが書いたコードを…

AOJ 2166: Erratic Sleep Habits

問題 Erratic Sleep Habits | Aizu Online Judge睡眠のサイクル(12時に寝てt時間寝る)と、D日目はM時に起きないといけない、という情報が与えられるので、睡眠サイクルをリセットする最小回数を求める。 解法 動的計画法。dp[i日目に][サイクルjがきてる]…

AOJ 1327: One-Dimensional Cellular Automaton

問題 One-Dimensional Cellular Automaton | Aizu Online Judgeとの漸化式が与えられるので、からを求める。 解法 上のような行列Dを考える。問題の操作は下の式のようになるので、最初の状態に行列DをT回かければ良い。よってを考える。などの計算はまとも…

AOJ 1306: 風船キャッチゲーム

問題 Balloon Collecting | Aizu Online Judge 落ちてくる風船をキャッチするゲーム。キャッチャーは風船を積むごとに動きが遅くなるほか、風船は最大3個までしか積めない。積んでいる風船はHouseに戻ることで0にすることが出来る。最小の移動で全ての風船が…

AOJ 1296: 幅優先探索

問題 Repeated Substitution with Sed | Aizu Online Judge n個のαとbの組が与えられる。1回の操作で文字列γの中のαを全てβに置き換えることができる。αとβを上手く使いながら、γをδに変換するのに必要な最小の操作回数を考える。 解法 幅優先探索。βはαより…

AOJ 2021: お姫様の危機をワーシャル-フロイト法で解く

問題 Princess in Danger | Aizu Online Judge 解法 まずは制限時間や冷凍庫位置を考えずに、ワーシャルフロイト法で任意の2点間の最小必要時間を出しておく。すると任意の2冷凍庫間の最小必要時間も出る。この後は冷凍庫間の移動だけを考えるので、それ以外…

AOJ 1127: クラスカル法で最小全域木問題を解く

問題 Building a Space Station | Aizu Online Judge 3次元空間にn個の球形の宇宙ステーションがあるので、それらを行き来する通路を作る際の、通路の最小合計距離を求める。 解法 2つの宇宙ステーション間の距離を求め、最小全域木探索する。 コード import…

AOJ 2002: X-Ray Screening System

問題 X-Ray Screening System | Aizu Online Judge 解法 それぞれの物体の四点を取って、その中に空白が入ってたらアウト。空白のある物体が存在しない時は上下関係を見て、矛盾があればアウト。 本当は、必ず1つは長方形が存在するはずなので、それを上手く…

AOJ 1144: カーリング2.0

問題 Curling 2.0 | Aizu Online Judge スタートのマスとゴールのマスが決まっている平面上で、駒をゴールまで運ぶ。駒は滑って移動するしかなく、障害物にぶつかるまで止まれない。ぶつかられた障害物は消滅する。フィールド外に出た場合は失敗となる時、最…

AOJ 2175: ホイスト

問題 Whist | Aizu Online Judge 解法 Google コード import java.util.Scanner; public class Main { public static void main(String[] args) { Scanner sc = new Scanner(System.in); while (true) { char T = sc.next().charAt(0); if (T == '#') { sc.c…

AOJ 2321: Butterfly

問題 Butterfly | Aizu Online Judge あれな感じの女の子ができるだけ多くの男とデートしたいのだが全員とする時間がない時、イケメンとだけデートできるように最適なデートプランを考える。ふぁっく。 解法 DFS コード import java.util.ArrayList; import …

AOJ 1237: Shredding Company

問題 Shredding Company | Aizu Online Judge 解法 DFS コード import java.util.Scanner; public class Main { private static int N; public static void main(String[] args) { Scanner sc = new Scanner(System.in); while (true) { N = sc.nextInt(); S…

AOJ 1250: Leaky Cryptography

問題 Leaky Cryptography | Aizu Online Judge 解法 Kの後ろからi桁目を0にした時に、下i桁の答えが条件に合うならば、Kの後ろからi桁目は0であり、合わなければ1である。 コード import java.util.Scanner; public class Main { public static void main(St…

AOJ 2340: Carpenters' Language

問題 Carpenters' Language | Aizu Online Judge 解法 "("の数と")"の数が一緒ならYes。マジなんなんだこの問題。 解答 import java.io.IOException; import java.util.Scanner; public class Main { public static void main(String[] args) throws IOExcep…

AOJ 1325: Ginkgo Numbers

問題 Ginkgo Numbers | Aizu Online Judge 2つの整数mとnが与えられるので、m2+n2 の約数となる x2+y2 を満たす整数xとyが存在するかどうかを調べる。 解法 全探索。素因数分解。 コード import java.io.IOException; import java.util.Scanner; public clas…

AOJ 2243: ダンレボのあれ

問題 Step Step Evolution | Aizu Online Judge 上の図の一番右のように右足と左足が交差しないようにパネルを踏む時、同じ足で連続して踏む回数を最小にするにはどうしたら良いか。 解法 DP。例えば、i番目のパネルがi-1番目のパネルより右にある時、i番目…

AOJ 1316: ドーナツ

問題 The Sorcerer's Donut | Aizu Online Judge 上のようにドーナツ状になっている文字表の中に2回出てくるフレーズを探す。2つ以上ある場合は最も長いものを返す。同じ長さなら辞書順で前にあるものを返す。 解法 例にあるとおり、 ABCD EFGH IJKL のFから…