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

解法 DP + 筋肉 コード #include <algorithm> #include <cmath> #include <cstdio> #include <cstring> #include <ctime> #include <fstream> #include <iostream> #include <set> #include <sstream> #include <typeinfo> #include <vector> using namespace std; string dp[51][51][51][7], tmp[51][51][51][7]; const int AA = …</vector></typeinfo></sstream></set></iostream></fstream></ctime></cstring></cstdio></cmath></algorithm>

Easy: KeyDungeonDiv2 #include <algorithm> #include <cmath> #include <cstdio> #include <cstring> #include <ctime> #include <fstream> #include <iostream> #include <set> #include <sstream> #include <typeinfo> #include <vector> using namespace std; class KeyDungeonDiv2 { public: int countDoors(vector</vector></typeinfo></sstream></set></iostream></fstream></ctime></cstring></cstdio></cmath></algorithm>

問題 Problem - E - Codeforces 解法 各xについて独立に考えることができる。各xについてtを座標圧縮して、Fenwick Tree を使って管理する。 コード #include <bits/stdc++.h> using namespace std; template <typename T> void uniq(vector<T> &v) { v.erase(unique(v.begin(), v.end()), </t></typename></bits/stdc++.h>…

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

問題 Dashboard - Round 1A 2016 - Google Code Jam 解法 親友関係を有向グラフとして考える。頂点kの連結成分はk本の有向辺を持つため閉路を一つだけ含む。この閉路を構成する頂点数が2の時、これらは輪になって並べる時のパーツとして使うことができる。閉…

解法 NをYにするのは意味が無いので、YをNにすることだけ考える。各spellを覚えたかどうかをビットマスクで管理し、新しくスペルを覚えるのに潰さなければならないYの個数をコストとしてダイクストラする。 コード #include <bits/stdc++.h> using namespace std; typedef p</bits/stdc++.h>…

問題 Dashboard - Round 1A 2016 - Google Code Jam 解法 あるiについて、(0, 0)と(i, i) を頂点とする正方形を作ると、必ず(i, i)が正方形の中で最大値になる。この性質を利用する。 コード #include <bits/stdc++.h> using namespace std; typedef long long ll; template <class T, class U></class></bits/stdc++.h>…

問題 Dashboard - Round 1A 2016 - Google Code Jam 解法 S[0]〜S[N-1] を並び替えるとき、S[0]から見て外側にあるほどS[i]のiは大きくなる。ちゃんと書くと、最終的な単語の先頭部分 S[i]S[j]S[k]...S[0] においてi>j>k>...>0 が成り立たなければならない。…

コード #include <algorithm> #include <cassert> #include <cmath> #include <cstdio> #include <cstring> #include <ctime> #include <fstream> #include <iostream> #include <set> #include <sstream> #include <typeinfo> #include <vector> using namespace std; typedef long long ll; class WolfPackDivTwo { int dist…</vector></typeinfo></sstream></set></iostream></fstream></ctime></cstring></cstdio></cmath></cassert></algorithm>

問題 Dashboard - Qualification Round 2016 - Google Code Jam 解法 2世代目のパネルには、1枚を見るだけで1世代目のパネルの1枚目と2枚目を同時に調べられるパネルがある。同様に、3世代目には1世代目のパネルを3枚同時に調べられるパネルがある。このよう…

問題 Dashboard - Qualification Round 2016 - Google Code Jam 解法 愚直にやる。N=16の答えを2つ並べるとN=32の答えになる。 コード #include <bits/stdc++.h> using namespace std; typedef long long ll; ll generate(ll mask, ll b) { ll ans = 0; ll a = 1; while (ma</bits/stdc++.h>…

問題 Dashboard - Qualification Round 2016 - Google Code Jam 解法 ある区間について、その区間をすべて '-' あるいは '+' に出来るかどうかを考える。 コード #include <bits/stdc++.h> using namespace std; typedef long long ll; string turn(const string &S) { stri</bits/stdc++.h>…

問題 Dashboard - Qualification Round 2016 - Google Code Jam 解法 愚直 コード #include <bits/stdc++.h> using namespace std; typedef long long ll; ll solve(ll M) { vector<bool> check(10, false); for (int i = 1; i < 100000000; ++i) { ll N = M * i; while (N > 0) {</bool></bits/stdc++.h>…

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

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

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

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

問題 https://community.topcoder.com/stat?c=problem_statement&pm=14214 解法 Gomory-Hu 木が作れることからGomory-Hu 木が作れることは明らか。 kyuridenamida先生のコードを写経した。 コード #include <bits/stdc++.h> using namespace std; struct UnionFind { vector<int></int></bits/stdc++.h>…

解法 当たりそうなところだけを持っていればおk コード #include <algorithm> #include <cassert> #include <cmath> #include <cstdio> #include <cstring> #include <ctime> #include <fstream> #include <iostream> #include <iterator> #include <map> #include <set> #include <sstream> #include <typeinfo> #include <vector> using namespace…</vector></typeinfo></sstream></set></map></iterator></iostream></fstream></ctime></cstring></cstdio></cmath></cassert></algorithm>

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