問題 D: プレゼント - AtCoder Beginner Contest 038 | AtCoder 解法 最終的に重なった箱たちを内側から見た時、縦と横はそれぞれhとwの増加数列になっているはずである。このことから、もしhとwがそれぞれすべて異なる値で構成されている場合、ソートしてLI…

問題 Problem - E - Codeforces 解法 K=0 のときや、'?' が含まれるときは場合分けでなんとかなる。'?' が含まれず、Kが0でない時を考える。がx-kで割り切れるとき、f(k)=0 だから、 である。 よって、より はkの倍数である。 とおいて全体をkで割ると、 よ…

問題 Problem - D - Codeforces 解法 筋肉ダイクストラ コード #include <bits/stdc++.h> using namespace std; template <class T, class U> void chmin(T &t, U f) { if (t > f) t = f; } typedef tuple<int, int, int, int> P; // dist, layer, h,w const int INF = 1e9, LAYERS = 4; const int RIGHT = 0, LEFT</int,></class></bits/stdc++.h>…

問題 C: 鯛焼き - AtCoder Regular Contest 054 | AtCoder 解法 http://arc054.contest.atcoder.jp/data/arc/054/editorial.pdf コード #include <bits/stdc++.h> using namespace std; int64_t extgcd(int64_t a, int64_t b, int64_t &x, int64_t &y) { int64_t d = a; if </bits/stdc++.h>…

解法 dp[sum][m] := m個の相異なる非負整数からなる合計がsumとなる増加数列の個数。 この並び方は m! 通りある。 さらにこの数列の上に blocks 個の M の倍数を積んでいく時、重複組合せより通りある。逆元から組み合わせを求めるテクを使うと大きい数字に…

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

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

C. Money Transfers Problem - C - Codeforces 解法 合計すると0になる連続部分列をできるだけ多くすれば良い。 コード #include <bits/stdc++.h> using namespace std; template <class T, class U> void chmax(T &t, U f) { if (t < f) t = f; } int main() { cin.tie(0); ios::sync_with_st</class></bits/stdc++.h>…

問題 No.372 It's automatic - yukicoder 解法 DP コード #include <bits/stdc++.h> using namespace std; const int64_t MOD = 1e9 + 7; int main() { cin.tie(0); ios::sync_with_stdio(false); string inS; cin >> inS; int N = inS.size(); vector<int> S(N); for (int i = 0</int></bits/stdc++.h>…

問題 No.371 ぼく悪いプライムじゃないよ - yukicoder 解法 必要な素数をエラトステネスのふるいで全列挙しておく。列挙した素数を大きい方から見ていき、その素数が解答の最小の素因数になりうるかを考える。見ている素数をprime[i]とするとき、[L, H] に含…

C. Recycling Bottles Problem - C - Codeforces 問題 2次元平面で Adil が (ax, ay) に、Bera が (bx, by) にいる。ゴミ箱が (tx, ty) にあり、ゴミが散らばっている。2人は以下の操作を繰り返す。 落ちているゴミを選び、そこまで行く。 ゴミを拾い、ゴミ…

問題 Dashboard - Round 1C 2016 - Google Code Jam 解法 閉路があると無限ループしてしまうので、求めるグラフはDAGである。よってビル番号の小さい方から大きい方へ移動することにする。1〜N-1とBのN個の頂点で可能な辺を全て張ってDAGを作ると、1からBへ…

問題 Problem - D - Codeforces 解法 埋め込み コード #include <bits/stdc++.h> using namespace std; int main() { cin.tie(0); ios::sync_with_stdio(false); int N, K; cin >> N >> K; int a, b, c, d; cin >> a >> b >> c >> d; vector<bool> used(N + 1, false); used[a] = </bool></bits/stdc++.h>…

問題 Problem - F - Codeforces 解法 含むべき部分文字列以外の部分は、残った数字でできるだけ小さい整数を作れば良い。求めるべき文字列は3つのうちのいずれかである。 含むべき部分文字列をTとすると、 Tを先頭に含むもの。 Tの1桁目の数字をqとした時に…

問題 Problem - E - Codeforces 解法 愚直シミュレーション コード #include <bits/stdc++.h> using namespace std; string S; map<int, int> tree_map; int dfs(int pos) { if (pos == S.size()) return pos; if (S[pos] == '(') { int right = dfs(pos + 1); tree_map[pos] = right;</int,></bits/stdc++.h>…

問題 Dashboard - Round 1B 2016 - Google Code Jam 解法 一意に定まる。 コード #include <bits/stdc++.h> using namespace std; string solve(const string &S) { map<int, int> cnt; for (int i = 0; i < S.size(); ++i) cnt[S[i]]++; vector<int> ans(10, 0); ans[0] = cnt['Z']; ans[2</int></int,></bits/stdc++.h>…

問題 Dashboard - Round 1B 2016 - Google Code Jam 解法 幅優先 コード #include <bits/stdc++.h> using namespace std; string solve(const string &S, const string &T) { int N = S.size(); queue<tuple<int, int64_t, int64_t>> que; que.emplace(0, 0, 0); vector<tuple<int64_t, int64_t, int64_t>> ans; while (!que.empty())…</tuple<int64_t,></tuple<int,></bits/stdc++.h>