AtCoder Beginner Contest 109 に出場した
はじめに
こんばんはtikedaです。
先週の9/8(土)にAtCoderのABC109が開催されたので、久々に出場しました。
最近、競プロのモチベがダダ↓↓↓だったのですが、@chokudaiさんにtweet(以下参照)を「いいね！」されてしまい、出ることに...
もちべあがってきた
— tikeda🐾 (@tikeda_meu) September 8, 2018
今日はAtCoderでるぞい
しかし今回は初めて全完できたので、ドヤ顔して記事を書くことができるのである(は?)
A
問題は以下を参照。
A - ABC333
AとBをかけたものが奇数か偶数かで判定すればよい。
僕のコードは以下で、ACを得た。
//#include <bits/stdc++.h> #include <iostream> #include <complex> #include <sstream> #include <string> #include <algorithm> #include <deque> #include <list> #include <map> #include <numeric> #include <queue> #include <vector> #include <set> #include <limits> #include <cstdio> #include <cctype> #include <cmath> #include <cstring> #include <cstdlib> #include <ctime> #include <climits> #define REP(i, n) for(int i = 0; i < (int)(n); i++) #define FOR(i, j, k) for(int i = (int)(j); i < (int)(k); ++i) #define ROF(i, j, k) for(int i = (int)(j); i >= (int)(k); --i) #define FORLL(i, n, m) for(long long i = n; i < (long long)(m); i++) #define SORT(v, n) sort(v, v+n) #define REVERSE(v) reverse((v).begin(), (v).end()) using namespace std; using ll = long long; const ll MOD=1000000007LL; typedef pair<int, int> P; ll ADD(ll x, ll y) { return (x+y) % MOD; } ll SUB(ll x, ll y) { return (x-y+MOD) % MOD; } ll MUL(ll x, ll y) { return x*y % MOD; } ll POW(ll x, ll e) { ll v=1; for(; e; x=MUL(x,x), e>>=1) if (e&1) v = MUL(v,x); return v; } ll DIV(ll x, ll y) { /*assert(y%MOD!=0);*/ return MUL(x, POW(y, MOD-2)); } int main(void){ int a, b; cin >> a >> b; if( (a*b)%2 == 0){ cout << "No" << endl; } else{ cout << "Yes" << endl; } return 0; }
B
問題は以下を参照。
B - Shiritori
Bのくせに案外難しいめうと思ったが、map使って数える + 文字列のお尻と次の文字列の頭が一致しているか判定するのをすぐ思いつき実装した。実装に、ちょっと時間かかったのが残念なところ。
//#include <bits/stdc++.h> #include <iostream> #include <complex> #include <sstream> #include <string> #include <algorithm> #include <deque> #include <list> #include <map> #include <numeric> #include <queue> #include <vector> #include <set> #include <limits> #include <cstdio> #include <cctype> #include <cmath> #include <cstring> #include <cstdlib> #include <ctime> #include <climits> #define REP(i, n) for(int i = 0; i < (int)(n); i++) #define FOR(i, j, k) for(int i = (int)(j); i < (int)(k); ++i) #define ROF(i, j, k) for(int i = (int)(j); i >= (int)(k); --i) #define FORLL(i, n, m) for(long long i = n; i < (long long)(m); i++) #define SORT(v, n) sort(v, v+n) #define REVERSE(v) reverse((v).begin(), (v).end()) using namespace std; using ll = long long; const ll MOD=1000000007LL; typedef pair<int, int> P; ll ADD(ll x, ll y) { return (x+y) % MOD; } ll SUB(ll x, ll y) { return (x-y+MOD) % MOD; } ll MUL(ll x, ll y) { return x*y % MOD; } ll POW(ll x, ll e) { ll v=1; for(; e; x=MUL(x,x), e>>=1) if (e&1) v = MUL(v,x); return v; } ll DIV(ll x, ll y) { /*assert(y%MOD!=0);*/ return MUL(x, POW(y, MOD-2)); } map<string, int> mp; int main(void){ int n; cin >> n; string s[n]; string p_s; int p_s_l; REP(i, n) cin >> s[i]; REP(i, n){ if( i > 0 && p_s[p_s_l-1] != s[i][0]){ cout << "No" << endl; return 0; } //cout << p_s[p_s_l - 1] << endl; if(mp[s[i]] == 0){ mp[s[i]]++; } else{ cout << "No" << endl; return 0; } p_s = s[i]; p_s_l = p_s.length(); } cout << "Yes" << endl; return 0; }
C
問題は以下を参照。
C - Skip
個人的に一番時間をかけてしまった問題で、難しかっためう + 1WA。 はじめは愚直にシミュレーションしてみた。Xから各y_iに対して距離(差の絶対値)を計算し、ソートした後に、最も近い距離をDの最大値として1ずつ減らしながらシミュレーションを行った。このやり方でACしたという話も聞いたので、自分の実装力の無いが故にどこかしらでバグってWAとなったと思われる。 ここで諦めて頭をつかうことにした。先程の距離を計算する際に、Xと各y_iの距離らの最大公約数が解となることに気づいたので、そのように実装したらACをした。 コーナーケースと思われるn=1の時は、単純にy_0とXの差の絶対値を取るだけで良いので、そのように実装した。
//#include <bits/stdc++.h> #include <iostream> #include <complex> #include <sstream> #include <string> #include <algorithm> #include <deque> #include <list> #include <map> #include <numeric> #include <queue> #include <vector> #include <set> #include <limits> #include <cstdio> #include <cctype> #include <cmath> #include <cstring> #include <cstdlib> #include <ctime> #include <climits> #define REP(i, n) for(int i = 0; i < (int)(n); i++) #define FOR(i, j, k) for(int i = (int)(j); i < (int)(k); ++i) #define ROF(i, j, k) for(int i = (int)(j); i >= (int)(k); --i) #define FORLL(i, n, m) for(long long i = n; i < (long long)(m); i++) #define SORT(v, n) sort(v, v+n) #define REVERSE(v) reverse((v).begin(), (v).end()) using namespace std; using ll = long long; const ll MOD=1000000007LL; typedef pair<int, int> P; ll ADD(ll x, ll y) { return (x+y) % MOD; } ll SUB(ll x, ll y) { return (x-y+MOD) % MOD; } ll MUL(ll x, ll y) { return x*y % MOD; } ll POW(ll x, ll e) { ll v=1; for(; e; x=MUL(x,x), e>>=1) if (e&1) v = MUL(v,x); return v; } ll DIV(ll x, ll y) { /*assert(y%MOD!=0);*/ return MUL(x, POW(y, MOD-2)); } ll gcd( ll m, ll n ) { if ( ( 0 == m ) || ( 0 == n ) ) return 0; while( m != n ) { if ( m > n ) m = m - n; else n = n - m; } return m; } ll lcm(ll a, ll b){ if( (a==0) || (b==0)) return 0; return (a/gcd(a,b)*b); } int main(void){ int n; cin >> n; ll X; cin >> X; ll x[n]; ll s_x[n+1]; REP(i, n){ cin >> x[i]; s_x[i] = x[i]; } s_x[n] = X; if(n == 1){ cout << abs(x[0]-X) << endl; return 0; } SORT(s_x, n+1); SORT(x, n); ll diff[n]; REP(i, n){ diff[i] = s_x[i+1]-s_x[i]; //cout << diff[i] << endl; } REP(i, n-1){ diff[i+1] = gcd(diff[i], diff[i+1]); //cout << diff[i+1] << endl; } cout << diff[n-1] << endl; return 0; }
D
問題は以下を参照。
D - Make Them Even
問題を読んだときに、いつかABCのC問題辺りでやったリバーシを思い出した。(問題がいつか忘れた。) 解法はいくつか存在するが、僕は以下のように解いた。
- 左端から右端を除く列へ、そのマスが奇数であれば-1, 右隣りのマスを+1する。
- 右端の列を上から下へ、そのマスが奇数であれば-1, 下のマスを+1する。
図解すると以下のようになる。
→→↓ →→↓ →→○
これでもWAをくらってしまったのだが、出力の際に行数nを入れ忘れたのが原因である。
許すまじn。
コードは以下。
//#include <bits/stdc++.h> #include <iostream> #include <complex> #include <sstream> #include <string> #include <algorithm> #include <deque> #include <list> #include <map> #include <numeric> #include <queue> #include <vector> #include <set> #include <limits> #include <cstdio> #include <cctype> #include <cmath> #include <cstring> #include <cstdlib> #include <ctime> #include <climits> #define REP(i, n) for(int i = 0; i < (int)(n); i++) #define FOR(i, j, k) for(int i = (int)(j); i < (int)(k); ++i) #define ROF(i, j, k) for(int i = (int)(j); i >= (int)(k); --i) #define FORLL(i, n, m) for(long long i = n; i < (long long)(m); i++) #define SORT(v, n) sort(v, v+n) #define REVERSE(v) reverse((v).begin(), (v).end()) using namespace std; using ll = long long; const ll MOD=1000000007LL; typedef pair<int, int> P; ll ADD(ll x, ll y) { return (x+y) % MOD; } ll SUB(ll x, ll y) { return (x-y+MOD) % MOD; } ll MUL(ll x, ll y) { return x*y % MOD; } ll POW(ll x, ll e) { ll v=1; for(; e; x=MUL(x,x), e>>=1) if (e&1) v = MUL(v,x); return v; } ll DIV(ll x, ll y) { /*assert(y%MOD!=0);*/ return MUL(x, POW(y, MOD-2)); } int a[575][575]; int ans1[250000]; int ans2[250000]; int ans3[250000]; int ans4[250000]; int main(void){ int H, W, itr=0; cin >> H >> W; REP(i, H){ REP(j, W){ cin >> a[i][j]; } } REP(i, H){ REP(j, W-1){ if(a[i][j]%2 != 0){ a[i][j]--; a[i][j+1]++; //cout << i+1 << " " << j+1 << " " << i+1 << " " << j+2 << endl; ans1[itr] = i+1; ans2[itr] = j+1; ans3[itr] = i+1; ans4[itr] = j+2; itr++; } } } REP(i, H-1){ if(a[i][W-1]%2 != 0){ a[i][W-1]--; a[i+1][W-1]++; //cout << i+1 << " " << W << " " << i+2 << " " << W << endl; ans1[itr] = i+1; ans2[itr] = W; ans3[itr] = i+2; ans4[itr] = W; itr++; } } cout << itr << endl; REP(i, itr){ cout << ans1[i] << " " << ans2[i] << " " << ans3[i] << " " << ans4[i] << endl; } return 0; }
最後に
ここまで見てくださってありがとうございました。参加が5回目？か6回目？ぐらいでようやっと茶色の半分に到達しました。まずは水色になれるよう精進します。めう。 それにしてもモチベーションが維持できないのでPaizaの問題でも解こうかな...辛い
NoSQLについてまとめてみる 〜後編〜
前回からの続きです。
NoSQLは、モデルによって大きく4種類に分けられます。
それぞれの特徴をざっと表にしました。
?はケースバイケースです。
| 種類 | スケーラビリティ | 性能 | 柔軟性 (高い表現力) | 簡易さ |
|---|---|---|---|---|
| Key-Value Store | o | o | x | o |
| Column Store | o | o | x | o |
| Document Store | o | ? | o | o |
| Graph Store | ? | ? | o | x |
次に代表的なDBを取り上げてみます。
Key-Value Store (KVS)
以下の記事ではantirez氏が同じKVS型DBのMemcachedとRedisを比較しています。
Memcachedは非常にシンプルでメモリ効率が良い一方、メモリフラグメンテーション、LRU性能、監視しやすさといった点ではRedisに軍配があがるとのこと。
Redisは会社でもたまに耳にするので、今度触ってみたいです。
Column Store
列方向のaggregationが優秀らしい。（名前の通りか）
CassandraとHBaseの比較をしている以下のSlideShareがわかりやすかったです。
pp. 55~が比較スライドとなっている。耐障害性や性能、手動・自動の違いがあったりなど、Column Store型の中でも違いが大きいらしい。障害発生時の挙動が異なるようなので、ユースケースごとに使い分けるべき?
Document Store
MongoDBやElasticsearchがこれにあたる。個人的には一番馴染みが深い。PostgreSQLもDocument orientedに分類される?のか...? (RDBかと思っていたが、要確認)
特にMongoDBは、性能をとる代わりに、結果の整合性やトランザクションがサポートされていないです。
Elasticsearchは高性能・高スケーラビリティな全文検索エンジンで、通常の検索だけでなく、集計処理やソート、スコアリングといった処理も高速に可能です。実態はLucene Indexが動いていて、裏でsegments mergingなど起こったりしています。
あと余談ですが、ElasticsearchはCAP定理でいうPを落としている(と思われます。)というのもnode全体の生存監視やshardsの管理をするMaster nodeと候補となりうるMaster eligible nodeがそれぞれ分断された場合、分断後のネットワークらはどちらも動作可能であるからです。
Elasticsearchの話も、後々まとめたいです。
Graph Store
Facebookのお友達つながりなんかを表現するのに向いてるグラフです。あまり馴染みがないのですが、以下のブログが具体的なイメージの参考になりました。
グラフDBのNeo4jを1日触ってみた - Wantedly Engineer Blog
こうした複雑な関係性をRDBMSで表現しようとすると骨が折れそう、というか無理ですね。
今回は、各モデルについてちょっとずつ言及する形で代表的なDBをまとめました。
実際に触ってみることで得られる知見もあると思うので、手を動かしていきたいですね。
NoSQLについてまとめてみる 〜前編〜
はじめに
こんばんは、tikedaです。
7月末までは時系列データ解析のお仕事に携わっていました。8月から元の部署へ戻り、お仕事させて頂いています。
今私がいるチームでは、主にストレージ系の研究開発に取り組んでいます。私自身はDBや分散ストレージの知識に乏しいので、これを機に勉強しようと思い、その証を、記事として残していこうと思っています。間違いなどありましたら、ご指摘いただけると幸いです。
前編は概要だけまとめます。
RDBとNoSQL
DBMS(Data Base Management System)をざっくり分けると、テーブルを組み合わせて表現するRDB(Relational Data Base)とその他のNoSQL(Not-only Structured Query Language)に分けられます。
それぞれの特徴やPros/Consは、以下の記事の解説がわかりやすいです。
トランザクションのサポートや拡張性など、色々なトレードオフがありますが、利用シーンによって使い分けることが大切だと感じました。
中でも今回は、NoSQLについて調べます。
NoSQLって何?
以下の記事が非常に参考になりました。
データモデルによって、大きく4種類に分けられます:
- Key-Value Store
鍵(Key)とそれに対応する値(Value)を格納する、簡潔なDB。
例. Memcached, Redis - Column Store
データをrawではなくcolumnに分割して格納するDB。
例. Apache Cassandra, Apache HBase - Document Store
XMLやJSONのような、スキーマレスで柔軟な構造を持つことが可能なDB。
例. MongoDB, Apache CouchDB, Amazon DynamoDB - Graph Store
グラフ構造のDB。
例. Neo4j, InfiniteGraph
ざっとこんな感じです。
次回は 各DBの特徴についてまとめます。
