noyのブログ

プログラミングとかゲームとか

AOJ 0110 Alphametic

覆面算 | Aizu Online Judge

概要

A + B = C
という形式で式が与えられる。式の長さは 126 以下である。
与えられる数値にはひとつ以上の X が含まれている。

X0 以上 9 以下の整数である。
X に当てはまる整数を求めよ。当てはまる整数がない場合は NA を出力せよ。

実装

X に当てはまる数値を全探索する。
多倍長整数でなければオーバーフローする。

C++には多倍長整数はない。

ではどうするか。

modを使うのである。

この嘘解法を落とすケースはあるようで、 mod 10^9 + 7 と mod 10^9 + 9 ではWA。
よくわからない大きな素数でmodを取るとACする

#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 long long M = 67280421310721LL;

vector<string> split(string in, char sp = ' '){
	vector<string> ret;
	stringstream ss(in);
	string s;
	while(getline(ss, s, sp)){
		ret.emplace_back(s);
	}
	return ret;
}

void modmod(vector<string> sp, int start){
	range(i,start,10){
		vector<long long> a(3,0);
		rep(j,3){
			for(auto c : sp[j]){
				(a[j] *= 10) %= M;
				if(c == 'X') a[j] += i;
				else a[j] += c - '0';
			}
		}
		if((a[0] + a[1]) % M == a[2] % M){
			cout << i << endl;
			return;
		}
	}
	cout << "NA" << endl;
	return;
}

int main(){
	string s;
	while(cin >> s){
		rep(i,s.size()) if(s[i] == '+') s[i] = '=';
		vector<string> sp = split(s, '=');

		int start = 0;
		for(auto& i : sp) if(i.front() == 'X' and i.size() > 1) start = 1;
		modmod(sp, start);
	}
}

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になっていたので、正しいものに変更する。

コップ本でScala入門 - 2 配列、リストなど

配列

関数型なのに配列を!?

string a[3];
a[0] = "ab";
a[1] = "cd";
a[2] = "ef\n";
for(int i = 0; i < 3; i++){
    cout << a[i];
}
val a = new Array[String](3)
a(0) = "ab"
a(1) = "cd"
a(2) = "ef\n"
for(i <- 0 to 2){
    print(a(i))
}

生成するインスタンスの構成を設定する事をパラメーター化という。
上記の例では、Stringという型パラメーター、3という値パラメーターを設定している。

for式にある to はメソッドである。
詳しく書くと、こうなる。

for(i <- (0).to(2))

数値はIntオブジェクトである。
toというメソッドを呼び出し、Intオブジェクトである2を渡している。
もっというと、すべての演算がメソッド呼び出しである。

val num = Array(1,2,3)

このような初期化もできる。

リスト

配列は変更可能(ミュータブル)であるが、
Scalaのリストは変更不能(イミュータブル)である。
※可変リストもある

val a = List(1,2)
val b = 0 :: a
val c = b ::: a
println(b)
println(c)
出力
List(0, 1, 2)
List(0, 1, 2, 1, 2)

セミコロンで整数をくっつけたり、リストをくっつけたりできる。
Listメソッドにはいろいろある。

その中でも関数言語感を感じるmapの紹介を。

val list = List(1,2,3,4)
println(list.map(a => a * a))
出力
List(1, 4, 9, 16)

リストの各要素に関数を適用する。

タプル

イミュータブルなコンテナオブジェクト。
異なる型の要素を持つ事ができる。

val pair = (1, "a")
val tuple = (1, "a", 3.1)
println(pair._1)
println(tuple._3)
println(tuple)
出力
1
3.1
(1,a,3.1)

ここで、tupleの型はTuple3[Int, String, Double]になっている。

0-indexではないが、これは静的に型付けされたタプルは1から始まるという伝統のためである。

scala> val t = (1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,16,17,18,19,20,21,22)                                             
t: (Int, Int, Int, Int, Int, Int, Int, Int, Int, Int, Int, Int, Int, Int, Int, Int, Int, Int, Int, Int, Int, Int) = (1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,16,17,18,19,20,21,22)

要素をたくさん増やしたくなるが、23個以上はエラーが返ってくる。

集合とマップ

Scalaにはミュータブルなコレクションとイミュータブルのコレクションが区別されている。

イミュータブルなset

var set = Set(1,2,3)
set += 4
println(set.contains(4))
出力
true

setに要素を追加するには+演算子を使う。

イミュータブルなmap

val map = Map(1 -> "a", 2 -> "b", 3 -> "c")
println(map(2))
出力
b

イミュータブルなmapに要素を追加しようとするとエラーが返る。
追加したい場合は、ミュータブルなmapを使う。

test.scala:3: error: value += is not a member of scala.collection.immutable.Map[Int,String]               
Expression does not convert to assignment because receiver is not assignable.                                       
map += (4 -> "a")

Scalaプログラマーに求められる態度

val、イミュータブルオブジェクト、副作用のないメソッドを優先する。
理由があるなら、var、ミュータブルオブジェクト、副作用のあるメソッドを使う。

Haskellは後者を許さない(はず)。一度Haskellに挑戦した事があるが、簡単なコードを書くのにもかなり苦労した。
その点Scalaは融通が利いて良いが、常にJavaとして書いてしまうと関数型言語の考えが身につかないので、うまく使い分ける必要がありそう。

まとめ

  • 配列が使える
  • コレクションはイミュータブルとミュータブルが区別される
  • val、var、イミュータブル、ミュータブルは使い分ける


コップ本でScala入門 - 1 Scalaとは / if、for - noyのブログ
次 ないです

コップ本でScala入門 - 1 Scalaとは / if、for

はじめに

C言語でプログラミングのセンスがあるかどうかはわからないけど、
関数型言語わからないのはセンスがないよねw」

き 僕 教 な
ず の 授 に
つ 心 の げ
け を 冗 な
談 い
◯ ◯

目標

Scalaスケーラブルプログラミング第3版の内容を理解する。
そしてWebアプリケーション開発へ。
多分失踪する。

Scala とは

関数型プログラミング言語である
でもJavaっぽく書くこともできる。
純粋なオブジェクト指向言語関数型言語が両方そなわり最強な静的型付け言語に見える。初心者が使うと逆に頭がおかしくなって死ぬ。

スクリプト言語のように見えたりもする。

ロゴが螺旋階段

言語別給与ランキングでは上位にいる
需要は少ないが、それ以上に供給が少ない(と思っている)。

scalaを選ぶ理由

互換性
簡潔性
高水準
静的な型付け

プログラミング第一歩

変数

val : 代入不可
var : 代入可能

C++で言うところのこれが、

int a = 5;
const int b = 10;

こう。

var a = 5
val b = 10

型推論の機能を持つので、型名を省略することができる。
セミコロンも省略可。

関数

int max(int a, int b){
	if(a > b) return a;
	else return b;
}

max関数の実装。Scalaでは以下のように実装する。

def max(a: Int, b: Int): Int = {
	if(x > y) x
	else y
}

def 関数名 (変数名: 型, ...): 結果型 = {
	関数本体
}

Scalaでは戻り型を結果型という。
また、三項演算子のようにif式が値を返す。

def greet() = println("Hello, world!")

関数のカーリーブラケットは省略可能。
C++ならこのような関数の戻り型はvoidだが、ScalaではUnitという結果型になる。

インクリメント

i++のような書き方はできない。

forループ

argsの要素を一つずつ表示するコードをC++で書くとこうなる。

for(auto arg : args){
	cout << arg << endl;
}

Scalaはこうなる。

for(arg <- args){
	println(arg)
}

数学記号で言う所の(要素 ∈ 集合)が、Scalaの(要素 <- 集合)に当たる。

また、このような書き方もできる。

for_each(args.begin(), args.end(), [](string arg){ cout << arg << endl;});
args.foreach(arg => println(arg))
args.foreach((arg: String) => println(arg))

(変数名: 型, ...) => 関数本体 //関数リテラル


さらに、一個の引数をとる一文からなる関数リテラルの場合、色々略せる。

args.foreach(println)

短い。

実践

A - Product

object Main extends App {
  val in = scala.io.StdIn.readLine.split(" ").map(_.toInt)
  def func(x: Int): String = if (x % 2 == 1) "Odd" else "Even"
  println(func(in(0) * in(1)))
}

ちなみに、

if (x % 2) "Odd" else "Even"  

だとエラーが返ってくる。

まとめ


競技プログラマーが始めるScala - 2 配列、リストなど - noyのブログ

技術室奥プログラミングコンテスト 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にはかわりないが。

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

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

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