ABC130に参加して冷えた話
はじめに
更新をサボり気味なので、これから毎週コンテスト後の感想を綴っていこうと思います。
2完しか出来ずに氷河期を迎えた（茶パフォ）、前回稼いだレートは消えました。
A問題
お決まりのif文知ってますか問題、変数の名前は問題のと異なってます
int main(void){ ios_base::sync_with_stdio(false); cin.tie(0); int n,x; string s; cin >> n >> x; if(n < x) cout << 0 << endl; else cout << 10 << endl; return 0; }
B問題
累積和作れば良かったのだと思うのですけど、n番目を考慮漏れして1WAしてしまった
深く考えずにvectorへ突っ込んだ後、上記に気づいてAC
int main(void){ ios_base::sync_with_stdio(false); cin.tie(0); int n,x; string s; cin >> n >> x; vector<ll> L(n+1); vector<ll> D(n+1); REP(i, n) cin >> L[i]; ll cnt = 1; D[0] = 0; vector<ll> vec; FOR(i,1,n+1) { D[i] = D[i-1] + L[i-1]; vec.push_back(D[i]); } sort(vec.begin(), vec.end()); for(auto &e: vec){ if(e <= x){ cnt++; } } cout << cnt << endl; return 0; }
C問題
何故か問題を読んだ時から格子状での解法を考えていた。。。
よくよく考えると線の傾きに制限はないので、四角形の中心を通る切り方が最適であると分かる
よって、座標(x, y)が中心に与えられた場合は切り方として無限パターン存在する
その他の場合は1パターンしかない
int main(void){ ios_base::sync_with_stdio(false); cin.tie(0); ll w, h, x, y; cin >> w >> h >> x >> y; cout << fixed << setprecision(20); cout << double(w) * double(h) /2 << " " << (x+x == w && y+y == h) << endl; //所与の点が中心である ... (w/2, h/2) = (x, y) return 0; }
D問題
解法は合っていたが、TLEして終了した
原因は個数を数える際にleft = 0を代入して、逐一計算していたこと
あと途中まで単調増加か否かを無視してしゃくとり法走ってたのも良くなかった...
sumがkの値を以上ならば以降の(n-r+1)の要素についても sum >= kが成立するため、これをansに足し合わせる方針で解けば良い
↑自分の考えと逆の足し方だったので、ちゃんと覚える
int main(void){ ios_base::sync_with_stdio(false); cin.tie(0); ll n,k; cin >> n >> k; vector<ll> a(n); REP(i,n) cin >> a[i]; ll ans = 0LL, sum = 0LL; int r = 0; REP(l, n){ while(sum < k){ if(r == n) break; else{ sum += a[r]; r++; } } if(sum < k) break; ans += n-r+1; sum -= a[l]; } cout << ans << endl; return 0; }
E以降
解いてないので、また今度やります
所感
くっそ冷えて萎えましたが、最近精進できてなかったので致し方ないです
なので今週は、しゃくとり法をそらで高速に書けるよう精進します！
覚えること: 「〜以降は条件を満たす」場合は、後ろから差分を引いてansに加える
忙しい人のためのRedisチュートリアル
この記事は何?
RedisConf19参加にあたり, Redisのdocsをしっかり読み込んだことがなかったため実施した. 量が多いため, 途中から要約だけ載せる.(疲れたので)
なお, 現時点でのlatest stableはRedis v5.0.4である.
commands
データ型はstring, bit, hash, list, set, sorted set, hyperloglog, streamと多種揃っている. 呼び出せるコマンドについては全てココにあるため, 今回は割愛する. 日本語のドキュメントだと, v2.0.3までの関数は以下にある. コマンドリファレンス — redis 2.0.3 documentation
stream type
v5.0.0から stream型エントリ のデータ管理方法が実装された. stream型は名前のとおり, 時系列データを扱うためのデータ型である. XADDやXRANGE, XDEL, XTRIMといった先頭にXのつくコマンドがstream用のコマンドとなっている. 例. XADDのdoc XADD – Redis
例えばXADDは, 同一keyに対して複数valuesを与える形で記述できる.
redis> XADD mystream * name Sara surname OConnor
"1553778517432-0"
redis> XRANGE mystream - +
1) 1) "1553778517432-0"
2) 1) "name"
2) "Sara"
3) "surname"
4) "OConnor"
redis> XADD mystream * field1 value1 field2 value2 field3 value3
redis> XRANGE mystream - +
1) 1) "1553778517432-0"
2) 1) "name"
2) "Sara"
3) "surname"
4) "OConnor"
2) 1) "1553778517433-0"
2) 1) "field1"
2) "value1"
3) "field2"
4) "value2"
5) "field3"
6) "value3"
value登録時に発行される文字列をstream IDと呼ぶ. 例えば上記の例では"1553778517432-0"が該当する. ご覧の通り, stream IDは[unix msecのタイムスタンプ]-[シーケンス番号]と構成される.
以下参考.
qiita.com qiita.com streamのintroduction (とは思えない程の分量と内容) Redis Pub/Subを先に読むことを推奨 Introduction to Redis Streams – Redis
Pipelining
https://redis.io/topics/pipelining
TL;DR
ClientがRequestを発行してからServerがResponseし, Clientへ結果が戻るまでの時間をRoundTripTimeと呼ぶ. Server側がRequestを受信する度にResponseを返すのではなく, まとめて返事することで(server側の)system callsの実行回数が減り, レイテンシ低減する. それだけでなく, 時間辺りに実行できるクエリ数も増加する. できるだけpipeliningを使おう!←結論
Pub/Sub
https://redis.io/topics/pubsub
Apache Kafkaとか有名なやつ, メッセージングパターン.
TL;DR
例えばclientがsubscribeしたいとする. この時, clientはチャンネルをSUBSCRIBEコマンドで指定する. そしてチャンネルにpushされたメッセージは, それをsubscribeしている全clientに送信される. pushするにはPUBLISHコマンドを用いる. チャンネルのsubscribeをやめる場合は, UNSUBSCRIBEコマンドを用いる. Redis Pub/SubはパターンマッチングによるPub/Sub機能もある. それぞれPSUBSCRIBE, PUNSUBSCRIBEを使う. Pub/Sub subsystemの状態を見たい場合はPUBSUBコマンドを叩く.
以下参考.
Lua scripting
https://redis.io/commands/eval Luaスクリプトを実行できるよ!
> eval "return {KEYS[1],KEYS[2],ARGV[1],ARGV[2]}" 2 key1 key2 first second
1) "key1"
2) "key2"
3) "first"
4) "second"
RedisとLuaの相互型変換は可能らしい. ただし, 浮動小数で返してほしい場合はLua側が文字列として返す必要あり.
If you want to return a float from Lua you should return it as a string
あとSHA-1ハッシュ関数を使うEVALSHAコマンドもある.
transactions
トランザクションもあるよ. https://redis.io/topics/transactions
トランザクション — Redis Documentation (Japanese Translation)
トランザクション自体の説明は以下参考.
データベースさわったこと無い新人向けトランザクション入門 - Qiita
TL;DR
主にMULTI, EXEC, DISCARD, WATCHコマンドを使う.
> MULTI OK > INCR foo QUEUED > INCR bar QUEUED > EXEC 1) (integer) 1 2) (integer) 1
特徴として, コマンドがミスっていても, 実行可能なものは処理されてしまうという点には気をつけたい.
even when a command fails, all the other commands in the queue are processed
Trying 127.0.0.1... Connected to localhost. Escape character is '^]'. MULTI +OK SET a 3 abc +QUEUED LPOP a +QUEUED EXEC *2 +OK -ERR Operation against a key holding the wrong kind of value
ロールバックはサポートされていない. 理由は - シンタックスが間違ってるときしか失敗しないから - ロールバックしなくても問題ないぐらい速い (もう一度実行しろってことかな)
DISCARDコマンドでトランザクションのabortが可能
> SET foo 1 OK > MULTI OK > INCR foo QUEUED > DISCARD OK > GET foo "1"
WATCHコマンドを使うと, 楽観的なロックが実現できる. WATCHコマンドは check-and-set の振る舞いを提供する. つまりWATCHコマンドで監視しているkeyに変更が加わった場合, トランザクション全体を中止する.
persistence
Redisでは大きく2つの永続化オプションがある もちろん使わないことも可能だし, 片方だけ使うこともできるし, 組み合わせて使うことも可能. 求める永続化の性能に依存.
RDB: 指定時刻ごとにデータセットのスナップショットを取得する. もしくはコマンドを叩いて取得する. スナップショットはバックアップとしては完璧だが, redisに障害発生時のデータ損失可能性はそこまで低く出来ない.
AOF(= Append only log): 実行されたコマンドをログとして残す. 耐障害性はRDBより高いが, ファイルサイズが大きくなりがち.
Memory optimization
Redisをメモリ効率よく使うためのTips, まだ執筆途中とのこと. https://redis.io/topics/memory-optimization
TL;DR
メモリ効率の良いhashをできるだけ使いましょう
だいぶ端折りましたが, 疲れたので残りは次回！
ABC118 に参加した話
問題
下記リンク
解答
A問題
cin >> a >> b; if(b%a == 0) cout << a+b << endl; else cout << b-a << endl;
B問題
mapに挿入、n個あるものをカウントして出力
int k[31], a[31][31]; map<int, int> mp; int main(void){ ios_base::sync_with_stdio(false); cin.tie(0); int n, m; string s; cin >> n >> m; REP(i, n){ cin >> k[i]; REP(j, k[i]){ int tmp; cin >> tmp; mp[tmp]++; } } int cnt = 0; for(auto itr = mp.begin(); itr!=mp.end(); itr++){ if(itr->second == n) cnt++; } cout << cnt << endl; return 0; }
C問題
A_iの中から小さい数を取り出してmodをとる これを繰り返し、できなくなったら終了 最小値を出力
const int INF = 1e9; int n; ll a[100100]; int mini = INF; int main(void){ ios_base::sync_with_stdio(false); cin.tie(0); cin >> n; REP(i,n) { cin >> a[i]; if(a[i] < mini) mini = a[i]; } bool f = true; while(f){ int tmp = mini; int cnt = 0; REP(i, n) { if(a[i]%mini != 0){ a[i] %= mini; } else{ cnt++; } } if(cnt == n) break; REP(i, n) mini = min((int)a[i], mini); } cout << mini << endl; return 0; }
D問題
(時間内に解けなかった) 考えたことは、DPで解けそう→dp[i][j]で長さ最大の文字数を入れればいけそう→経路の復元方法が分からない→貪欲 という流れで貪欲を書いたが、RE
正解は、string型の一次元DPに文字列ごと保持する 文字列長が最大となるものを管理しつつ、長さが同じ場合は辞書順比較で小さいものを常に管理する (他の方のコードを参考にさせていただきました)
//解説AC //https://atcoder.jp/contests/abc118/submissions/4292391 int num[]={0,2,5,5,4,5,6,3,7,6}; int a[10]; int n,m; void cng(string &t, string p){ if(t=="0") t=p; else if(t.size() < p.size())t=p; else if(t.size() == p.size()){ if(t<p) t=p; } } int main(void){ ios_base::sync_with_stdio(false); cin.tie(0); cin >> n >> m; REP(i,m) cin >> a[i]; string dp[100100]; REP(i, n+1) dp[i] = "0"; dp[0] = ""; REP(i, n+1){ if(dp[i] == "0") continue; REP(j, m){ cng(dp[i+num[a[j]]], dp[i]+(char)(a[j]+'0')); } } cout<<dp[n]<<endl; }
感想
D問題、解けない問題ではないので、頑張って解きたかった... 引き続き精進します
学んだこと
- 文字列の辞書順比較はoperator >, <で可能
例えば '9' > '11' はtrueになる- (char)(a[j]+'0')でint->char変換
ABC097 D Equals を解いた話
最近更新できていないので、競プロネタを投稿。
下記の問題を解説ACした。 D - Equals
問題
整数x [1, N]を適当に並び替えた順列p_1, p_2, ..., p_NとM個の整数ペア(x_1, y_2), ..., (x_M, y_M)が与えられる。
与えられた整数ペアを用いて、 swap(p_x, p_y)を何度でも行えるとする。
操作後にp_i = i となる数の最大数を求めよ。
要はインデックス通りに並べられることが可能な数字の最大の数を求める?ということ。
自力ではACできずにUnionFindの解法を参考にした。
www.slideshare.net
素集合データ構造で、同じグループに属す(Union)操作と同じグループかを探す(Find)操作を行うものである。
素集合というのは、ある要素が複数の集合に含まれないものを指すらしい。
コードはこんな感じになった。
x,yの配列いらないしメモリ無駄にしてるけど、とりあえずこれで提出して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++) using namespace std; using ll = long long; template <typename T> class UnionFind { public: T n; vector <T> d; UnionFind(T n) :d(n, -1) {} int find(T x){ if(d[x] < 0) return x; return d[x] = find(d[x]); } bool unite(T x, T y){ x = find(x); y = find(y); if(x == y) return false; if(size(x) < size(y)) swap(x, y); d[x] += d[y]; d[y] = x; return true; } int size(T v){ return -d[find(v)];} bool same(T x, T y){ return find(x) == find(y); } }; int p[1000000], x[1000000], y[1000000]; int main(void){ ios_base::sync_with_stdio(false); int n, m; cin >> n >> m; REP(i, n) cin >> p[i]; REP(i, m) cin >> x[i] >> y[i]; UnionFind<int> uf = UnionFind<int>(n+1); REP(i, m) uf.unite(x[i], y[i]); ll ans = 0LL; REP(i, n) if(uf.same(i+1, p[i])) ans++; cout << ans << endl; //if(uf.unite(x[0], y[0])) cout << "success" << endl; //cout << uf.size(5) << endl;; return 0; }
日本語形態素解析エンジンKuromojiについて調べた
はじめに
とある事情(仕事)により、日本語の形態素解析エンジンKuromojiについて調べる必要があったので、ドキュメントとコードを読み込んだ。 形態素解析とは、ものすごく簡単に言うと、文章をその構造や品詞に細かく分解することです。分解された単位をトークンと呼ぶ。(イメージとしては、単語や助詞がトークンとなりえる。)
特に、自然言語処理(NLP)なんかでは馴染みがあるのでは？(私は素人なので...) 形態素解析は、主に利用する辞書の精度(網羅率)に大きく依存する形になります。例えば「ほげふが」という文章を解析するとして、辞書に「ほげ」と「ふが」が存在している場合、["ほげ", "ふが"]と2つのトークンに分解することができる。(これをトークナイズと呼ぶ。) 同じく文章をトークンに分解する方法として、N-gramがあります。Nに数字が入るわけですが、例えば2-gramで文章「ほげふが」をトークナイズする場合は、["ほげ", "げふ", "ふが"]と3つのトークンを生成することができる。
なおApatche版とAtilika版の2つが存在しますが、本記事では Atilika版 version 0.9.0を対象としている。
Kuromoji
概要
Java製の日本語形態素解析エンジン。
公式
kuromoji - japanese morphological analyzer
単語辞書
Kuromojiでは、ユーザ側は用意されている単語辞書(例. kuromoji-ipadic)に加えて、ユーザ独自で固有名詞等を指定できるユーザ辞書を利用できる。 また、内部的にはこれらの辞書に含まれない単語を、「未知の」単語辞書として保持しているようです。ちなみに未知の単語辞書については、そのカテゴリによって自動的にトークン化される。例えば「123#.!」という文章がある場合、["123", "#.!"]と数字、記号のカテゴリにトークン化される。詳しくは以下の実装を確認してほしい。
kuromoji/ViterbiBuilder.java at 0b01987c6977701f01db901d738869b0275212d5 · atilika/kuromoji · GitHub
Kuromojiの解析モード
トークン化する際の解析粒度に応じて、モードが3つほど存在する。
Normalモード デフォルトモードで、辞書にのっとってトークナイズする。 未知の単語については、上記の方法にのっとり、カテゴリごとにまとめてトークナイズする。
Searchモード Normalモードに加えて、複数の言葉が組み合わさった単語を分解してトークナイズする。 例えば「日本経済新聞」という名詞があった場合、["日本", "経済", "新聞"]と分解する。 何が嬉しいかというと、全文検索エンジンなどで、単語を引っ掛けたい時に有効。
Extendsモード Searchモードに加えて、未知語をuni-gram (雲丹ではなくて「1」という意味)としてトークナイズする。 例えば、「サバゲー」が未知語の場合は、["サ", "バ", "ゲ", "ー"]となる。
内部で用いられるアルゴリズム
形態素ラティス
下図のような、ノードがトークンとなったラティス。 各ノード・エッジにはコストが存在し、それぞれ単語辞書・解析モード別の計算式によって与えられる。 このコストを最小となる (≒ 尤もらしいトークナイズができている) パスを求めるためにViterbiアルゴリズムを用いる。
Viterbi
隠れマルコフモデルに基づいた動的計画法(DP)で、考えられる経路の中で尤もらしい経路を見つける。 隠れマルコフモデルに従うので、コストの部分について確率的な解釈が可能 (というかそうするのが一般) である。しかし今回のケースではコストが一意に決まるため、最小コストを確率ではなく一意に探索することが可能。
Viterbiアルゴリズム - 機械学習の「朱鷺の杜Wiki」
http://www.phontron.com/slides/nlp-programming-ja-04-ws.pdf
時間計算量がO(T*N2)かかる？ (T: 時間の終端、N:ノード数)
実装は以下。
kuromoji/ViterbiBuilder.java at 0b01987c6977701f01db901d738869b0275212d5 · atilika/kuromoji · GitHub
Patricia Trie
基数木と呼ばれる木構造のこと。
連想配列を使って各エッジに文字が張られるイメージ。
Pros
- 省メモリ
- 検索・挿入・削除 : O(k) (k: キーの長さ) なので、 (二分木と比べると、場合によっては)物凄く速い。
- 日本語の場合は文字列長が小さいので、ここはかなり効いてくると考えられる。
Cons
- 文字列や、文字列に変換可能なデータしか扱えない。
Finite State Transducer (FST)
有限状態トランスデューサと呼ばれる。いわゆる有限状態オートマトンに各エッジの出力を加えたもの。
Luceneで使われてるFSTを実装してみた（正規表現マッチ：VMアプローチへの招待）
Pros
- Patricia Trieが利用可能・状態数が最小であることが保証されるため、省メモリ。
- 決定性を持つため、入力に対する出力が一意に決定。
- DAGなのでトポロジカルソート可能。 ラティスにおける最小コストの経路はトポロジカルソート+ Viterbiで高速に探索可能。トポロジカルソートはO(V+E) (V:ノード数, E:エッジ数)。
Cons
- 先頭文字(prefix)の探索に時間がかかる。(日本語だと候補となる文字数が多すぎるので危険...) なので、先頭文字はcachingなどによる高速化で工夫される。
FSTで単語辞書を管理している。 (未知の単語辞書も含む) // Note that FST only allows the presorted dictionaries as input.
kuromoji/Builder.java at 0b01987c6977701f01db901d738869b0275212d5 · atilika/kuromoji · GitHub
ユーザ辞書を使った単語分割
こっちもFSTで保持。 surfaceが(Trie構造)FSTで保持している辞書
kuromoji/UserDictionary.java at 0b01987c6977701f01db901d738869b0275212d5 · atilika/kuromoji · GitHub
若干しゃくとり法と似てるなと思った（は？）
以下が実装部分
/** Lookup words in text
* @param text text to look up user dictionary matches for
* @return list of UserDictionaryMatch, not null */
public List<UserDictionaryMatch> findUserDictionaryMatches(String text) {
List<UserDictionaryMatch> matchInfos = new ArrayList<>();
int startIndex = 0;
while (startIndex < text.length()) {
int matchLength = 0;
int endIndex = 0;
while (currentInputContainsPotentialMatch(text, startIndex, endIndex)) { //トークン検索
String matchCandidate = text.substring(startIndex, startIndex + endIndex);
if (surfaces.containsKey(matchCandidate)) {
matchLength = endIndex;
}
endIndex++;
}
if (matchLength > 0) { //マッチするようなトークンが見つかったらば,
String match = text.substring(startIndex, startIndex + matchLength);
int[] details = surfaces.get(match);
if (details != null) {
matchInfos.addAll(
makeMatchDetails(startIndex, details)
);
}
}
startIndex++;
}
return matchInfos;
}
おわりに
まとめると、シンプルにかけます。 1. FSTによる管理で高速に辞書検索（トークンとなる候補をここで探す。） 2. 形態素ラティスを構築して尤もらしくトークナイズする（トークンとなる候補の中から、トークンを決定する。） 高速化を意識された実装になっていて、素晴らしいと思いました。
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をまとめました。
実際に触ってみることで得られる知見もあると思うので、手を動かしていきたいですね。
