ためすう

参照渡しを使ってみる (C++)

2020-05-23

確認環境

$ g++ --version
g++ (Homebrew GCC 9.2.0) 9.2.0
Copyright (C) 2019 Free Software Foundation, Inc.
This is free software; see the source for copying conditions.  There is NO
warranty; not even for MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.

調査

test.cpp

#include <bits/stdc++.h>
using namespace std;

void f1(int *a) {
    for (int i = 0; i < 3; i++) {
        a[i] *= 2;
    }
}

void f2(vector<int> &a) {
    for (int i = 0; i < 3; i++) {
        a[i] *= a[i];
    }
}

int main() {
    int a[] {1, 2, 3};
    f1(a);

    vector<int> b = {1, 2, 3};
    f2(b);

    // 関数を通すと値が変わっている
    for (int i = 0; i < 3; i++) {
        cout << a[i] << " ";
    }
    cout << endl;

    for (int i = 0; i < 3; i++) {
        cout << b[i] << " ";
    }
    cout << endl;
}

出力結果

2 4 6
1 4 9

参考

AtCoderで緑色になりました! からの、思い出の問題ベスト3 と やってきたこと少々

2020-05-19

2020/05/10 AtCoder Beginner Contest 167 で緑にタッチすることが出来たので、色変記事でも書こうと思います。

(今後、何度か反復横跳びしそうですが、書いちゃいます。)

普段やっていることで、特に変わったことはないので既出の内容かなと思います。

なので、コンテスト中に対峙した記憶に残る問題ベスト3のことから書いてみます。

rating.png

第3位

E - Crested Ibis vs Monster

初めてコンテスト中に DP を使って AC しました。

雰囲気でやったら、サンプルが合ったので、添字をバグらせまくりながらACしました。

そういえば、この時のコンテストで茶色になりました。

恥ずかしながらコンテスト中に DP を使って解けたのは、これっきり… (頑張ります)

第2位

D - Banned K

直前のC問題でド嵌りして、この問題をやるとき時間がほとんどなかったのですが、15m くらいでギリギリ解けました。

(諦めなければ、何とかなることもあるなと思ったりしました。)

ちなみに、この時のコンテストは、パフォーマンスが悪く冷えましたが、 冷えを少なくできたということでこの問題が印象に残っています。

この時、3連続冷え中でした。まあまあ辛かったです。

第1位

C - Sqrt Inequality

はい。まあまあ問題文が短いアレです。コンテスト中、解けませんでした。

問題自体というより、コンテストの時の記憶補正がかかってます。

一見簡単そうに見えるので、解けなかった時のダメージが大きかったです。

そして、このコンテストを機に、問題をきちんと考えてやろうと思い直しました。


それではさらっと、やってきたことのまとめ書いときます。

初期スペック的なもの

  • 大学受験で数学を勉強したので、嫌いではない(※ 得意ではない)
  • 考えるのは好き(※ 得意ではない)
  • 競争はあんまり好きではない (※ 本当かな?)

やってきたこと

その他、お世話になっているもの

  • AtCoder Problems
    • 神サイト。Virtual Contest もできるし、問題の diff も載っているので、精進するときはこのサイト必ず使ってます。

最後に

緑にタッチするまで、遠かったです。

次の目標は安定して、1000パフォーマンスを出すことかなあと思ってます。

無理せず頑張ります。

競プロ楽しい。

isinf を使ってみる (C++)

2020-05-17

確認環境

$ g++ --version
g++ (Homebrew GCC 9.2.0) 9.2.0
Copyright (C) 2019 Free Software Foundation, Inc.
This is free software; see the source for copying conditions.  There is NO
warranty; not even for MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.

調査

数値が無限大(infinity)であるか判定する。

test.cpp

#include <bits/stdc++.h>
using namespace std;

int main() {
    double tmp = 1e100000 / 1e-10;

    cout << INFINITY << endl;
    cout << std::numeric_limits<float>::infinity() << endl;
    cout << tmp << endl;

    cout << "-- inf --" << endl;
    cout << isinf(INFINITY) << endl;
    cout << isinf(std::numeric_limits<float>::infinity()) << endl;
    cout << isinf(tmp) << endl;

    cout << "-- not inf --" << endl;
    cout << isinf(0) << endl;
    cout << isinf(100) << endl;
}

出力結果

inf
inf
inf
-- inf --
1
1
1
-- not inf --
0
0

参考

データの一意性を保証するとき、データベース (MySQL) で Unique 制約をつけた方が良さそうな件

2020-04-18

みなさんは、どんなときに MySQL で Unique 制約をつけるでしょうか。

「必要ならつける!」が答えなのですが、どんな時に必要でしょうか。

今回は、「MySQL で Unique 制約をつける場面はどんなときか」というのを考えてみたいと思います。

Unique 制約とは

あるテーブル内のカラムのデータが1つであることを保証します。(一意性)

Web アプリケーションの場合で考えてみる

Web アプリケーション (Rails) でデータの一意性を保証したい場合

  1. Web アプリケーション側 (サーバー側) で、データ保存前に検証する
  2. MySQL 側に Unique 制約をつける

で実現すると思います。

さて最初の問いである「MySQL で Unique 制約をつける場面はどんなときか」の答えとして、

  1. Web アプリケーション側 (サーバー側) で、データ保存前に検証する

さえ満たしていれば、

  1. MySQL 側に Unique 制約をつける

は不要でしょうか。いや必要です。

必要になるケースについて見ていきましょう。

確認環境

$ rails --version
Rails 5.2.3

$ mysql --version
mysql  Ver 14.14 Distrib 5.6.43, for osx10.13 (x86_64) using  EditLine wrapper

検証

準備

MySQL

CREATE TABLE `hoges` (
  `id` bigint(20) NOT NULL AUTO_INCREMENT,
  `uniq_test1` int(11) DEFAULT NULL,
  `uniq_test2` int(11) DEFAULT NULL,
  `created_at` datetime NOT NULL,
  `updated_at` datetime NOT NULL,
  PRIMARY KEY (`id`),
  UNIQUE KEY `uniq_test2` (`uniq_test2`)
) ENGINE=InnoDB DEFAULT CHARSET=utf8mb4
INSERT INTO hoges VALUES (null, 11111, 22222, NOW(), NOW());

app/models/hoge.rb

class Hoge < ApplicationRecord
  validates :uniq_test1, uniqueness: true
  validates :uniq_test2, uniqueness: true

  validate :hoge

  def hoge
    sleep(5)
  end
end

Web アプリケーション側 (サーバー側)では、uniq_test1、uniq_test2 ともにデータ保存前に検証します。

今回は、rails console でモデルを create します。

$ rails c
Running via Spring preloader in process 12528
Loading development environment (Rails 5.2.3)
irb(main):002:0> ActiveRecord::Base.transaction do
irb(main):003:1* Hoge.create(uniq_test1: 5, uniq_test2: nil)
irb(main):004:1> end
   (1.9ms)  BEGIN
  Hoge Exists (6.3ms)  SELECT  1 AS one FROM `hoges` WHERE `hoges`.`uniq_test1` = 5 LIMIT 1
  Hoge Exists (9.9ms)  SELECT  1 AS one FROM `hoges` WHERE `hoges`.`uniq_test2` IS NULL LIMIT 1
  Hoge Create (4.0ms)  INSERT INTO `hoges` (`uniq_test1`, `created_at`, `updated_at`) VALUES (5, '2020-03-09 16:42:39', '2020-03-09 16:42:39')
   (6.9ms)  COMMIT
=> #<Hoge id: 6, uniq_test1: 5, uniq_test2: nil, created_at: "2020-03-09 16:42:39", updated_at: "2020-03-09 16:42:39">

処理のおおまかな流れはこんな感じです。

  1. MySQL の transaction 開始
  2. データの一意性検証
  3. MySQL の transaction 終了 (ここでデータが作られる)

問題になるのはほぼ同時に処理が実行されたときです。

MySQL に Unique キー制約なし (悪いパターン)

コンソール1

$ rails c
Running via Spring preloader in process 12742
Loading development environment (Rails 5.2.3)
irb(main):001:0> ActiveRecord::Base.transaction do
irb(main):002:1* Hoge.create(uniq_test1: 5, uniq_test2: nil)
irb(main):003:1> end
   (2.2ms)  SET NAMES utf8mb4,  @@SESSION.sql_mode = CONCAT(CONCAT(@@sql_mode, ',STRICT_ALL_TABLES'), ',NO_AUTO_VALUE_ON_ZERO'),  @@SESSION.sql_auto_is_null = 0, @@SESSION.wait_timeout = 2147483
   (1.1ms)  BEGIN
  Hoge Exists (3.2ms)  SELECT  1 AS one FROM `hoges` WHERE `hoges`.`uniq_test1` = 5 LIMIT 1
  Hoge Exists (1.4ms)  SELECT  1 AS one FROM `hoges` WHERE `hoges`.`uniq_test2` IS NULL LIMIT 1
  Hoge Create (4.3ms)  INSERT INTO `hoges` (`uniq_test1`, `created_at`, `updated_at`) VALUES (5, '2020-03-09 16:55:12', '2020-03-09 16:55:12')
   (7.9ms)  COMMIT
=> #<Hoge id: 7, uniq_test1: 5, uniq_test2: nil, created_at: "2020-03-09 16:55:12", updated_at: "2020-03-09 16:55:12">

コンソール2

$ rails c
Running via Spring preloader in process 12757
Loading development environment (Rails 5.2.3)
irb(main):001:0> ActiveRecord::Base.transaction do
irb(main):002:1* Hoge.create(uniq_test1: 5, uniq_test2: nil)
irb(main):003:1> end
   (1.8ms)  SET NAMES utf8mb4,  @@SESSION.sql_mode = CONCAT(CONCAT(@@sql_mode, ',STRICT_ALL_TABLES'), ',NO_AUTO_VALUE_ON_ZERO'),  @@SESSION.sql_auto_is_null = 0, @@SESSION.wait_timeout = 2147483
   (1.5ms)  BEGIN
  Hoge Exists (2.0ms)  SELECT  1 AS one FROM `hoges` WHERE `hoges`.`uniq_test1` = 5 LIMIT 1
  Hoge Exists (5.1ms)  SELECT  1 AS one FROM `hoges` WHERE `hoges`.`uniq_test2` IS NULL LIMIT 1
  Hoge Create (5.1ms)  INSERT INTO `hoges` (`uniq_test1`, `created_at`, `updated_at`) VALUES (5, '2020-03-09 16:55:13', '2020-03-09 16:55:13')
   (49.3ms)  COMMIT
=> #<Hoge id: 8, uniq_test1: 5, uniq_test2: nil, created_at: "2020-03-09 16:55:13", updated_at: "2020-03-09 16:55:13">

Web アプリケーション側 (サーバー側) をすり抜けてしまいました!!!

MySQL に Unique キー制約あり (良いパターン)

コンソール1

$ rails c
Running via Spring preloader in process 12742
Loading development environment (Rails 5.2.3)
irb(main):001:0> ActiveRecord::Base.transaction do
irb(main):002:1* Hoge.create(uniq_test1: nil, uniq_test2: 77777)
irb(main):003:1> end
   (3.7ms)  BEGIN
  Hoge Exists (1.4ms)  SELECT  1 AS one FROM `hoges` WHERE `hoges`.`uniq_test1` IS NULL LIMIT 1
  Hoge Exists (2.8ms)  SELECT  1 AS one FROM `hoges` WHERE `hoges`.`uniq_test2` = 77777 LIMIT 1
  Hoge Create (3.5ms)  INSERT INTO `hoges` (`uniq_test2`, `created_at`, `updated_at`) VALUES (77777, '2020-03-09 16:57:01', '2020-03-09 16:57:01')
   (18.2ms)  COMMIT
=> #<Hoge id: 9, uniq_test1: nil, uniq_test2: 77777, created_at: "2020-03-09 16:57:01", updated_at: "2020-03-09 16:57:01">

コンソール2

$ rails c
Running via Spring preloader in process 12757
Loading development environment (Rails 5.2.3)
irb(main):001:0> ActiveRecord::Base.transaction do
irb(main):002:1* Hoge.create(uniq_test1: nil, uniq_test2: 77777)
irb(main):003:1> end
   (7.9ms)  BEGIN
  Hoge Exists (3.7ms)  SELECT  1 AS one FROM `hoges` WHERE `hoges`.`uniq_test1` IS NULL LIMIT 1
  Hoge Exists (1.8ms)  SELECT  1 AS one FROM `hoges` WHERE `hoges`.`uniq_test2` = 77777 LIMIT 1
  Hoge Create (5.4ms)  INSERT INTO `hoges` (`uniq_test2`, `created_at`, `updated_at`) VALUES (77777, '2020-03-09 16:57:04', '2020-03-09 16:57:04')
   (19.1ms)  ROLLBACK
Traceback (most recent call last):
        2: from (irb):4
        1: from (irb):5:in `block in irb_binding'
ActiveRecord::RecordNotUnique (Mysql2::Error: Duplicate entry '77777' for key 'uniq_test2': INSERT INTO `hoges` (`uniq_test2`, `created_at`, `updated_at`) VALUES (77777, '2020-03-09 16:57:04', '2020-03-09 16:57:04'))

Web アプリケーション側 (サーバー側) をすり抜けたとしても、MySQL に保存したときに MySQL 側のエラーで弾くことができます。

まとめ

データの一意性を保証する必要があるなら、MySQL に Unique キーをつけましょう!

副次的なメリットとして、Web アプリケーション側 (サーバー側) の実装漏れがあった場合も対処できます。

_GLIBCXX_DEBUG を使ってみる (C++)

2020-04-18

確認環境

$ g++ --version
g++ (Homebrew GCC 9.2.0) 9.2.0
Copyright (C) 2019 Free Software Foundation, Inc.
This is free software; see the source for copying conditions.  There is NO
warranty; not even for MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.

調査

_GLIBCXX_DEBUG あり

test.cpp

#define _GLIBCXX_DEBUG

#include <bits/stdc++.h>
using namespace std;

int main() {
    vector<int> a(5);

    cout << "---1---" << endl;
    a[1] = 20;
    cout << a[1] << endl;
    cout << "---2---" << endl;
    a[10000000] = 99;
}

出力結果

---1---
20
---2---
/usr/local/Cellar/gcc/9.2.0/include/c++/9.2.0/debug/vector:427:
In function:
    std::__debug::vector<_Tp, _Allocator>::reference
    std::__debug::vector<_Tp,
    _Allocator>::operator[](std::__debug::vector<_Tp,
    _Allocator>::size_type) [with _Tp = int; _Allocator =
    std::allocator<int>; std::__debug::vector<_Tp, _Allocator>::reference =
    int&; std::__debug::vector<_Tp, _Allocator>::size_type = long unsigned
    int]

Error: attempt to subscript container with out-of-bounds index 10000000, but
container only holds 5 elements.

Objects involved in the operation:
    sequence "this" @ 0x0x7ffeebcfa610 {
      type = std::__debug::vector<int, std::allocator<int> >;
    }
Abort trap: 6

_GLIBCXX_DEBUG なし

test.cpp

#include <bits/stdc++.h>
using namespace std;

int main() {
    vector<int> a(5);

    cout << "---1---" << endl;
    a[1] = 20;
    cout << a[1] << endl;
    cout << "---2---" << endl;
    a[10000000] = 99;
}

出力結果

---1---
20
---2---
Segmentation fault: 11

_GLIBCXX_DEBUG ありだと、エラーの原因も記載されています。

参考

外部ファイルを読み込む (C++)

2020-04-12

確認環境

$ g++ --version
g++ (Homebrew GCC 9.2.0) 9.2.0
Copyright (C) 2019 Free Software Foundation, Inc.
This is free software; see the source for copying conditions.  There is NO
warranty; not even for MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.

調査

sample.txt

aaa
bbb
222
ccc

test.cpp

#include <bits/stdc++.h>
#define rep(i, n) for (int i = 0; i < (n); ++i)
#define sz(x) int(x.size())
using namespace std;
typedef long long ll;
typedef pair<int, int> P;

const ll INF = 1LL << 60;

int main() {
    ifstream ifs("sample.txt");
    if (!ifs) {
        cout << "Miss" << endl;
    } else {
        // getを使って読み込むパターン
        // char c;
        // while (ifs.get(c)) {
        //     cout << c;
        // }

        // getline を使って読み込むパターン
        char s[100];
        while (ifs.getline(s, 100)) {
            cout << s << endl;
        }
    }
}

出力結果

aaa
bbb
222
ccc

参考

std::count を使ってみる (C++)

2020-04-05

確認環境

$ g++ --version
g++ (Homebrew GCC 9.2.0) 9.2.0
Copyright (C) 2019 Free Software Foundation, Inc.
This is free software; see the source for copying conditions.  There is NO
warranty; not even for MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.

調査

test.cpp

#include <bits/stdc++.h>
using namespace std;

int main() {
    vector<int> v = {3, 4, 3, 1, 2, 3};

    cout << "idx: 0 ~ 2 の範囲で 3 の数" << endl;
    cout << count(v.begin() + 0, v.begin() + 3, 3) << endl;

    cout << "idx: 0 ~ 1 の範囲で 3 の数" << endl;
    cout << count(v.begin() + 0, v.begin() + 2, 3) << endl;

    cout << "idx: 0 ~ 5 の範囲で 3 の数" << endl;
    cout << count(v.begin() + 0, v.begin() + 6, 3) << endl;
    cout << count(v.begin() + 0, v.end(), 3) << endl;

    cout << "idx: 2 ~ 5 の範囲で 3 の数" << endl;
    cout << count(v.begin() + 2, v.begin() + 6, 3) << endl;
}

出力結果

idx: 0 ~ 2 の範囲で 3 の数
2
idx: 0 ~ 1 の範囲で 3 の数
1
idx: 0 ~ 5 の範囲で 3 の数
3
3
idx: 2 ~ 5 の範囲で 3 の数
2

参考

<random> ライブラリを使ってみる (C++)

2020-04-05

確認環境

$ g++ --version
g++ (Homebrew GCC 9.2.0) 9.2.0
Copyright (C) 2019 Free Software Foundation, Inc.
This is free software; see the source for copying conditions.  There is NO
warranty; not even for MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.

調査

test.cpp

#include <bits/stdc++.h>
using namespace std;

int main() {
    std::random_device rng;
    for (int i = 0; i < 5; i++) {
        cout << rng() << endl;
    }
    cout << "---" << endl;
    std::mt19937 engine(rng());
    std::uniform_real_distribution<> dist1(-1.0, 1.0);
    for (int i = 0; i < 5; i++) {
        cout << dist1(engine) << endl;
    }

    cout << "-- 1 ~ 10 の整数を等確率で出力する --" << endl;
    std::random_device rng2;
    std::mt19937 engine2(rng2());
    std::uniform_int_distribution<> dist2(1, 10);
    for (int i = 0; i < 5; i++) {
        cout << dist2(engine2) << endl;
    }
}

出力結果

28733216
299212032
131005940
463750635
2721402783
---
-0.179933
-0.992599
-0.705688
-0.27019
-0.209114
-- int -
5
9
10
1
7

参考

swap を使ってみる (C++)

2020-04-04

確認環境

$ g++ --version
g++ (Homebrew GCC 9.2.0) 9.2.0
Copyright (C) 2019 Free Software Foundation, Inc.
This is free software; see the source for copying conditions.  There is NO
warranty; not even for MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.

調査

swap は、

2つの値を入れ替える。

使ってみます。

test.cpp

#include <bits/stdc++.h>
// #define NDEBUG
#include <cassert>
using namespace std;

int main() {
    int x = 100, y = 777;
    cout << "case1" << endl;
    printf("x: %d y: %d\n", x, y);

    cout << "case2" << endl;
    swap(x, y);
    printf("x: %d y: %d\n", x, y);

    cout << "end" << endl;
}

出力結果

case1
x: 100 y: 777
case2
x: 777 y: 100
end

参考

assert を使ってみる (C++)

2020-04-04

確認環境

$ g++ --version
g++ (Homebrew GCC 9.2.0) 9.2.0
Copyright (C) 2019 Free Software Foundation, Inc.
This is free software; see the source for copying conditions.  There is NO
warranty; not even for MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.

調査

assert は、

式が真であることを表明する。

使ってみます。

test.cpp

#include <bits/stdc++.h>
#include <cassert>
using namespace std;

int main() {
    cout << "case1" << endl;
    assert(10 > 5);

    cout << "case2" << endl;
    assert(10 < 5);

    cout << "end" << endl;
}

出力結果

case1
case2
Assertion failed: (10 < 5), function main, file assert.cpp, line 10.
Abort trap: 6

10 < 5 が偽であるため、failed になりました。

参考