AtCoder
問題 A: 幾何問題を解こう - Japan Alumni Group Summer Camp 2015 Day 2 | AtCoder 解法 N^k 進数で表せる小数は N 進数で表せる。 コード #include <bits/stdc++.h> using namespace std; typedef long long ll; set<int> yakusu(int B) { set<int> p; int s = sqrt(B) + 10; for (i</int></int></bits/stdc++.h>…
問題 D: Suffix Concat - AtCoder Regular Contest 050 | AtCoder 解法 公式解説の通り。suffix array ではなく rolling hash でやった。 http://arc050.contest.atcoder.jp/data/arc/050/review.pdf コード #include <bits/stdc++.h> using namespace std; typedef long lo</bits/stdc++.h>…
問題 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 の時、すべての生徒の成績は異なるため、各々が前から何行目に来るかが定まる。各生徒を自分がいるべき行まで移動させる。この時、列は移動させないため、重なる生…
問題 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>…
問題 C: データ構造 - AtCoder Regular Contest 033 | AtCoder 解法 @kenkoooo BITには二分探索というテクがあるそうです(受け売りhttps://t.co/VM8Y0DxGUz— CodeVS本戦通過ラインの境界 (@btk15049) 2016, 3月 8lower_bound() 搭載 Binary Indexed Tree (BI…
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>…
問題 I: 支配と友好 - 東京大学プログラミングコンテスト2013 | AtCoder 解法 2回オイラーツアーするだけ。勝手に根が0だと思い込んで（しかもサンプルがそれで合う）メッチャハマった。 コード #include <bits/stdc++.h> using namespace std; typedef long long ll; const</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>…
問題 E: 宝くじ - 東京大学プログラミングコンテスト2014 | AtCoder 解法 yosupo 先生のコードを写経した。Trie 木を作って、その桁で終わるくじの当選金と、その桁より後ろの桁で終わるくじの当選金の最高値をそれぞれのノードに持たせる。 コード #include <bits/stdc++.h></bits/stdc++.h>…
問題 D: 閉路 - AtCoder Beginner Contest 014 | AtCoder 解法 AtCoder Beginner Contest 014 解説LCA のライブラリを蟻本から写経。 コード #include <bits/stdc++.h> using namespace std; typedef signed long long ll; class LCA { private: LCA() {} vector<vector<int>> G; vector<vector<int></vector<int></vector<int></bits/stdc++.h>…
問題 G: ケンドー - 京都大学プログラミングコンテスト2015 | AtCoder 解法 Bは昇順でソートされているので後ろから見ていき、B[i]より大きいAの中で最も右側にあるものをB[i]と戦わせていけば良い。 i を回して、 Priority Queue に毎回 B[i] 以上のA を入…
問題 abc033.contest.atcoder.jp 解法 ある一点 I を決め、その点を原点として他の点を仰角でソートする。I と他の一点 J を選んだ時に、角 KIJ が鋭角となるような点 K はしゃくとり法によって求められる。発想自体はこれに近い気がする↓ kenkoooo.hatenabl…
問題 discovery2016-qual.contest.atcoder.jp 解法 DDPC 2016 予選 解説 from AtCoder Inc. www.slideshare.net解説スライドの通り、出来るだけ前の方をaで埋めて、置換しきれない分は辞書順最小の接尾辞を探している。接尾辞を探すのは Suffix Array ではな…
問題 tkppc.contest.atcoder.jp 解法 動的計画法で後ろから数字の桁数を決めていく。この時、s[i, k] と s[j, k] の文字列の大小関係を比較したいが、普通にやるとO(N)かかってしまう。そこでSA-ISを使うのが想定解法っぽい。 mayokoex.hatenablog.comが、SA…
問題 indeednow-finala-open.contest.atcoder.jp 解法 木DP。 コード #include <cstdio> #include <iostream> #include <sstream> #include <fstream> #include <iterator> #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></iterator></fstream></sstream></iostream></cstdio>
問題 code-festival-2015-morning-hard.contest.atcoder.jp 解法 1回もひっくり返されない区間iが存在する。この時、区間i-jと区間i+jは、それぞれj回ひっくり返されるので、ある区間を選んだ時にひっくり返される合計の回数は累積和で予め計算しておくこと…
問題 abc015.contest.atcoder.jp 解法 DP コード #include <cstdio> #include <iostream> #include <sstream> #include <fstream> #include <iomanip> #include <algorithm> #include <cmath> #include <string> #include <vector> #include <list> #include <queue> #include <stack> #include <set> #include <map> #include </map></set></stack></queue></list></vector></string></cmath></algorithm></iomanip></fstream></sstream></iostream></cstdio>
問題 arc046.contest.atcoder.jp 解法 AtCoder Regular Contest 046 from AtCoder Inc. www.slideshare.net組み合わせを高速に求める数論ライブラリを手に入れた。 コード #include <iostream> #include <algorithm> #include <vector> #include <queue> #include <set> #include <map> using namespace std</map></set></queue></vector></algorithm></iostream>…
問題 arc046.contest.atcoder.jp 解法 AtCoder Regular Contest 046 from AtCoder Inc. www.slideshare.net コード #include <iostream> #include <algorithm> #include <vector> #include <queue> #include <set> #include <map> using namespace std; int main() { int N, M; cin >> N >> M; vector<int> men_o</int></map></set></queue></vector></algorithm></iostream>…
問題 code-thanks-festival-2015-open.contest.atcoder.jp 解法 ダイクストラやるだけ。 コード #include <cstdio> #include <cmath> #include <cstring> #include <ctime> #include <iostream> #include <algorithm> #include <set> #include <vector> #include <tuple> #include <sstream> #include <typeinfo> #include <fstream> #include…</fstream></typeinfo></sstream></tuple></vector></set></algorithm></iostream></ctime></cstring></cmath></cstdio>
問題 code-thanks-festival-2015-open.contest.atcoder.jp 解法 2次元の累積和をとる。こうすると長方形の中の累積和がO(1)で得られる。kenkoooo.hatenablog.com後はしゃくとりする。 コード ライブラリはmamekinさんのコピペです。 #include <cstdio> #include <iostream> #in</iostream></cstdio>…
問題 code-festival-2015-qualb.contest.atcoder.jp 解法 塗り終わった区間の[始点, 終点]を保持しおく。塗るときに合併される区間がある場合は合併していけば、保持する情報も少なくて済む。これのイメージで解いた↓kenkoooo.hatenablog.com コード import …
問題 C: 転倒距離 - AtCoder Regular Contest 043 | AtCoderarc043.contest.atcoder.jp 解法 最初に転倒数を求めて、それの1/2だけ転倒するようにバブルソートする。バブルソートに一部は Binary Indexed Tree を使うと高速化できる。 コード import java.ut…
問題 D: 金塊ゲーム - AtCoder Beginner Contest 008 | AtCoderabc008.contest.atcoder.jp 解法 AtCoder Beginner Contest 008 解説 from AtCoder Inc. www.slideshare.netいわゆるメモ化再帰。w1 コード import java.util.HashMap; import java.util.Scanne…
問題 C: 辞書式順序ふたたび - AtCoder Beginner Contest 009 | AtCoderabc009.contest.atcoder.jp 解法 前の方から貪欲に決めていく。 コード import java.util.Arrays; import java.util.Scanner; public class Main { public void solve() { Scanner scan…
問題 C: 天下一美術館 - 天下一プログラマーコンテスト2015予選A | AtCodertenka1-2015-quala.contest.atcoder.jp 解法 http://tenka1.klab.jp/2015/explain/quala_c.htmltenka1.klab.jp隣り合った2マスが両方Bと違い、かつ、入れ替えればBと一致する場合、…
問題 B: アリの高橋くん - AtCoder Regular Contest 042 | AtCoderarc042.contest.atcoder.jp 解法 幾何ライブラリ貼るだけ。 コード import java.util.Scanner; public class Main { public void solve() { Scanner scanner = new Scanner(System.in); int …
