GoogleCodeJam

Google Code Jam 2019 Round 1B - Fair Fight

問題 codingcompetitions.withgoogle.com数列 が与えられる。 となるような (l, r) の組の数を求めよ。 解法 となるような (l, r) の組の数を求めて全体から引くことにする。 と は c と d を入れ替えることで独立に同じように求めることができる。各 i につ…

Google Code Jam 2019 Round 1B - Draupnir

問題 codingcompetitions.withgoogle.com要素数 6 の数列 がある。クエリとして D を出力すると、 が与えられる。クエリを 2 回投げた後に を出力せよ。 解法 は入力を 64bit 整数に収めるためのものではなく、解法の重要なポイントになる。D=200 で得られる…

GCJ 2016 Round 2 B: Red Tape Committee

問題 Dashboard - Round 2 2016 - Google Code Jam 解法 Bは K-1 個選んだ状態でもう一つの確率を p とすると答えは p の一次式だから端っこで最大になるはずで、だから両端から見れば良い、と思って書いて、あとになって示せてない気がしたけどやっぱり示せ…

GCJ 2016 Round 1C B: Slides!

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

GCJ 2016 Round 1B A: Getting the Digits

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

GCJ 2016 Round 1B B: Close Match

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

GCJ 2016 Round 1A C: BFFs

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

GCJ 2016 Round 1A B: Rank and File

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

GCJ 2016 Round 1A A: The Last Word

問題 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 が成り立たなければならない。…

GCJ 2016 Qualification Round D: Fractiles

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

GCJ 2016 Qualification Round C: Coin Jam

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

GCJ 2016 Qualification Round B: Revenge of the Pancakes

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

GCJ 2016 Qualification Round A: Counting Sheep

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