AtCoder

第2回 ドワンゴからの挑戦状 予選 D: 庭園

問題 D: 庭園 - 第2回 ドワンゴからの挑戦状 予選 | AtCoder 解法 ある高さ h よりも上の部分でできる長方形の最大値と、下の部分でできる長方形の合計を最大化することを考え、hを全て試せば良い。 コード #include <bits/stdc++.h> using namespace std; template <class T, class U> void c</class></bits/stdc++.h>…

第2回 ドワンゴからの挑戦状 予選 C: メンテナンス明け

問題 C: メンテナンス明け - 第2回 ドワンゴからの挑戦状 予選 | AtCoder 解法 第2回 ドワンゴからの挑戦状 予選 C - メンテナンス明け - うさぎ小屋 コード #include <bits/stdc++.h> using namespace std; typedef pair<int64_t, int> P; int main() { cin.tie(0); ios::sync_with_stdio</int64_t,></bits/stdc++.h>…

AtCoder Regular Contest 052 C: 高橋くんと不思議な道

問題 C: 高橋くんと不思議な道 - AtCoder Regular Contest 052 | AtCoder 解法 (辺Bを通った数, 頂点vまでのコスト) を頂点としてダイクストラする。 コード #include <bits/stdc++.h> using namespace std; typedef tuple<int, int, int> P; // cost, count, vertex int main() { cin.tie(</int,></bits/stdc++.h>…

square869120Contest #2 C: 何通りの分割方法がある?

問題 C: 何通りの分割方法がある? - square869120Contest #2 | AtCoder 解法 文字列が短いので、全ての部分文字列を数字にした時の値を計算しておく。メモ化再帰で 「substr(pos, length) で D 以下になる組み合わせの数」を求めれば良い。 コード #include <bits/stdc++.h></bits/stdc++.h>…

JAG 夏合宿 2015 Day2 G: Escape

問題 G: Escape - Japan Alumni Group Summer Camp 2015 Day 2 | AtCoder 解法 「入ったら頂点1に戻ることができずに確実に終了する点」を列挙する。逆に、これらの点以外の点は常に行き来できるので、その点数は確実に手に入る。あとは戻れない点に設定され…

JAG 夏合宿 2015 Day2 D: 真っ暗な部屋

問題 D: 真っ暗な部屋 - Japan Alumni Group Summer Camp 2015 Day 2 | AtCoder 解法 最初 M 人の人が、それぞれの暗い部屋にいるとする。これらの人たちを全員明るい部屋に連れていくことを考える。各状態について、遷移の仕方がk通りある。全員が暗い部屋…

JAG 夏合宿 2015 Day2 B: 監獄

問題 B: 監獄 - Japan Alumni Group Summer Camp 2015 Day 2 | AtCoder 解法 N回目に [0, k-2] の人は N-1 回目には +1 した位置に、[k-1, 2*k-3] の人は +2 した位置にいるので、遡っていけば良い。 コード #include <bits/stdc++.h> using namespace std; typedef long lo</bits/stdc++.h>…

JAG 夏合宿 2015 Day2 A: 幾何問題を解こう

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

AtCoder Regular Contest 050 D: Suffix Concat

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

東京大学プログラミングコンテスト2014 B: 交点

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

AtCoder Regular Contest 018 C: 席替え

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

AtCoder Beginner Contest 034 D: 食塩水

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

AtCoder Regular Contest 033 C: データ構造

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

Japan Alumni Group Summer Camp 2014 Day 4 F: Longest Match (SA-IS)

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

Japan Alumni Group Summer Camp 2014 Day 4 F: Longest Match

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

東京大学プログラミングコンテスト2013 I: 支配と友好

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

AtCoder Regular Contest 048 D: たこ焼き屋とQ人の高橋君

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

AtCoder Regular Contest 048 C: 足の多い高橋君

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

東京大学プログラミングコンテスト2014 E: 宝くじ

問題 E: 宝くじ - 東京大学プログラミングコンテスト2014 | AtCoder 解法 yosupo 先生のコードを写経した。Trie 木を作って、その桁で終わるくじの当選金と、その桁より後ろの桁で終わるくじの当選金の最高値をそれぞれのノードに持たせる。 コード #include <bits/stdc++.h></bits/stdc++.h>…

AtCoder Beginner Contest 014 D: 閉路

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

京都大学プログラミングコンテスト 2015 G: ケンドー

問題 G: ケンドー - 京都大学プログラミングコンテスト2015 | AtCoder 解法 Bは昇順でソートされているので後ろから見ていき、B[i]より大きいAの中で最も右側にあるものをB[i]と戦わせていけば良い。 i を回して、 Priority Queue に毎回 B[i] 以上のA を入…

AtCoder Beginner Contest 033 D: 三角形の分類

問題 abc033.contest.atcoder.jp 解法 ある一点 I を決め、その点を原点として他の点を仰角でソートする。I と他の一点 J を選んだ時に、角 KIJ が鋭角となるような点 K はしゃくとり法によって求められる。発想自体はこれに近い気がする↓ kenkoooo.hatenabl…

DISCO presents ディスカバリーチャンネル プログラミングコンテスト2016 予選 C: アメージングな文字列は、きみが作る!

問題 discovery2016-qual.contest.atcoder.jp 解法 DDPC 2016 予選 解説 from AtCoder Inc. www.slideshare.net解説スライドの通り、出来るだけ前の方をaで埋めて、置換しきれない分は辞書順最小の接尾辞を探している。接尾辞を探すのは Suffix Array ではな…

技術室奥プログラミングコンテスト G: おおきなかずを作った

問題 tkppc.contest.atcoder.jp 解法 動的計画法で後ろから数字の桁数を決めていく。この時、s[i, k] と s[j, k] の文字列の大小関係を比較したいが、普通にやるとO(N)かかってしまう。そこでSA-ISを使うのが想定解法っぽい。 mayokoex.hatenablog.comが、SA…

Indeed なう A日程 D: Longest Path (木DP)

問題 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 あさぷろ Hard A: 一次元オセロ

問題 code-festival-2015-morning-hard.contest.atcoder.jp 解法 1回もひっくり返されない区間iが存在する。この時、区間i-jと区間i+jは、それぞれj回ひっくり返されるので、ある区間を選んだ時にひっくり返される合計の回数は累積和で予め計算しておくこと…

AtCoder Beginner Contest 015 D: 高橋くんの苦悩

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

AtCoder Regular Contest 046 D: うさぎとマス目

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

AtCoder Regular Contest 046 C: 合コン大作戦

問題 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 G: カメレオン

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