Firebaseをandroidアプリに追加したときにつまずいたポイント


androidアプリにFirebaseを追加する

これは、Firebaseコンソールから行う。

名前や鍵を設定し、google-services.jsonをダウンロードし、所定の位置に置く。
その後、gradleファイルを変更する。

app_name/app/src/build.gradleを以下のように変更。

dependencies {
  ...
  compile 'com.google.firebase:firebase-core:11.8.0'
  ..
}
apply plugin: 'com.google.gms.google-services'

app_name/build.gradleを以下のように変更。

buildscript {
  ...
  dependencies {
    ...
    classpath 'com.google.gms:google-services:3.2.0'
  }
}

次に、画面上側のオレンジのバーのSyncをクリックする。
しかし、エラー。

Failed to resolve: com.google.firebase:firebase-core:9.0.0

解決策

app_name/build.gradleを以下のように変更。

allprojects {
    repositories {
        jcenter()
        maven {
            url "https://maven.google.com"
        }
    }
}

File google-services.json is missing. The Google Services Plugin cannot function

解決策

google-services.jsonは、app_name直下ではなく、app_name/appに置く。

しかし、エラー。

No matching client found for package name '〇〇'

解決策

app_name/app/google-services.jsonの以下の部分を変更。

"client": [
{
  "client_info": {
    "mobilesdk_app_id": "9:99999999:android:9ccdbb6c1ae659b8",
    "android_client_info": {
      "package_name": " ここを一致させる "
    }
  }
}

com.exampleになっていたので、正しいものに変更する。

技術室奥プログラミングコンテスト E - 不可視境界線 (The Invisible Borderline)


E - 不可視境界線 (The Invisible Borderline)

問題概要

辺にコストがある木が与えられる。
各頂点から最も遠い点を求めよ。

考察

木の直径を用いて解を求めることを考えます。

f:id:noy72:20180111095259p:plain:w500

まず、最長パス p_0, p_1, p_2, ... , p_k を求めます。
赤い部分は最長パスに含まれることを表しています。

すると、最長パスに含まれる頂点と、最長パスに含まれない部分木に分けることができます。

最長パスに含まれる頂点 p_i の最遠点

p_0 から p_i までの距離と、 p_i から p_k の距離を比較すれば良いです。

部分木に含まれる頂点の最遠点

ある部分木 s_{p_i} に含まれる全ての頂点の最遠点は、 p_i の最遠点と一致します。
一致しないと仮定すると、最長パスであることと矛盾します。

  • 最長パスの一部を含まないようなパスよりも、含むパスの方が必ず長くなる。
  • 最長パスの一部を経由して別の部分木に入るようなパスよりも、入らないパスの方が必ず長くなる。


最遠点が複数ある場合は、頂点番号が小さいものを出力しなければいけないので、そこだけ注意します。

コード

※最長パスが複数ある場合を考えていないのにACしたコード

  1. bfsで最長パスを求める
  2. 最長パスに含まれている頂点の最遠点を求める
  3. 部分木を求める
  4. 部分技に含まれる頂点の解を求める
  5. 出力
#include<bits/stdc++.h>
#define range(i,a,b) for(int i = (a); i < (b); i++)
#define rep(i,b) for(int i = 0; i < (b); i++)
#define all(a) (a).begin(), (a).end()
#define show(x)  cerr << #x << " = " << (x) << endl;
using namespace std;

#define int long long
const int INF = (1LL << 60);

const int MAX_V = 100005;

class Edge{
	public:
		int to, dis;
		Edge(){}
		Edge(int to, int dis): to(to), dis(dis)  {}
};

vector<Edge> g[MAX_V];
int dis[MAX_V];

vector<int> bfs(int s, int n, bool f){
	queue<int> q;

	rep(i,n) dis[i] = INF;
	dis[s] = 0;
	q.push(s);

	vector<int> pre(n,-1);
	while(not q.empty()){
		int d = q.front(); q.pop();

		rep(i,g[d].size()){
			Edge e = g[d][i];
			if(dis[e.to] == INF){
				pre[e.to] = d;
				dis[e.to] = dis[d] + e.dis;
				q.push(e.to);
			}
		}
	}

	int maxi = -1;
	rep(i,n){
		if(dis[i] == INF) continue;
		if(maxi == -1) maxi = i;
		if(dis[maxi] < dis[i]){
			maxi = i;
		}
	}
	if(f) return vector<int>() = {maxi};

	vector<int> path = {maxi};
	while(pre[maxi] != -1){
		maxi = pre[maxi];
		path.emplace_back(maxi);
	}
	reverse(all(path));
	return path;
}

//---------------------------- union-find
int par[MAX_V]; //親
int depth[MAX_V];//木の深さ

void init(int n){
	rep(i,n){
		par[i] = i;
		depth[i] = 0;
	}
}

int find(int x){
	if(par[x] == x){
		return x;
	}else {
		return par[x] = find(par[x]);
	}
}

void unite(int x, int y){
	x = find(x);
	y = find(y);
	if(x == y) return;

	if(depth[x] < depth[y]){
		par[x] = y;
	}else{
		par[y] = x;
		if(depth[x] == depth[y]) depth[x]++;
	}
}

bool same(int x, int y){
	return find(x) == find(y);
}
//----------------------------

signed main(){
	int n;
	cin >> n;

	vector<pair<int, int>> e(n - 1);
	rep(i,n - 1){
		int a, b, c;
		cin >> a >> b >> c;
		a--; b--;
		e[i] = make_pair(a,b);
		g[a].emplace_back(b,c);
		g[b].emplace_back(a,c);
	}

	vector<int> path = bfs(bfs(0, n, 1).front(), n, 0); //最長パスを求める
	vector<bool> used(n,0);
	vector<int> ans(n);
	for(auto i : path){
		used[i] = true;
		if(dis[i] > dis[path.back()] - dis[i]){
			ans[i] = path.front();
		}else if(dis[i] < dis[path.back()] - dis[i]){
			ans[i] = path.back();
		}else{
			ans[i] = min(path.front(), path.back());
		}
	}

	init(n);
	rep(i,n - 1){ //部分木を求める
		if(used[e[i].first] and used[e[i].second]) continue;
		unite(e[i].first, e[i].second);
	}

	vector<int> par(n);
	for(auto i : path){
		par[find(i)] = ans[i];
	}
	rep(i,n){
		if(used[i]) continue;
		ans[i] = par[find(i)];
	}

	for(auto& i : ans){
		cout << i + 1 << endl;
	}
}

ARC 088 E - Papple Sort


E - Papple Sort

公式解説が賢かった(レート1600並感)。

問題概要

英小文字からなる文字列 S が与えられる。
隣り合う 2 つの文字をスワップできる。
S を回文にするためのスワップの最小回数を求める。
回文にできない場合は −1 を出力する。

考察

  • 回文なので、文字列を半分に分けて考えそう。
  • 左右どちらの文字列に合わせて回文にすれば良いのかわからない。
  • 外側から貪欲に決めれば最小回数になりそう(適当) 
外側から決める方法

以下、スワップする回数をコストと呼ぶ。

回文;????????
余り;ataatmma

回文を a??????a にするとき、必要なコストは0。
回文を t??????t にするとき、必要なコストは4。
回文を m??????m にするとき、必要なコストは6。
よって、a??????a にするのが最善。

回文:a??????a
余り:taatmm

同様に、
aa????aa にするとき、コスト4。
at????ta にするとき、コスト2。
am????ma にするとき、コスト4。
よって、at????ta にするのが最善。

これを繰り返す。

回文:at????ta
余り:aamm

回文:ata??ata
余り:mm

回文:atammata
余り:

計算量

  • 外側の文字を決める O(26)
  • 外側を決めうちしたとき、必要なコストを求める O(log |S|)

各英小文字につき、何番目に出てくるかを前計算しておき、最も小さい値と最も大きい値(外側に近い)を参照すればよい(前計算 O(|S|)、本計算O(1))。
ただし、「余り」文字列において何番目に現れたかを持っていなければ、コストが計算できない。
そのため、セグ木(BIT)を使って何番目かを再計算する必要がある。
よって、O(log |S|)となる。

  • 回文を構築する O(|S|)

したがって、O(26 * |S| log |S|)

実装

#include<bits/stdc++.h>
#define range(i,a,b) for(int i = (a); i < (b); i++)
#define rep(i,b) for(int i = 0; i < (b); i++)
#define all(a) (a).begin(), (a).end()
#define show(x)  cerr << #x << " = " << (x) << endl;
const int INF = 1e8;
using namespace std;

const int MAX_N = 200005;

//[1, n]
int bit[MAX_N + 1] = {0};

int sum(int i){
	int s = 0;
	while(i > 0){
		s += bit[i];
		i -= i & -i;
	}
	return s;
}

void add(int i, int x){
	while(i <= MAX_N){
		bit[i] += x;
		i += i & - i;
	}
}

bool impossible(vector<vector<int>> v){
	int odd = 0;
	rep(i,26){
		if(v[i].size() % 2) odd++;
	}
	return odd >= 2;
}

int main(){
	string s;
	cin >> s;

	vector<vector<int>> v(26); // 各英小文字が何番目に現れるか
	rep(i,s.size()){
		v[s[i] - 'a'].emplace_back(i);
	}
	if(impossible(v)){
		cout << -1 << endl;
		return 0;
	}

	pair<int, int> p[26];
	rep(i,26) p[i] = make_pair(0, v[i].size() - 1); //front, back

	int len = s.size() - 1;
	long long ans = 0;
	rep(i,s.size() / 2){
		int t;
		int minCost = INF;
		rep(j,26){
			if(v[j].size() <= 1) continue;

			int front, back;
			tie(front, back) = p[j];
			if(front >= back) continue;

			int front_p = v[j][front];
			int back_p = v[j][back];

			int left = front_p - sum(front_p + 1); //  「余り」文字列の何番目に現れるか
			int right = back_p - sum(back_p + 1);

			int cost = left + (len - right); // 'a' + j を外側に移動させるコスト
			if(minCost > cost){
				minCost = cost;
				t = j;
			}
		}

		ans += minCost;
		add(v[t][p[t].first] + 1, 1);
		add(v[t][p[t].second] + 1, 1);
		p[t].first++;
		p[t].second--;
		len-=2;
	}

	cout << ans << endl;
}

Indeed study session に競プロ的な愚直解コードを投げてしまった話

Indeed study session に参加して思ったこと。

Indeed study sessionとは

提出したコードをレビューしてもらえる勉強会。
書いたコードについて色々言ってもらえる。

ちなみに2次募集の締め切りが 12/20 です。

学んだこと

競プロの気持ちでやってはダメだよ

競プロをやる気持ちで書いたコードを投げてはいけない(それはそう)。

無駄な部分は減らそう

AC or TLE で考えると無意味な高速化もちゃんとやらないといけない。

競プロ的に丁寧に書いても読めない

競プロの丁寧は、読めないを読めるようにはしない。

includeを減らす

いらない部分は消す。

参照渡しを使う

for(auto &i : data) とか。
競プロ的にはあまり変わらなくても、無駄は減らす。

using namespace stdはダメ

それはそう。

感想

コードレビューに使うコードは90分で書く必要がある。
簡単に言えば、一問だけの90分コンテスト。
解法が思いつかず、時間ギリギリに愚直解で書いたのが悪かった。
自明に高速化できる部分が多々あった。それでもTLEにはかわりないが。

このような形式であれば、さっさと見切りをつけて部分点解法を書く気持ちで取り掛かった方が良いかもしれない。
アルゴリズムの部分はほぼ触れられていないので、考える部分を間違えた感がある(それはそう)。

コードをきっちりかかないと、それだけレビューの内容も薄くなってしまう。
つめるところはきっちりとつめよう。

全体的に”それはそう”という感想しか出てこない。

dein.vimとdeopleteをmacにインストールする。

環境

暗黒のVimmer(見習い)

dein.vim

github.com

dein.vimは暗黒のプラグインマネージャです。
元々neobundleを使っていましたが、後継が1.5年前に出ているのでさすがに乗り換えました。

インストール

githubのQuick start、dein.vimのインストール自体にハマってしまったメモ - Qiitaを参照。

1、Run below script.

$ curl https://raw.githubusercontent.com/Shougo/dein.vim/master/bin/installer.sh > installer.sh
$ sh ./installer.sh {specify the installation directory}

これを実行すると、最後に「今表示したscriptをvimrcに貼り付けてね(意訳)」と表示されるので見逃さずに貼り付けましょう(1敗)。

" If you want to install not installed plugins on startup.
if dein#check_install()
  call dein#install()
endif

この部分のコメントアウトを外して起動時にインストールするようにします。

You can specify revision/branch/tag.
call dein#add('Shougo/deol.nvim', { 'rev': 'a1b5108fd' })

vim8だとこの部分で deol.nvim requires Neovim と言われます。
, { 'rev': 'a1b5108fd' } の部分を消して、deol.nvimを削除、その後インストールすれば使えます。

deoplete.nvim

github.com

自動補完プラグイン

インストール

vimrcに以下を記述。
C++の補完のため、deoplate-clangもインストールする。
GitHub - deoplete-plugins/deoplete-clang: deoplete.nvim source for C/C++/Obj-C/Obj-C++ with clang-python3

brew install cmake
brew install llvm --with-clang

必要なものを揃える。

call dein#add('Shougo/deoplete.nvim')
call dein#add('zchee/deoplete-clang')
if !has('nvim')
  call dein#add('roxma/nvim-yarp')
  call dein#add('roxma/vim-hug-neovim-rpc')
endif

上記をvimrcに追加。

g:deoplete#sources#clang#libclang_path
g:deoplete#sources#clang#clang_header

この二つの設定は必須です。
libclang_pathにはlibclang.dylibへのpath、clang_headerはclangディレクトリへのpathです。
libclang_pathと同じディレクトリにclangのディレクトリがあれば、それへのpathをclang_headerにします。


denite.vimはうまく動かないので諦めました。

AtCoder Beginner Contest D問題ジャンル分け


行列累乗

D - 漸化式

フロー

D - 浮気予防

数学(組み合わせの計算など)

D - 大ジャンプ
D - 多重ループ
重複組み合わせ

D - 動的計画法
D - 乱数生成
確率

D - Maximum Average Sets

ダブリング

D - 阿弥陀
別解:巡回置換

セグメントツリー | Binary Indexed Tree

D - プレゼント

シミュレーション

D - へんてこ辞書

ARC016 - C ソーシャルゲーム


問題概要

商品が n 種類、くじが m 種類あります。
くじを一度引くのにお金がかかります。
くじからは、ある確率である商品が手に入ります。

最善を尽くしたとき、全ての商品を集める金額の期待値を求めてください。

考えたこと

期待値についてはこちら 期待値と条件付確率 - math314のブログ
問題文についてはこちら ARC016-C「ソーシャルゲーム」 の記事が非常に参考になります。

こちら 期待値と条件付確率 - math314のブログ の記事で例として挙げられているコイントスの期待値についてです。
頂点の値が、連続で表が出た回数を示しています。
青矢印が表が出たことを、橙矢印が裏が出たことを表しています。
期待値はこのように状態の遷移から式を立てることができます。
f:id:noy72:20171027164545j:plain:w500

単純なくじで、期待値を求める式を立ててみます。
E は、その状態から全ての商品を集めるためにくじを引く回数を表しています。

頂点の値は、商品の入手を bit で表しています。
00 の状態からそれぞれ 10, 01 の状態へ遷移し、最後は 11 となります。
11 は全て揃った状態でありこれ以上はくじを引く必要がないため E_11 = 0 です。
10 の状態から 11 になるに 1 番目の商品を引かなければなりません。
このとき、 5% の確率で引けるので、くじを引く回数の期待値は 100 / 5 回です。
もう片方は 95% なので、 100 / 95 回です。

00 からは 5% の確率で 01 になり、 01 からは 100 / 95 回で全て揃います。
また、 95% の確率で 10 になり、 10 からは 100 / 5 回で全て揃います。
これで、 00 から 11 までの期待値が計算できました。
f:id:noy72:20171027164552j:plain:w500

式を実際に立ててみると、後ろから計算することで解がわかることに気付けます。
f:id:noy72:20171027164617j:plain:w500
f:id:noy72:20171027164624j:plain:w500
f:id:noy72:20171027164641j:plain:w500
あとは式を計算できるように実装します。

実装

sum が自分自身に返ってこない場合の期待値を表しています。
100 / (100 - k) が自分自身に返ってくる確率の逆数(期待値)を表しています。

手計算した式をどうにか実装したらうまくいった、という感じです。

#include<bits/stdc++.h>
#define range(i,a,b) for(int i = (a); i < (b); i++)
#define rep(i,b) for(int i = 0; i < (b); i++)
#define all(a) (a).begin(), (a).end()
#define show(x)  cerr << #x << " = " << (x) << endl;
const int INF = 1e8;
using namespace std;

//i番目のビットを返す
bool getBit(int num, int i){
	return ((num & (1 << i)) != 0);
}

//i番目を1にする
int setBit(int num, int i){
	return num | (1 << i);
}

int main(){
	int n, m;
	cin >> n >> m;

	vector<int> c(m), cost(m);
	vector<vector<pair<int, int>>> kuji(m); //番号、確率
	rep(i,m){
		cin >> c[i] >> cost[i];
		rep(j,c[i]){
			int a, b;
			cin >> a >> b;
			a--;
			kuji[i].emplace_back(a,b);
		}
	}

	double dp[1 << 10];
	rep(i,1 << 10) dp[i] = INF;
	dp[(1 << n) - 1] = 0;

	for(int s = (1 << n) - 1; s >= 0; s--){
		rep(i,m){
			double sum = cost[i], k = 0;
			for(auto j : kuji[i]){
				if(not getBit(s, j.first)){
					sum += dp[setBit(s, j.first)] * j.second / 100.0;
				}else{
					k += j.second;
				}
			}
			dp[s] = min(dp[s], sum * 100.0 / (100 - k));
		}
	}

	cout << fixed << setprecision(10) << dp[0] << endl;
}