社内se × プログラマ × ビッグデータ

プログラミングなどITに興味があります。

AtCoder ABC003 B - AtCoderトランプ

atcoder.jp

使用言語は”Java8 (OpenJDK 1.8.0)”です。
取りあえず要件を満たすようにストレートに書いてみて、「こんな冗長なコードは通らないだろうな」と思ったら、一応結果はACでした。
解説を見ても、基本的なロジックは同じように思います。
AtCoder Beginner Contest 003 解説

import java.util.Scanner;
 
class Main {
  public static void main(String[] args) {
    Scanner sc = new Scanner(System.in);
    String S = sc.next();
    String T = sc.next();
    String[] arrS = S.split("");
    String[] arrT = T.split("");
    for (int i = 0; i < S.length(); i++) {
    // 同じ文字であるかをチェックする
      if (!arrS[i].equals(arrT[i])) {
        // もし S 側の文字が "@" だったら、T 側のもじが 'a','t','c','o','d','e','r' の何れであるかをチェックする
        if (arrS[i].equals("@")) {
          if (arrT[i].equals("a") || arrT[i].equals("t") || arrT[i].equals("c") || arrT[i].equals("o") || arrT[i].equals("d") || arrT[i].equals("e") || arrT[i].equals("r")) {
          } else {
            System.out.println("You will lose");
            System.exit(0);
          }
        // もし T 側の文字が "@" だったら、S 側のもじが 'a','t','c','o','d','e','r' の何れであるかをチェックする
        } else if (arrT[i].equals("@")){
          if (arrS[i].equals("a") || arrS[i].equals("t") || arrS[i].equals("c") || arrS[i].equals("o") || arrS[i].equals("d") || arrS[i].equals("e") || arrS[i].equals("r")) {
          } else {
            System.out.println("You will lose");
            System.exit(0);
          }
        } else {
          System.out.println("You will lose");
          System.exit(0);
        }
      }
    }
    // 最後まで NG のチェックにかからなければ、"You can win."
    System.out.println("You can win");
  }
}

単回帰分析の回帰直線の傾きと切片を求める式

実験データのような誤差を含む値から、 それにフィットするような関数を求めるために最小二乗法が使われるようです。
blueskyarea.hatenablog.com

ついては、以下の数式の J を最小にする直線の a (傾き) と b(切片) を求めれば良いことになると思われます。

\displaystyle{
J=\sum_{i=1}^n (y _ i-ax _ i-b)^ 2
}

言い換えると、Jを最小化することが最小二乗法の目標になりそうです。
Jを最小にするには「極値となる点では、微分した結果が0になる」ということを利用して求めます。

ax^ 2
a > 0 の時、下に凸な二次関数
a < 0 の時、上に凸な二次関数
Jは下に凸な二次関数なのでこれで最小値が求まるはずです。

f:id:blueskyarea:20200111171646p:plain

今具体的に求めたいのはaとbの値なので、それぞれについて偏微分していきます。
偏微分とは、「特定の文字以外定数だとみなして」微分していくことです。

a に対する偏微分

\displaystyle{
\frac{∂J}{∂a}=\sum_{i=1}^n (y _ i-ax _ i-b)^ 2
}

\displaystyle{
\frac{∂J}{∂a}=-2\sum_{i=1}^n x(y _ i-ax _ i-b)
}

b に対する偏微分

\displaystyle{
\frac{∂J}{∂b}=\sum_{i=1}^n (y _ i-ax _ i-b)^ 2
}

\displaystyle{
\frac{∂J}{∂b}=-2\sum_{i=1}^n (y _ i-ax _ i-b)
}

それぞれをイコール0として、以下の連立方程式を解く。

\displaystyle{
\frac{∂J}{∂a}=-2\sum_{i=1}^n x(y _ i-ax _ i-b)=0
}

\displaystyle{
\frac{∂J}{∂b}=-2\sum_{i=1}^n (y _ i-ax _ i-b)=0
}

結論を書くと、a(傾き)については、以下のような式で求められるはずです。

\displaystyle{
a=\frac{Sxy}{Sxx}
}

\displaystyle{
Sxx=\sum_{i=1}^n (x _ i-ave(x))^ 2
}

\displaystyle{
Sxy=\sum_{i=1}^n (x _ i-ave(x))(y _ i-ave(y))
}

ここで Sxx は x の分散で、Sxy は x,y の共分散のことになります。
あとは、 b(切片) については

\displaystyle{
y = ax + b
}

\displaystyle{
b = y - \frac{Sxy}{Sxx}x
}

ブログで少し複雑な数式を書くのかなり大変です。。

TOEIC の受験票が届かなかった話

TOEIC 受験をネットで申し込んで、e-mail にて申し込み完了通知を受取。
受験の2週間前に e-mail にて受験票送付の案内がありましたが、1週間経過しても届かず。
この場合、受験前に「受験票が届いていない旨」を電話で連絡する必要があります。

受験票が届いていない旨の連絡

電話で連絡すると、音声案内に従ってボタンをプッシュ。
「受験票未着」に対する音声案内は無かったものの、オペレータさんが出た途端「未着に関する問合せですね?」と言われたので、恐らく電話番号がそれ専用のものと思われます。
その電話では、「受験番号」と「試験会場」を案内されるので、それを控えます。
当日の持ち物に関しては、公式ホームページで確認するようにとのこと。

  • HBの鉛筆
  • 消しゴム
  • 4 × 3 cm の証明写真が貼付された受験票(今回は受験票が無いので、写真のみ)
  • 身分証明書(免許証など)
  • 腕時計

などが該当します。

そして試験当日は受付にて、受験票が届いていなかった旨を伝えるように言われました。
そのときに、「受験番号」を伝える必要があるので、くれぐれも間違えないように復唱して確認されました。

当日の受付

試験会場の受付にて、受験票が届いていなかった旨を伝えます。
すると、「予備受験票」と呼ばれるものをその場で作成することになりますが、ここに「受験番号」を記入する必要がありました。
証明写真はその「予備受験票」に貼付します。
※貼り付けるための、のりは貸してくれました

あとは、身分証明書と共に本人確認を行い、試験会場に入ることが出来ました。

単回帰分析の解を求めるのに最小二乗法を使うらしい

scikit-learn(サイキット・ラーン)を使うと、単回帰分析を(なんとなく)手軽にできました。

ただ、ライブラリに頼りっぱなしではなくて、そのアルゴリズムや計算をある程度理解したいと言う想いがあります。
使わないで計算で求める場合、”最小二乗法”を使うようですが、"最小二乗法"は聞いた覚えはあるけど、どんなものであったか覚えていません。

自分なりに分かり易かったのは以下の図で、存在している全てのデータからなるべく近い位置で引ける直線を求めることになるかと思います。

f:id:blueskyarea:20200111162831p:plain

ある直線は y = ax + b という一次方程式の形で表せるので、y - ax -b の絶対値がそのデータと直線の距離ということになります。
そして全てのデータからの距離を考える必要があるため、距離の二乗和が最小となるような解を求める必要があります。

\displaystyle{
J=\sum_{i=1}^n (y _ i-ax _ i-b)^ 2
}

この J を最小にする直線の a (傾き) と b(切片) を求めれば良いことになると思われます。
たしかにその直線であれば、そのデータの説明変数から目的変数を推測することができそうです。
これを求めるためには”偏微分”というキーワードが出てきました。
引き続き調べて、次は出来ればプログラム書いてみます。

AtCoder Count Triplets

atcoder.jp

競技プログラミングはあまり得意ではないですが、たまに挑戦しています。
上の課題については、最初に書いたのが、すべての数字を一つずつチェックする方法です。
以下のようにすぐに書けた(Java)のは良かったですが、for を3重で回しており、処理速度が遅過ぎました。

public class Main {
  public static void main(String args[]){
    Scanner sc = new Scanner(System.in);
    int N = sc.nextInt();
    List<Integer> list = new ArrayList<>();
    for (int i = 1; i <= N; i++) {
      list.add(sc.nextInt());
    }
    
    int count = 0;
    for (int i = 0; i < N; i++) {
      int target = list.get(i);
      for (int j = i + 1; j < N; j++) {
        if (target < list.get(j)) {
          int nextTarget = list.get(j);
          for (int k = j + 1; k < N; k++) {
            if (list.get(k) < nextTarget) {
              count++;
            }
          }
        }
      }
    }
    System.out.println(count);
  }
}

より良い回答を得るためのポイントとして、以下のことを考慮する必要がありました。
1.i, j, k のうち j を固定し、j より左で Aj より小さいものの数を lj , 右で Aj より小さいものの数を rj とする。
2.lj ∗ rj を足していく。
3.時間計算量は O(N2) になる。
4.Long 型で数値を扱う。

数学やこういったプログラミングに慣れていないと、案外思いつかないものかもしれません。

Docker mysql8.0 コンテナ作成した後

mysql に root でログイン

$ docker-compose exec mysql8-db bash -c 'mysql -uroot'

新しいユーザーの作成
grant コマンドで一気に作成しようとするが失敗。mysql8では許されていないらしい。

mysql> grant all privileges on *.* to 'blueskyarea'@'localhost' identified by 'area';
ERROR 1064 (42000): You have an error in your SQL syntax; check the manual that corresponds to your MySQL server version for the right syntax to use near 'identified by 'area'' at line 1

以下のように create user でユーザー作成してから、grant で権限追加する。

mysql> create user 'blueskyarea'@'localhost' identified by 'area';
Query OK, 0 rows affected (0.01 sec)

mysql> grant all on *.* to 'blueskyarea'@'localhost' with grant option;
Query OK, 0 rows affected, 1 warning (0.01 sec)

mysql> flush privileges;
Query OK, 0 rows affected (0.01 sec)

作成したユーザーでログイン

mysql> quit;
Bye
$ docker-compose exec mysql8-db bash -c 'mysql -ublueskyarea -parea'

データベースの生成
データベースを生成して選択する。

mysql> create database bluesky;
Query OK, 1 row affected (0.01 sec)

mysql> use bluesky;
Database changed

データのインポート

mysql> source /tmp/SQLExample.sql
Query OK, 1 row affected (0.01 sec)

Docker mysql8.0 Could not open file '/var/log/mysql/mysql-error.log' for error logging: Permission denied

Ubuntu18.04 上で発生した問題(Macでは発生しない?)
権限の問題であるようには見えるので、無理やり権限を変更してみる。
下記の変更で動作するようになりました。

変更前
docker-compose.yml

version: "3"
services:
  mysql8-db:
    image: mysql:8.0
    volumes:
      - db8-store:/var/lib/mysql
      - db8-log-store:/var/log/mysql
      - ./conf/my.cnf:/etc/mysql/conf.d/my.cnf
    environment:
      - MYSQL_DATABASE=${DB_NAME}
      - MYSQL_USER=${DB_USER}
      - MYSQL_PASSWORD=${DB_PASS}
      - MYSQL_ROOT_PASSWORD=${DB_PASS}
      - TZ=${TZ}
    ports:
      - ${DB_PORT}:3306

volumes:
  db8-store:

Dockerfileなし

変更後
docker-compose.yml

version: "3"
services:
  mysql8-db:
    build:
      context: "."
      dockerfile: Dockerfile
    volumes:
      - db8-store:/var/lib/mysql
      - db8-log-store:/var/log/mysql
      - ./conf/my.cnf:/etc/mysql/conf.d/my.cnf
    environment:
      - MYSQL_DATABASE=${DB_NAME}
      - MYSQL_USER=${DB_USER}
      - MYSQL_PASSWORD=${DB_PASS}
      - MYSQL_ROOT_PASSWORD=${DB_PASS}
      - TZ=${TZ}
    ports:
      - ${DB_PORT}:3306

volumes:
  db8-store:
  db8-log-store:

Dockerfile

FROM mysql:8.0
RUN mkdir /var/log/mysql
RUN chown mysql:mysql /var/log/mysql