AWS Certified Data Analytics - Specialtyに合格しました
皆さんおはようございます。最近AWS資格記事しか書いていないような気がしますが、記録のため書いておきます。
先日試験を受けて、無事合格しました。
AWS DASとは？
AWSのSpecialty資格のなかで、分析ソリューション関係の知識を問う資格です。
全65問で180分、Professionalよりも問題数は少ないですが、時間は同じですね。
ガイドを見ると、GlueやRedshift、KinesisやDynamoDBなど分析関係のサービスがピックアップされています。
逆に、データベース設計やPySparkなどの領域は出ないですね。
結果は？
851/1000で合格しました。
Professionalと違って、時間も結構余りました。
そして、「多分受かったな…」という手ごたえの元、回答終了ボタンを押せました。初めての体験。
勉強時間も、10時間ほど。Professionalよりは楽だったなという印象でした。
ただ、ここ数年ずっとこの分野のAWSのサービスを触っていたり、最近より深くかかわるようになってきたりしているので、
業務知識がある状態で、という前提です。何も知らない状態だと、やはりきついと思います。
やっておいた方が良いものは？
TechStock
やはり鉄板。Professionalが終わって課金期間が終わっていたので、再課金しました。
#34から#18まではやったかな。
今回思ったのは、とりあえず試験に受かるなら、1問1問分からなかったところを調べるのではなくて、とりあえず周回することが近道。
なんとなく似ている問題が実際出るから、とりあえず見たことあるって状況を作った方が良い気がしました。
ただ、もちろんただ暗記ゲーだけだと何も見につかないので、ところどころは調べた方が良いですが、優先度としては周回スピード優先の方が合格率は高まりそうと感じました。
今回これ以外はなし。
BlackBeltはもともとちょこちょこ見ていたから、大体頭に入っていたと思います。
Kinesis系だけはあまり触ってなかったら、BlackBeltも観たかな。
おわりに
今回は、Professionalよりはいろいろと楽でした。というかあれがつらすぎた。二度と受けたくない…。
次はDeveloper受けたいな。あわよくばProまで。
それでは、良いお年を！
AWS Certified Solutions Architect - Professional に合格しました
皆さんこんばんは。夏も終わり、涼しくなってきましたね。
今回は、久々のAWS試験シリーズです。SysOpsをこの夏にとって、それ以降このProfessionalを勉強してきました。
先日試験を受けて、合格したのでその記録です。
結果は？
803/1000で合格しました。（SAAと同じ点数…）
750点以上が合格なので、可もなく不可もなくというところでしょうか。
よく聞くように、「回答終了」のボタンを押す瞬間は落ちたと思いました。
というのも、自信をもって選べた問題が75問中10問くらいしかなかったためです。
時間についても、180分の制限時間でほとんど余りませんでした。そのため、見直しもほぼできず。
受かってよかったです。
やっておいた方が良いものは？
TechStock（通称koiwa-club）
まずはこれ。というかほとんどこれしかやっていません。
大体どの合格記でも、この問題集の#30-を3周くらいやれと書いてあります。
私も意気込んでそれをしたのですが、勉強時間が足りず結局#30-54, #67-70を1周しかできませんでした…。
（途中から、#70からやり始めた）
勉強時間も合計30時間くらいで、圧倒的に足りなかったですが、運よく受かりましたね。
Black Belt
サービス別資料 | AWS クラウドサービス活用資料集
koiwa-clubで理解が浅いサービスが判明するので、その時はこれ。
公式だけあって、内容が充実しています。あと網羅的でよい。
サービス以カット以外でのおすすめはこれら。
20200722 AWS Black Belt Online Seminar AWSアカウント シングルサインオンの設計と運用
めくるめくSSOの世界を説明してくれています。
個人的に、IdPとアイデンティティが別のサービスで利用できるというところが目から鱗でした。
https://d1.awsstatic.com/webinars/jp/pdf/services/20210209-AWS-Blackbelt-DirectConnect.pdf
サービスカット意外といいつつ、がっつりAWS Direct Connectの資料ですが…
オンプレからVPCへの接続パターンを挙げてくれてるのがよかったです。
クラスメソッドさんのブログ
BlackBeltがいきなり詳細すぎたときは、クラメソさんブログで理解していました。
分かりやすい。とても分かりやすい。
個人的な推し執筆者が2人います。
チバユキさん
千葉 幸宏（チバユキ） | DevelopersIO
分かりやすいし詳しいし、何といってもAWS愛が伝わってきます。
高品質の記事を高頻度で出していて、それが無料。AWS界の吉野家ですね。
たまちゃんさん
たまちゃん | DevelopersIO
記事に取り上げるトピックが、自分の興味あるものばかり。（今回の資格勉強に限らず）
記事のタイトルで選んでいたら、「え、これもたまちゃんさん？え、これも？？」みたいになりました。
AtCoderコンテスト_ABC268_C-Chinese Restaurant解説
皆さんこんばんは。ABC268お疲れさまでした。
最近、C問題が難しくないですか？
今回も私は難しいと思ったのですが、時間内に何とか解けたのがうれしかったので、解説記事を出します。
C問題の概要
問題文は↑からどうぞ。
この問題は、結局のところ
「全ての料理p_iの中で、目の前の人の番号が、料理p_i自身の数-1～+1に収まっている個数が最大となるものを求めよ」
というものでした。
例えばこの場合。
赤文字の、料理は①で人が2の場合は、±1以内なのでOKです。
逆にそれ以外は、2以上離れているのでNGで、当てはまる合計数は1となります。
次に、このテーブルを反時計回りに1つずらしてみるとこうなります。
右上の料理が⓪で人が5の場合は5離れているように見えますが、料理⓪の-1はまた5に戻るようにするため、人5,0,1のどれかであればOKです。
今回の合計数は3となります。
このように考えたとき、合計数の最大値を求めるのが今回の問題です。
普通に考えると、テーブルを1つずつずらしていき、それぞれの合計数を求めていけば答えが出そうです。
ただ、そうすると計算量がO(N^2)となってしまいます。
今回、3 <= N <= 2 * 10^5 であるため、それだと計算時間に間に合いません。
解法
まず、例えばN=6の場合を考えます。
そして、料理が
[2, 1, 5, 0, 3, 4]
である場合を考えます。
こんな感じですね。
料理①の人1、料理③の人4、料理④の人5の3つが±1以内になっています。
さて、これを、2次元の表で表してみます。
横軸が料理の番号、縦軸が人です。
料理は[2, 1, 5, 0, 3, 4]であるため、そのセルが塗りつぶされています。
[2022/9/28追記 これ以降の縦軸と横軸について、人と料理が逆です。横軸が人で縦軸が料理番号となります。]
今回は料理の数の±1までOKなのでした。それを考慮して色を塗るとこうなります。
こうなった時、±1以内になっている料理というのはどれを指すでしょうか？
すでに±1までセルを塗っているので、今回の状況に当てはまるのは、料理と人が同じ番号であるとき、つまりは左上から右下に伸ばした直線上にセルが塗られていた場合です。
少し上に戻って、今回適しているのは3通りだったことを確認してみてください。
>料理①の人1、料理③の人4、料理④の人5の3つが±1以内になっています。
この3つが表で表現されていますね。
ここまでは、ある特定の場合のみでした。
今回の問題は、テーブルを逆時計回りに回転できます。
1回転させた場合がこちらです。
反時計回りのため、全体的に1列右にずらしています。
これも同じく線を引くと、2つの場合が±1以内になっています。
さらに1つずらすとこうなります。
つまり、このように1つずつずらしていって、左上から右下に直線を伸ばした時の数を数えて、一番多いものを出力すれば答えとなります。
ここからは、どうやってプログラムに落としていくかを考えます。
まず、1つずつずらすのはプログラムで表すのが難しいですよね。
どうにか、最初の初期状態の表から考えられないものか。。。
そこから、表全体をずらすのではなく、直線自体をずらせばよいのでは？という発想に行きつきます。
つまり、こういうことです。
こうすれば、初期状態を作ってしまえば、あとはこの直線をループで回せば処理できそうです。
ただ、この直線は斜めになっているため、いまいち扱いにくいですね。
なんとか横方向の直線にしましょう。
一つ上の図とよく見比べてみてください。
p_0の列はそのまま、p_1の列は1つ上にずらす、p_2の列は2つ上にずらす…とずらしています。
つまり、p_iの場合iだけ上にずらせばいいですね。
あとは、この直線の数（=人の数）だけループを回せば最大値を得られます。
以下に、自分が書いた実装載せておきます。
#include <iostream> #include <algorithm> #include <vector> #include <cmath> #include <numeric> #include <iomanip> #include <string> using namespace std; #include <map> int main() { int n; cin >> n; int p[n+10]; for (int i=0;i<n;i++) cin >> p[i]; int table[n+10]; // 表で表す for (int i = 0; i < n; i++) table[i] = 0; for (int i = 0; i < n; i++) { int p_0,p_1,p_m1; // 直線を斜めから横にするため、iだけマイナスする。 p_0 = p[i]-i; p_1 = (p[i]+1)%n -i; p_m1 = p[i]-1 -i; // 0未満の場合の処理 if (p_0<0) p_0+=n; if (p_1<0) p_1+=n; if (p_m1<0) p_m1+=n; table[p_0]++; table[p_1]++; table[p_m1]++; } // 最大値を調べる int M = 0; for (int i = 0; i < n; i++) { if (M < table[i]) M = table[i]; } cout << M << endl; }
感想
dpとかいもす法とかが頭の片隅に入っていて、とりあえず2次元の表で考えられないか、と考えるようになっていました。
そこで、なんとか表にして、ずらして、あとは足し算する方法を思いついて、きれいに整理できたので記事にしてみました。
Dの文字列のやつは全く解けなかったので、何とかDの領域も解けるようになっていきたいです。
いい加減なクオラム（sloppy quorum）を良い加減に説明する
意外と暑さが控えめになってきた8月上旬、皆様いかがお過ごしでしょうか。
今日は、みんな大好きデータ指向アプリケーションデザインの第5章レプリケーションより、いい加減なクオラム（sloppy quorum）について説明しようと思います。
理由としては、ここの内容が少しわかりにくいと感じたためです。また、日本語のネーミングがなんだかダサカワな感じで気に入ったからです。
まずはそもそものリーダーレスレプリケーション、クオラムの説明をして、いい加減なクオラムの内容を説明します。
リーダーレスレプリケーション
(*) レプリケーション
レプリケーションとは、他のノードに同じデータをコピーしておくことです。
（ノード：DBソフトウェアを実行している各マシンor仮想マシン）
そうすれば、仮にそのマシンが壊れてもコピー先のデータは生きているので可用性が高まります。
他にも、レプリケーションを地理的にバラバラなところに作ることでそれぞれの地域のユーザーからの読み取りレイテンシを下げたり、コピーをたくさん作ることで大量の読み取りアクセスの処理を分散させることでスループットを高めたりといった効果があります。
ちなみに、コピーを保存する各ノードのことを、レプリカと言います。
そんなナイスなレプリケーションですが、3つのアプローチが存在します。
シングルリーダー、マルチリーダー、リーダーレスです。今回は、このリーダーレスレプリケーションのお話です。
他のアルゴリズムには、レプリケーションを先導するリーダー（最初に書き込まれるノード）が存在しますが、リーダーレスレプリケーションには存在しません。
クライアントは、書き込みを複数のノードに送信します。そして、読み取りも複数のノードから平行に行います。
そして特徴的なのが、書き込みの際にバージョン情報を持たせておくことです。
こうすることで、もし書き込みがいくつか失敗しても、読み取りの際に1つでも更新に成功した（=バージョンが新しい）ノードから読み込めれば、正しい値を取得できます。
ちなみに、この書き込みや読み取りを誰が行うかは、実装によって異なります。
クライアント側が複数のノードに書き込みや読み取りを行う実装もありますし、コーディネータノードというノードが行う実装もあります。
Amazonの内部で使われているDynamoというデータストア（DynamoDBとはまた別）がこのリーダーレスレプリケーションを採用しているということで有名らしいです。
Dynamoについては、この方のブログや
AmazonのDynamoDB論文を眺めた | Takuya Kitazawa
実際のDynamoの論文（の和訳）など読むと理解が深まります。
Dynamo: Amazonの高可用性Key-value Store[和訳] · GitHub
クオラム
さて、このリーダーレスレプリケーションでは複数のノードに書き込みや読み取りが行われます。そのため、各ノードが個別に書き込みに成功したり失敗したりします。結局、処理全体としてはどういうことが起きるのかを見ていきましょう。
例えば、このようにx=1の値をx=2に上書きするようなレプリケーションを考えます。
今回の例では、読み取りが成功したレプリカ1,2は書き込みが失敗しています。そのため、実際はx=2を書き込んだはずですが、x=1が読み取られてしまいます。これは、処理全体としては誤った読み取りになってしまいますね。では、どういう場合なら、処理全体として読み取りが正しく行えると保証できるでしょうか？
ここで出てくるのがクオラムという考え方です。
レプリカ数をn、書き込みに成功したノード数をw、読み取りに成功したノード数をr個としたとき、
を満たすようにそれぞれの値を自身で決めます。
この時、
- 書き込みに成功した = w個以上のノードに書き込みが成功した
- 読み取りに成功した = r個以上のノードに読み取りが成功した
とみなします。このような書き込み、読み取りをクオラム書き込み、クオラム読み取りと呼びます。
このクオラム書き込み、クオラム読み取りでは、最新の書き込みが最低でも1つは読み取れることが保証されます。
なので、w個の書き込み成功したノードとr個の書き込み成功したノードの集合のベン図が、最低1つは交わるイメージです。
それでは、そのクオラムの具体例を見てみましょう。今、x=3の値をx=4に上書きしようとしています。
この例では、 と決めています。
を満たしているため、最新の成功した書き込みが最低でも1つは読み取れます。実際、レプリカ3はx=4と書き込みに成功していて、読み取りにも成功しています。
この時、（成功した読み取りのうち、2つがx=3で1つがx=4となっていて、どれを最終的な値として決めるんだ？）と思った方、ごもっともです。ここは何かしらの方法で、値を1つに決める必要があります。
例えば1つの方法として、書き込んだ値にバージョンを持っておく、という方法があります。
今回の例でいうと、x=3が書き込まれる前の状態なので、この状態をversion=1としましょう。その後、x=4が書き込まれたとき、version=2にします。
そうすると、読み取りが成功した3つは
[x=3, version=1] ,[x=3, version=1] ,[x=4, version=2]
となり、この中で一番versionが大きいものを選択すれば、正しい値を取得できますね。
このように、n, w, rの値を決めて、w,rの数だけ書き込み、読み取りが成功すれば処理全体を成功とするやり方がクオラムでした。
であれば、このクオラムの考え方を用いれば最強卍なのでしょうか。
ここからが、いよいよ分かりにくい「いい加減なクオラム」です。
いい加減なクオラム（sloppy quorum）
クオラムの考え方を用いれば、必ず1つは最新の書き込み成功したノードを読み取れました。
ただ、逆に言えば、w個の書き込み、r個の読み取りが成功しなければ、処理全体は失敗するわけです。
これは、可用性の面で問題になります。そこで出てくるのが、いい加減なクオラムです。
いい加減なクオラムを使うと、書き込みの可用性が上がります。具体例を見てみましょう。今回は、最初の具体例（誤った読み取りされてしまった例）を、いい加減なクオラムを使った場合どうなるかを見ていきます。少し複雑なので、3ステップに分けてみていきます。
STEP1. 書き込み
まずは書き込みです。レプリカ1~4は障害発生中でアクセスできません、そのため書き込みが失敗しています。
そして、いきなり右側に領域展開されたのは、レプリカとはまた別のノードたちです。いい加減なクオラムでは、n個のレプリカ以外にも書き込みを受け付けることができます。今回は別領域のノード2つに書き込みを試み成功しているため、w=3となり書き込み処理全体が成功となります。本来のレプリカの中であれば、書き込み成功したノード数は1でw=3を下回るため書き込み処理全体は失敗するはずですが、いい加減なクオラムにより成功となりました。これが、可用性向上といわれている所以です。
ただし、注意すべきは「wの数以上書き込みが成功すれば、書き込み処理全体として成功」というルールは引き続き適用される、ということです。別領域を使ったとしても、それは変わりません。
そのため、別領域のノードに書き込みに行ったが、別領域ノードが全て落ちていて書き込みが全て失敗した場合は、全体で成功した書き込みはレプリカ5の1つのままであるため、書き込み失敗となります。
STEP2. ヒント付きのハンドオフ
次は、ヒント付きのハンドオフです。一時的に書き込んでいた別領域のノードを本来のレプリカたちに転送します。
障害が起きていたレプリカ1~4のうち、レプリカ3,4は復旧したとします。その時、一時的な領域に保持していたx=2をレプリカ3,4に転送します。
こうすることで、n個のレプリカの中でw=3という条件が満たされたことになります。
また、ここでいう「ヒント」とは、「本来はどのノードに送られるべきだったか」という情報のことを指します。
STEP1で別領域のノードにx=2を書き込んだ際、じつはその値とともに「本当はレプリカ3に書き込む予定でした」という情報もメタデータとして持たせています。それをもとに、レプリカ3の状態を定期的に確認し、復旧が確認出来たらx=2をレプリカ3に転送します。
STEP3. 読み取り
最後は読み取りです。ここは別領域とは関係なく、n=5のレプリカを対象に読み取りします。別領域に読み取りに行くことはありません。
今度はレプリカ4,5が障害を起こして読み取りが失敗、レプリカ1~3の3つが成功したとします。r=3を満たしているので、読み取り処理全体も成功となります。レプリカ3を読み取っているので、最新のx=2という値を正しく読み取れていますね。（x=1が2つ、x=2が1つ読み取れていますが、先ほどの方法と同じくversionを付けて書き込んでいたため、最新のx=2を判別できたとします）
以上が、いい加減なクオラムの仕組みです。ただ、いい加減なだけあって、通常のクオラムでは起き得なかった問題が起きます。
いい加減なクオラムで起きる問題
別領域のノードに書き込めるとは言え、それは一時的な対応です。本来のレプリカはn個であり、読み取りもこのn個のレプリカを対象に行われます。そのため、ヒント付きのハンドオフが実施される前に読み取りが行われた場合、古い値を読み取ってしまう可能性があります。
例えば、先ほどのSTEP1が終わって（別領域のノード2つも含めて書き込みが成功した）すぐに、レプリカ3,4が復旧して、さらに読み取りも行われてしまった場合です。
ヒント付きのハンドオフが行われる前であるため、レプリカ3,4には古い値x=1が格納されています。この状態でレプリカ1~3で読み取りが成功すると、r=3以上のため読み取り処理全体として成功しますが、x=1が取得されてしまいます。
このように、いい加減なクオラムを使うと、障害発生/復旧タイミングによって古い値が読み取られてしまう可能性があるのです。
まとめ + ユースケース
リーダーレスレプリケーションでの書き込み、読み取りの方法として、クオラム書き込み/クオラム読み取りという手法がありました。
これは、を満たす書き込み、読み取りで、少なくとも1つは最新の値を読み取ることが保証されます。
ただ、その保証の裏返しとして、w個の書き込み、r個の読み込みが成功しないと失敗してしまいます。
一方で、いい加減なクオラムではn個のレプリカとは別の領域のノードを一時的に書き込みのノードとして利用できました。その後、一時的な書き込みのノードからn個のレプリカにヒント付きのハンドオフで転送します。
この方法を用いることで、書き込みの可用性は向上します。しかし、読み込みに最新の値が含まれる保証はありません。
上記を考慮してユースケースを考えてみます。
クオラムは値の正確性が必要な場合に使えそうです。例えば、オンラインショッピングでカートに入っている商品の一括購入など。「最後に削除した100万円のツボの削除処理がまだ反映されていなかったので購入しました」ということは避けなければなりません。
いい加減なクオラムは、書き込みの可用性が必要な時に使えそうです。例えば、twitterのTLの読み込みなど（使われているかは知りません）。「1秒前にAさんがつぶやいた「風呂なう」というツイートが読み込めていないため、TL全体の表示もエラーとなります」となってしまうと、ユーザー的には使いにくくなってしまいます。
以上、いい加減なクオラムの説明でした。
間違っているところなどありましたら、ぜひご指摘ください。
Python用ネガポジ分析ライブラリ「oseti」をWindows+Docker Desktop+jupyter notebookで動かす
梅雨が明けたっていうのに、微妙に雨模様ですね。という季節の挨拶からこんばんは。
皆さんは、もう何年もやり取りをしているLINEグループなどはありますでしょうか。
私はあります。5年間、ほぼ毎日発言しているLINEグループです。
高校の頃の友人とのグループなのですが、しょうもない話を永遠としております。
さて、そんなLINEグループでやりとりをしていて、ふと
「めちゃくちゃ発言数がたまってるから、これを何かデータ分析できないか…」
と考えました。
まずは、人別/月別で発言のネガティブ・ポジティブ判断をして、違いを見てみよう！ということで、
簡単に使えるネガポジ判定モデルがないかなと探しておりました。
そこで、osetiという神ライブラリに出会いました。
日本語評価極性辞書を利用したPython用Sentiment Analysisライブラリ oseti を公開しました - Qiita
ただ、導入に少し手間取ったので、備忘録も含めて爆速で実行環境をセットアップする方法を書き留めておこうと思います。
osetiとは
ネガポジを判定してくれる、pythonのライブラリです。
ネガポジを判定するには、まず教師データがいりますが、osetiではこちらの日本語評価極性辞書を利用しているそうです。
Open Resources/Japanese Sentiment Polarity Dictionary - 東北大学 乾研究室 / Inui Lab, Tohoku University
使い方はかなり簡単で、importして評価したい文を以下のように記載するだけです。
最大1.0～最小-1.0でポジティブ、ネガティブ度を判定します。
評価したい文が2文以上ある場合は、1文ずつのスコアを返します。（例の2つ目）
import oseti analyzer = oseti.Analyzer() analyzer.analyze('天国で待ってる。') # => [1.0] analyzer.analyze('遅刻したけど楽しかったし嬉しかった。すごく充実した！') # => [0.3333333333333333, 1.0]
実行方法
① Dockerfileとdocker-compose.ymlを作成する
以下の2つの内容をコピペして、適当なworkディレクトリ配下に2つのファイルを作成してください。
FROM python:3.9 WORKDIR /app SHELL ["/bin/bash", "-c"] RUN apt-get update RUN apt-get install libmecab2 libmecab-dev mecab mecab-ipadic mecab-ipadic-utf8 mecab-utils ENV MECABRC "/etc/mecabrc" RUN pip install --upgrade pip RUN pip install notebook pandas matplotlib oseti
version: '3' services: app: build: . volumes: - ./:/app ports: - 8888:8888 tty: true
② コンテナに入る
PowerShellを開いて、①のworkディレクトリに移動してください。
その後、以下の2つのコマンドを実行しましょう。
1つ目のコマンドがdockerのコンテナを作成、2つ目がそのコンテナへ入るコマンドです。
docker-compose up -d
docker-compose exec app bash
③ コンテナ内でjupyter notebookを実行する
PowerSellでコンテナ内に入れているので、あとは以下のコマンドを実行すればjupyter notebookが立ち上がります。
osetiに必要なライブラリや、oseti自体もすでに入っているのでそのままosetiが使えます。
jupyter notebook --port=8888 --ip=0.0.0.0 --allow-root --NotebookApp.token=''
④ ブラウザからjupyter notebookに接続する
コンテナ内で起動しているjupyter notebookですが、docker-compose.ymlでコンテナ内のportとホストのportをつなげてあります。
そのため、ホストOS（今回はwindows）のブラウザから、以下のurlに接続すればアクセスできます。
http://localhost:8888/
そこで、最初の例を実行すると、見事にosetiが使えています。
ハマったところ
大きく2つハマりました。
1つ目は、Windows特有の問題です。
始めは、dockerではなくWindowsのJupyterLab Desktopという、Windowsのアプリ上で実行しようとしました。
そうすると、c++のライブラリがないとか、Mecabの辞書がないとか、エラーが絶えず断念しました。
やっぱりDocker最強！！！
2つ目は、Mecabの問題です。
osetiは内部でMecabを使っているので、そちらをインストールしています。
しかし、ただインストールするだけだと、osetiを実行したときに
no such file or directory: /usr/local/etc/mecabrc
というエラーが出てしまいました。
mecabrcはMecabの設定ファイルで、デフォルトで使う辞書などを指定できます。
Mecabをインストールすると作成されるのですが、これが/etc直下にできているので、上記のようなエラーが出ます。
対処法としては、環境変数で/etc/mecabrcにパスを通してあげることです。Dockerfile内でそれをしています。
おわりに
ということで、久々の備忘録記事でした。
今回色々な記事を参考にしましたが、完全に同じ状況というのがなかなかなかったので、私以外の人類の誰か1人にでも役立てばうれしいです。
色々試行錯誤したことをDockerfileにまとめれば、それをそのまま利用できるので、再現性という意味でやはりDocker最強ですね。
参考
GitHub - ikegami-yukino/oseti: Dictionary based Sentiment Analysis for Japanese
Jupyter notebookをdockerコンテナで起動してホストのブラウザから使えるようにする
DebianでMeCab(日本語形態素解析システム)を利用する | qs Developers
fedora30 python3 から MeCabを使う → エラー「 [ifs] no such file or directory: /usr/local/etc/mecabrc」が出たら sudo cp /etc/mecabrc /usr/local/etc/ で解決 - min117の日記
競プロという名の光
最近溶けそうなほど暑いですね。こんばんは。
そんな中、最近競プロ（AtCoder）始めてみました。いつまでやるかは未定です。
そこで、AtCoder始めたぜ記念カキコと、昨日解けなかったB問題の解説をしようと思います。
競プロ始めてみた件
理由
何かコンペをしたい！という欲求が湧いてきたため。
今までだったらkaggleをやっていたのだけど、
・基本チーム戦
・結果出るのが数か月と長い
・潤沢なリソースがない
という理由から、ちょっと最近出るのがおっくうになっていました。
そこで、2時間くらいで終わるし、なんかプログラミング出来たらカッケーな！
と思い、参加しました。
あ、C++の練習にもなるかな、という理由もありました。
なぜC++の練習をしたかったかというと、かっこよいからです。
大変なところ
まず、ABCという初心者歓迎コンテストに出場する時間を確保するところが大変。
毎週土曜日の21時スタートなのですが、基本土曜日というのは飲み会が入ります。
そのため、飲み会はすべて金曜日に実施するか、早く切り上げて酔ったまま参加することになります。
これは、学生の頃やっておきたかった。それか、土曜の朝にやってくれないかな。
あとは、比較的ハードルは低いかなと思います。
C++のデバッグ環境も、ググればいろいろヒットします。これとか参考にしました。
【VScode＋WSLで始める】競プロ用C++デバッグ環境構築 - Qiita
（私は、このやり方だとincludeパスをうまく読み込めなかったので、Remote – WSLを使う方法に一部修正しました）
ただ、これはまだ私は来ていないですが、モチベ管理が大変なのだろうなと思います。
最初の色の茶色であっても、10回程度コンテストに出ないとなれないそうです。
レッドコーダーが教える、競プロ・AtCoder上達のガイドライン【初級編：競プロを始めよう】 - Qiita
今までの戦歴
ABC 256 : ABC
ARC 142 : nothing
ABC 257 : A
ARC 143 : A
という、輝かしい成績です。
どのコンテストも、最後解けなかった問題は、解法は思いついているんだけどもプログラミング的にアウトという感じでした。
例えばABC 256は、繰り返す試行の途中の状態の持ち方を複雑にしてエラーが起きて通らなかったり、
例えばARC 142は、long longの型で扱えばよかったものintやらdoubleやらでずっとこねくり回していたり…
まぁ、このあたりは経験積んでいくしかないですかね。
とりあえずは、茶色を目指して基本的な問題を取っていく方針です。
ということで、今回は昨日のB問題を解説しようと思います。（これも、プログラミング的に知っておくべきことがあったので）
ARC143 B問題の解説
問題
N×Nのマス目の各マスに1からN^2までの整数を1つずつ書き込む方法であって、どのマスも以下の条件のうち少なくとも一方を満たすようなものの個数を998244353で割ったあまりを求めてください。
・そのマスに書かれている数より大きい数が書かれているマスが同じ列に存在する。
・そのマスに書かれている数より小さい数が書かれているマスが同じ行に存在する。制約：1 <= N <= 500
このような問題でした。
まず最初に見たとき、998244353ってなんや…暗号か？と思いました。
解答方針
[ARC143] B - Counting Grids｜syamashi｜note
この方の考え方が分かりやすいです。
軽くまとめると、問題文の中の「少なくとも一方を満たすようなものの個数」というのを直接数え上げるのは面倒（or条件だから）なので、余事象を考えます。
そうすることで、問題文の2つの条件のand条件の個数を求めて、全通り（N^2の階乗）から引けば答えが出ます。
この方針は何となくコンテスト中にできていたんですが、、途中の数が大きすぎてlong longでも収まらなくなりました。さぁ大変。
そこで、今後も覚えておくべきポイントとして、2つをここに書き記します。
知っとこポイント①：modの世界
1つ目は、modの計算についてです。
mod自体は私も知っていました。何かで割った時のあまりですよね。
11 ≡ 3 (mod 4)
です。11÷4をしたとき、余りは3なので。
ただ、桁数が大きすぎるものを扱うときに、modを使うのがプログラミングの世界では常識らしいです。
イメージとしては、10^10と10^11をかけると、10^21ですよね。
AtCoderにおいて、最強の型であるlong long型ですが、これでも10^19くらいまでしか扱えません。つまり、上の計算式は普通にやるとオーバーフローします。
ではどうするか。
10^10と10^11を掛け合わせる前に、それぞれmod 998244353 を取ります。
10^10 ≡ 17,556,470 (mod 998244353)
10^11 ≡ 175,564,700 (mod 998244353)
そして、それらを掛け算して、さらにmod 998244353を取ります。
17,556,470 × 175,564,700 = 3,082,296,388,609,000 ※ この数は非常に大きいですが、10^15オーダーなのでlong longに格納可能です。
3,082,296,388,609,000 ≡ 329,696,899 (mod 998244353)
そうして出てきた329,696,899という数字、これは何と 10^21のmod 998244353を取った数と等しいのです！！
つまり、mod 998244353を最後にどうせ求めるなら、途中の式もmod 998244353を取っておくとオーバーフローせずに計算できちゃうということです。
今は掛け算でやりましたが、足し算と掛け算はそのまま途中をmodとっても結果が変わりません。
ただ、引き算と割り算（特に割り算）はちょっと注意が必要です。
そのあたりの細かいことは、この記事がめちゃくちゃ参考になりました。この記事ではmodを別の数で取ってますが、考え方は一緒です。
コンテスト中、「998244353」でググったらフーリエ変換とか出てきて泣きそうでしたが、この記事で救われました。
「1000000007 で割ったあまり」の求め方を総特集！ 〜 逆元から離散対数まで 〜 - Qiita
覚えること
10^19を超えるような数を扱うときは、modを使って計算しちゃおう！
知っとこポイント②：順列、階乗の計算
さて、こっちはどちらかというと実装ではまった点。
この問題を解くとき、順列や階乗の計算をします。
階乗は、5! = 5*4*3*2*1 などすべて掛け算だけで表せますね。
ただ、順列は公式通り考えると、n P r = n! / (n-r)! となります。そのため、実装で割り算を使います。
以下の記事がその実装を解説しています。
【基本C++】順列のプログラム - Qiita
これを使ってしまうと、ポイント①で触れたようにmodを考える上で注意が必要な割り算が出てきてしまいます。
その場合、ポイント①で参考に挙げた記事内に実装がありますが、さらにforループを回す必要が出てきてしまいます。
そのため、コードは複雑になり（順列のメソッドの中に、modの割り算をするような処理を加える）、forループが追加で入るので計算量も増えます。
ということで、順列の実装はこちらの方法を代わりに使いました。
こちらは、割り算ではなく、forループを後ろから考えることで掛け算だけで済ましています。
確かに、例えば7P3なら7*6*5で後ろから掛け算していけば終わりですよね。
【C++】順列を求めるプログラム - Qiita
覚えること
順列の計算は、掛け算だけで行おう！
自分の回答
私は前者の方法で最初実装していて、TLE（制限時間の2秒以内に計算が終わらない）になってしまいました。
ただ、後者の方法に変えたら、AC（すべてOK）になりました。
ACしたコードを載せておきます。自分用ですが、コメントとかもきれいにつけてみました。
ただ、おそらく競プロerの常識とは違う書き方になっているはず。
Submission #32801198 - AtCoder Regular Contest 143
・こう書いた方がより良いよ
・計算量のオーダーがこれからこれに変わったからTLEがACになったんだよ
というコメント、あれば非常にうれしいです。お待ちしております。
おわりに
ちょっと散文チックな記事になってしまいました。
昨日の復習をしていて、modで計算することに少し感動したので、こうして記事にしてみました。
こういうの、情報系の人なら大学で学ぶんだろうか。
kaggleもそうだったけど、全くの初心者から中級者になるとき、誰かコーチしてくれる人がいると効率が段違いだなぁ、とひしひしと感じております。
ただ、AtCoderは書籍とかブログも充実してるので、kaggleよりはやりやすそう。
とりあえず飽きるまでは、頑張っていきます。
UnicodeとUTF-8ってどういう関係があるんだっけ…夏。
最近暑い日が続きますね。皆さんいかがお過ごしでしょうか。
今日は、毎回ググるけど分かった気になって終わってしまう、文字コード関連です。
その中でも、UnicodeとUTF-8の関係について記載していこうと思います。
まずは文字コードについて軽く説明をして、そしてUnicodeについてを解説します。
今回は、この本の内容から一部抽出してまとめています。
文字コードとは？
文字集合
文字コードの前に、まずは文字集合です。
文字集合は、文字を重複なく集めた集合のこと。
例えば、以下はひらがなの文字集合です。
これ以外にも、常用漢字の文字集合やアルファベットの文字集合など、色々な文字集合があります。
文字コード
では、文字コードとは何か。
文字コードは、文字集合の各文字に対するビット組み合わせを一意に定めたものです。
（符号化文字集合とも言います）
例えば、上で示したひらがなの文字集合に対してビット組み合わせを定めた、My文字コードが以下です。
これがPCに実装されていたとしたら、
ビット組み合わせで「000101」「000110」「000111」と入力されたら、「おかき」という文字列が生成されます。
ASCII
その文字コードの中でも、最も基本的なものはASCII（American Standard Code for Information Interchange）です。
ASCIIは7ビットの1バイト文字コードです。つまり、2^7で128個の文字が定められます。
ただ、このすべてに文字が割り当てられているわけではないです。
ASCIIの文字コードは以下です。
英数字の大文字小文字といくつかの記号が割り当てられていますね。
https://www.pahoo.org/e-soul/webtech/encode/encode02-01.shtm
UnicodeとUTF-8/16/32の関係は？
Unicode
さてここまでで文字コードについてが分かりました。
「じゃあUnicodeってのは文字コードなんだね？！その亜種がUTF-8なのかな？！」
と思うかもしれませんが、落ち着きましょう。
Unicodeは、厳密には文字コード（符号化文字集合）ではありません。
wikipediaには、以下のような記載があります。
Unicode（ユニコード）は、符号化文字集合や文字符号化方式などを定めた、文字コードの業界規格。文字集合（文字セット）が単一の大規模文字セットであること（「Uni」という名はそれに由来する）などが特徴である。
つまりどういうことだってばよ？と思っていると思います。
私なりの解釈ですが、つまりUnicodeとは、
世界のあらゆる文字を集めた文字集合に対して、それぞれ番号を割り当てた集合
です。ビット組み合わせではなく独自の番号を割り当てているので、文字コードではないのです。
また、Unicodeはめちゃくちゃたくさんの文字を扱っています。先ほどのひらがなであれば2次元の表で表せましたが、Unicodeはなんと4次元で文字と番号を表します。
その4次元とは、群/面/区/点です。4つを指定すると、文字が一意に決まるわけです。
その4つを指定するとき、Unicodeの番号だよということでU+を頭につけて指定します。
例えば、U+306Cは「ぬ」を表します。
UTF-X
Xには8,16,32が入りますが、これは何なのか。
全て、Unicodeで表した番号をビット組み合わせに変換する方式のことを言います。
その変換する方式の違いで、8,16,32が分かれています。
例えば、先ほどの「ぬ」はUnicodeではU+306Cでした。
それが、UTFシリーズでは以下のようなビット組み合わせに変換されます。（16進数で記載）
UTF-8：E3 81 AC（3バイト）
UTF-16：30 6C（2バイト）
UTF-32：00 00 30 6C（4バイト）
さて、それぞれを軽く説明していきます。
先に言っておくと、UTF-32が一番楽に計算できます。次点がUTF-16。一番複雑なのがUTF-8です。（個人の感想）
UTF-32
UTF-32は4バイト固定です。一番容量を食います。
さて、UTF-32は簡単です。Unicodeの番号をそのままビット組み合わせにしたものが、UTF-32です。
Unicodeは群/面/区/点の4次元で文字を指定していると言いました。つまり、4バイトあれば文字を指定できます。
UTF-32は、4バイト確保しているので、そのままビット組み合わせとして指定できるのですね。
「ぬ」の例でも、U+306Cを「00 00 30 6C」と変換していました。そのままですね。
UTF-16
UTF-16は、基本2バイトなんですが一部4バイトになります。
「基本」と書いたのは、Unicodeの中のBMP（基本多言語面）に当たるものは2バイトで示せ、それ以外は4バイトになるからです。
はい、BMPの説明をします。
元々Unicodeは、16ビット（2バイト）の組み合わせで生まれました。つまり、2^16通りの文字が表せますね。
ですが、途中で「あかん、これだとたりーん！」となってしまったわけです。
なので、32ビット（4バイト）に拡張しました。
ただ、大体主要な文字は16ビット（2バイト）で表せていたんですね。日本語とか、英数字とか。
そのため、主要なこの16ビット（2バイト）の組み合わせを、BMPと言います。
BMPは2バイトの組み合わせで表現可能なので、群と面が00、00固定となります。
BMP以外の文字の例は、よくこの ほっけ と読む文字が出てきます。
𩸽
これは、Unicodeで言うと「U+00029E3D」になります。群は00ですが、面が02となっています。つまり、BMP外の文字ですね。
さて、UTF-16の説明に戻ります。
このBMPに入っている文字であれば、Unicodeの番号をそのままビット組み合わせに変換できます。
つまり、BMP内であればUTF-16もUTF-32も同じ（UTF-32は1，2バイト目が00 00になりますが）です。
では、BMP外の文字を表すとき…その時は、サロゲートペアという仕組みを使います。
この仕組みは、詳しく知りたい方はこの本を買うかググってください。
UTF-8
ラスボスのUTF-8です。
これは、1~4バイトで文字を表します。一番容量がお得な文字コードです。
「ぬ」の例でもありましたが、UTF-8はUnicodeの番号と同じようにあらわせません。
そのため、一番複雑です。
UTF-8：E3 81 AC（3バイト）
UTF-16：30 6C（2バイト）
UTF-32：00 00 30 6C（4バイト）
ざっくりいうと、Unicodeの番号をあるルールに則ってUTF-8のバイト列に変換できます。
それが、以下の表です。
例えば、「ぬ」をUTF-8に変換してみましょう。
Unicodeでは「U+306C」でした。306Cはこの表で言うと3行目に当たりますね。
では次に、306Cは16進数なので、それを2進数に変換すると、こうなります。
0011000001101100
さらにそれを表の右側のバイト列のxに当てはめると、こうなります。
1110xxxx 10xxxxxx 10xxxxxx
↓
11100011 10000001 10101100
さらにさらにこれを16進数したら…「ぬ」のUTF-8でのバイト表現の完成です！
E381AC
ここで確かめてみましたが、合ってそうですね。
【みんなの知識 ちょっと便利帳】URLエンコード/デコードツール = UTF-8
