Atcoder ABC 154 D - Dice in Lineをpythonで解く
コード本文
ABC154に参戦した。
この頃、競プロを少しかじっているので結構いい感じに解けるんじゃないかと思ったが、Cまでしか解けなくて落胆。
後日、解けなかったD問題を復習した。
以下通ったD問題のコード本文
コード解説
この問題で使うテクニックはしゃくとり法(または累積和)と期待値の基本的な知識
コードの流れは以下の通り
配列に収めたサイコロのそれぞれの期待値を事前に算出しておく。このときp種類の目が出るサイコロの目の期待値は(1+p) / 2であることに注意
しゃくとり法、または累積和を使って期待値の配列から長さがkの最大部分配列を算出する。
私はステップ1の期待値算出のところで期待値を(1+2+...+p) / pと計算してしまいTLEで爆死。
感想
ちょっといいスコア出るんじゃないかなと期待しつつ参戦したのにこの結果はかなり落ち込む。
とりあえず、数学、高校生からやり直してきます。
codelabのFirebase for Flutterを写経した
codelab Firebase for Flutterって何?
これ↓
codelabs.developers.google.com
投票アプリを題材にFlutterとCloudFireStoreの連携方法を学習することができる。
英語だが非常にわかりやすい教材。
学んだこと
案外dartのコンストラクタについてわかってなかったことに気付かされた。
下のコードは教材で登場するRecord クラス。
gist0a17acd65b073021281c3a1a19b28de2
このうちRecord.fromMapとRecord.fromSnapshotはNamed Constructorと呼ばれるコンストラクタである。
さらにNamed Constructorはコロンに続けてカンマ区切りで初期動作を定義することができる。
いつもここはどういう動作をしてるんだろうなとなんとなく思いながらプログラムをノリで読んでいたが、スッキリ。
詳しい説明は下のサイトを参照
Flutter でヌメロンゲームを作った(iPhoneアプリ・Android アプリ)
作った。
状態管理にはProviderを使っている。
ヌメロンって?
ヌメロンゲームとは相手プレイヤーがきめた3桁の数字を当てるゲーム
順番に数字を聞いていくことができ、そのフィードバックとして、聞いた三桁の数字のうち、桁があっているもの(ヒット)、桁はあっていないが正解に含まれているもの(バイト)の個数を得ることができる。
例えば正解が123であって、135と聞いた場合は、1ヒット、1バイトとなる。(1は桁あっているのでヒット。3は桁はあっていないが正解に含まれているのでバイト)
ちなみにこのゲームはバナナマンが司会をしていたテレビ番組「ヌメロン」で取り扱われていた。
あともっと遡ると、古畑任三郎シリーズにもこのゲームは登場する。
コード
コードは下のgithubで見る事ができる。
作りが荒くなっているところがあるのはご愛嬌。
まだ、dartにまだなれきっていないのでPythonならもっときれいに書けるのに。。。ともどかしくなってしまう部分が多くあった。
もっと鍛錬する必要あり。
FlutterでFirebaseをいじったときに詰まったこと一覧
Flutterとは
同じソースコードでiOSもAndroidも対応したアプリが作れるやつ。
Google製でFirebaseとの連携を推している。
連携を題材にした多くのチュートリアルがweb上にあり、初心者でも入りやすい環境が整っている。
僕が触ってみた連携のチュートリアルは下の2つ
ところどころ詰まったところがあったのでまとめる。
あくまで備忘録なので書きなぐりになっているがあしからず。。。
- codelabs
Firebase Authを利用するとAndroidのビルドが通らない
どんなエラーメッセージが出たかメモし忘れてしまったが症状は小見出し通り。
解決法
下のstackoverflowを参考にプラグインのバージョンを上げることで解決した。
codelabのチュートリアルで指定されたプラグインのバージョンが古く、そのままではビルドが通らない。注意。
The email address is badly formatted.
FirebaseAuthにEmailを投げたところフォーマットが合ってないよと怒られた。
Youtubeのコードそのまま書いたがだめだった。
解決法
Emailを変数に格納する際にtrimメソッドを使ってやる
trimは文字列クラスが持つメソッドで文字列の先頭、末尾の空白を消す。
(旧) _email = input
(新) _email = input.trim()
AuthResultとFirebaseUserについて
AuthReseltであるべきところをFirebaseUserを指定しているために型が合わないと言われる。
FirebaseUser user = await FirebaseAuth.instance .signInWithEmailAndPassword(email: _email, password: _password);
解決法
このように書き換える
FirebaseUser user = (await FirebaseAuth.instance .signInWithEmailAndPassword(email: _email, password: _password)).user;
firebase_authとcloud_firestoreを同時併用した際に怒られた
こんな感じで怒られた。
com.android.builder.dexing.DexArchiveMergerException: Error while merging dex archives flutter
解決法 android/app/build.gradleにあるminSdkVersion を21に設定する。
FlutterでFirestoreのfirebase_authプラグイン使用時に遭遇したエラーの解決方法
Android でビルドしたときにError: ADB exited with exit code 1 Performing Streamed Installと怒られた
題の通り
解決方法
Android Studio -> AVDManager -> Actionsにある▼ -> wipe data
Intelli jでandroidのエミュレータが突然起動できなくなってしまった。
Intellijのエディタ画面右上からエミュレータを起動しようとしたらiOSのエミュレータしか表示されなくなってしまった。
解決方法 Android Studio -> AVDManager -> 起動したいエミュの▶を押す
firebaseAuthでサインアップしようとしたらAn internal error has occurred. [ 7: ]と怒られる
題の通り
解決方法 エミュレータの再起動で解決した。
PlatformException(Error performing setData, PERMISSION_DENIED: Missing or insufficient permissions., null)と怒られた
解決方法 下にあるとおりにcloudstoreのルールをいじる
PythonのASCIIコードと文字列の変換
AtCoderABC146のB問題で「与えられた文字列をアルファベット順に任意の順番分進めろ」という問題が出た。
少し戸惑ったがPythonのchr関数、ord関数を使うとかんたんに溶けた
提出コード
gistefb6627090be1b4198b188589421dcbe
解説
与えられたアルファベットを一度ASCIIコードにエンコードし、任意の演算操作を加え、chr関数でもとの文字列にデコードしてやるという流れ。
ASCIIコードにエンコードしてから演算操作してやることで「文字列をアルファベット順にすすめる」という操作や、「zになったらaから演算し直す」といった一見複雑な操作もできる。
文字列操作に慣れていないのでチョット戸惑った。
公式ドキュメントのord関数の説明
1 文字の Unicode 文字を表す文字列に対し、その文字の Unicode コードポイントを表す整数を返します。例えば、 ord('a') は整数 97 を返し、 ord('€') (ユーロ記号) は 8364 を返します。これは chr() の逆です。
機械学習(分類タスク)で用いる評価指標についてわかりやすくまとめる
題名のとおり。
今日もアウトプットする
予測値の分け方
評価指標について説明する前に、機械学習の予測(分類タスク)は以下のような種類に分けられることを紹介しよう。
- TP(True Positive)
- TF(True False)
- FP(False Positive)
- FN(False Negative)
True/Falseは予測があっていたか、Positive/Negativeは予測値が正例かどうかを示している。
すなわち正例と予測し、合っていたらTPというわけだ。
少しややこしいので例で説明しよう。
ここにAIドクターがいる。
AIドクターは患者がガンかどうか見極める。(ガンだったら正例)
おや一人患者が来たようだ。。。
AIドクター「オマエ、チョット、ガン、ダトオモウワ」
早速、メスを取り出し、患者に手術するAIドクター。
しかし、どうやらガンは見つからなかったらしい。
AIドクター「マチガエチッタ。テヘペロ。」
この例をまとめるとAIドクターは患者をガンを患っていると予測したが(Positive)、誤診(False)だったのでFP(False Positive)となる。
評価指標
予測値の分け方を紹介した上で評価指標をいくつか説明する。
- Accuracy
- Precision
- Recall
- F1 value
Accuracyは以下のように計算できる。 一番直感的にこの指標がわかりやすいかもしれない。 単純に予測のいわゆる正解率を出している。
Accuracy = (TP + TN) / (全データ)
Precisionは以下のように計算できる。 これが意味するのは正例と予測した中にどれだけ間違いがあるかということである。 逆に言えば正例の取りこぼしのペナルティは全くない。(先の例で言えばがん患者を手術せず家に返しても医者の評価は下がらない)
Precision = TP / (TP + FP)
Recallは以下のように計算できる。 これが意味するところは真の値が正例であるものをどれだけ正確に予測できたかということである。 先の例で言えば、間違えて手術してもペナルティはまったくないということである。(積極的な診断をする医者の評価は高くなる)
Recall = TP / (TP + FN)
F1 valueはRecallの調和平均を撮ったものである。 PrecisionとRecallはトレードオフの関係にあり、この調和平均を取ることで2つの特性についてバランスの良い指標になるのである。
終わりに
まぁ他にも分類タスクでの指標はいっぱいあるけど今日はこのへんで。。。
書くこと思いつかないからマージソートについてまとめる
前回の記事で1週間に2記事書くと宣言した手前、何も書くことが思いつかないので自分の勉強のためにもマージソートについてまとめる。
マージソートのざっくりイメージ
「マージ(merge)」という単語の意味する通り、一度配列をバラバラに分解してから、結合していきながらソートを遂行するアルゴリズム。
下はイメージ図。ガバガバだけどないよりは良いだろう
バブルソートなどのO(N2)のアルゴリズムよりも早い。(後述)
マージの方法
マージソートの美しいところはマージの仕方にある。
マージソートはマージする部分配列がそれぞれソート済みであるということをうまく使って、効率的にソートを完了する。
具体的に見ていく。
下の図はマージソートが実行されている様子をあらわしたもの(まぁ1ステップ分しか書いてないのだが。)
マージソートではマージ時に部分配列の未マージ状態の端の要素のみを比較する。(下図においては1と5)
これは部分配列がソート済みであるために他の要素はマージ対象になりえないためである。(下図においてはマージ先の配列の0番目の要素(最小値)を探す際、最小値になり得るのは部分配列の最小値のどちらか(1と5)しかなりえない)
この操作を繰り返すことでソートをされたマージ配列ができる。
さらに、このマージ操作は2つの部分配列長分の繰り返し操作しか行わないので、計算量はO(N+M)となる(各部分配列長をN, Mとして)
マージソートの計算量と良くないところ
マージソートは各段階のマージにO(N)、マージをlog2N段階分おこなうので、計算量はO(NlogN)となる。
バブルソートなどよりも時間計算量は優れていると言える。
しかし、マージソートはマージのためにN分のメモリ領域が入力の別に必要になるというデメリットがある。(wikiによるとそれがいらないようにインプレースで処理を行うマージソートのバリエーションもあるらしい。)