理系の気ままメモ

自分の興味のあることや発見したことや思ったことなどを自由気ままに書くブログ。

競技プログラミングに使えそうなC++のSTLをまとめる

Pairについて

今度書きます。

std::Setについて

概要

setは順序付き集合。同じ値は保持しない。データの追加、削除、検索はO(logN)。重複はなく、キーに対して自動でソートされてデータが保持される。

準備

setを使用するためには

#include <set>

を記述する必要がある。

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

int main() {
    set<int> s;
    s.insert(2);    //データの追加はO(logN)
    s.insert(10);
    s.insert(6);
    s.insert(100);

    s.erase(100);   //データの消去はO(logN)

    auto itr = s.find(10); //値を検索。値が獣所付き集合に含まれないときはend()を返す。O(logN)
    cout << "10:" << s.count(10) << endl; //値の個数を返す。setは重複がないので1又は0のみ。O(logN)
    cout << "100:" << s.count(100) << endl;
    cout << "size:" << s.size() << endl; //集合に含まれる要素の個数を返す。
}

参考サイト
C++ 順序付集合 std::set 入門
set - C++ Reference

競技プログラミングのためにC++で使えそうなことをまとめる

自分用にまとめます。ちょくちょく更新していくと思います。

C++で浮動小数点について、表示桁数を指定する。

ライブラリ:iomanip
関数:
setprecision(int n)

#include <iostream>
#include <iomanip>
using namespace std;

int main() {
    double a = 13.1415926535;
    cout << setprecision(10) << a << endl;
    cout << fixed << setprecision(10) << a << endl;
}

出力

13.14159265
13.1415926535

メモ:
fixedを使うと、整数部分も含めてsetprecisionで指定した桁数で表示される。
fixedを使わなければ、整数部分を含めずにsetprecisionで指定した桁数で表示される。

参考サイト(cppreference.com)
std::setprecision - cppreference.com
std::fixed, std::scientific, std::hexfloat, std::defaultfloat - cppreference.com

√(ルート)の計算

ライブラリ:cmath
関数:
float sqrt(float x)
double sqrt(double x)
long double sqrt(long double x)

double sqrt(Integral x) // C++11 から
float sqrtf(float x) // C++17 から
long double sqrtl(long double x) // C++17 から

#include <cmath>
#include <iomanip>
#include <iostream>
using namespace std;

int main() {
    double a = 3.141592;
    cout << sqrt(a) << endl;
    cout << setprecision(10) << sqrt(a) << endl;
}

出力

1.77245
1.772453667

メモ:
関数がオーバーロードされているので、引数の型によって返り値の方が異なる。

参考サイト(cppreference.com)
sqrt - cpprefjp C++日本語リファレンス

線形代数学(集合と写像)

数学 線形代数学 離散数学

（つづく集合について

定義

集合(set)とは、「数学的に意味のある要素を集めた集まり」すなわち「客観的にその集合の要素に含まれるか否かを判断できる要素の集まり」である。

説明

具体例を示しながらどのようなものが集合として定義できるのかを示したいと思います。ここで、次の二つの条件によって集められる要素の集まりがそれぞれ集合と呼べるのかについて考えてみよう。

「背の高い人の集まり」 (A)

「身長が175cm以上の人の集まり」 (B)

一つ目の(A)について考えてみましょう。背の高い人とは、どのような人のことを指すのでしょうか。身長が170cm以上の人のことでしょうか。175cm以上の人のことでしょうか。背の高い人という条件だけでは、聞いた人によって集合にその要素が含まれるか否かの境界があやふやになります。つまりある人からすれば、背の高い人とは170cm以上の人と思うかもしれませんが、また別の人からすれば、背の高い人とは180cm以上の人のことだと思うかもしれません。このように、人によって集合の境界が異なるような要素の集まりは集合ではありません。

次に２つ目の(B)について考えてみましょう。こちらはどうでしょうか。(A)とは違い、どの人に聞いても身長が175cm以上の人とは身長が175cm以上の人のことを指します。つまり、どの人に聞いても、ある人がその集合に含まれるかどうかは一致するはずです。このように、人によって集合の境界が一致するような要素の集まりのことを集合と呼ぶことができます。

 補足

0.一般に集合は大文字のアルファベットで表し、要素は小文字のアルファベットで表すことが多い。

1.集合を構成する個々のもののことを、「要素」または「元」と呼ぶ。

2.ある集合Xを構成する要素の一つが要素aであるとき、「集合Xは要素aを含む」や「要素aは集合Xに属する」といい、次のように表す。

a \in X

 3.ある集合Xがx_1,x_2,...,x_nのn個要素を持っているとき、次のように表す。

X = \{ x_1,x_2,...,x_n \}

また、ある集合Yについて考える。集合Yが自然数を要素とする集合とすると、次のように表せる。

Y = \{ 1,2,3,... \}

また、次のようにも表せる。

Y = \{x | x \in \mathbb{N} \}

前者のように集合が持つすべての要素を書きだす記法を「外延的記法」という。

また、後者のように、集合が持つすべての要素を書きだすのではなく、「|」の前に集合が持つ要素を示し、「|」の後ろにその要素が満たすべき条件を示すことで集合の持つ要素を示す記法を「内包的記法」という。

また、集合Yの前者の外延的記法の例や集合Xについての外延的記法の書き方では1,2,3の後にどの数字が来るのかは明確には示されていないが、普通に考えればこの後に4,5,6,...と続くと考えられる。このように、外延的記法では、要素の数が多い場合や無限の場合は"..."を用いて、省略する場合があるが、読み手側は文脈などから"..."の省略部分を正しく読み取る必要がある。また、書き手側も読み手側が省略部分である"..."が何を省略しているのかが分かるように注意する必要がある。

4.集合Aが1,2,3の要素をもち、集合Bは自然数を要素にもつとする。このとき、集合Aは次のように表す。

Y = \{ 1,2,3 \}

集合Aの要素の個数は3個である。このようにある集合の要素の個数が有限の数であるとき、その集合を「有限集合」とよび、絶対値の記号"|"で有限集合を表す文字を挟むことで、その有限集合の要素の個数を表すことができる。集合の要素数のことを集合の「濃度」ともいう。例えば次のように表せる。

|A| = 3

また、集合Bは無限個の要素を持つ。このように、無限個の要素をもつ集合のことを「無限集合」という。無限集合の要素の数を集合の「濃度」と呼ぶ。

（続きはいずれ書きます…）

はてなブログでLaTeXを導入するまで

HatenaBlogについて

はじめに

今回が初めての記事なんですが、これからはてなブログで記事を書く際に数式を書きたくなることもあるだろうと思い、LaTeXをはてなブログで導入しようと思いました。色々な人が導入方法を書いてくれいていますが、一応自分も書いておこうと思います。自分はLaTeXなんて使ったことがなく、これが初めてです。

LaTeXとは

TeXという、フリーの組版ソフトが機能強化されたものがLaTeXだそうです。組版（くみはん）とは、活版印刷の用語で活字を組み合わせて、印刷用の版を作ることがもともとの意味らしい。今では、組版と言えば、レイアウトに従って紙や画面に文字・写真・図などを配置することを言う。

導入

1.MathJaxをはてなブログで使えるようにする。

MathJaxはJavaScriptを利用してLaTeXで記述された数式をウェブブラウザ上で表示できるようにするものらしい。

MathJax | Beautiful math in all browsers.

下にスクロールしていくと、Documentaionという項目があるので、その中からGetting Startedを探してLearn moreをクリックする。すると

If you write your own HTML (directly or via a template/theme engine), you can include MathJax by adding this snippet to your page:

 と書かれた下にHTMLが書かれていると思うのでそれをコピーする。

<script src='https://cdnjs.cloudflare.com/ajax/libs/mathjax/2.7.5/MathJax.js?config=TeX-MML-AM_CHTML' async></script>

 現在では(2019/02/26)上記のように書かれていた。

自分のはてなブログの管理ページからデザイン>カスタマイズ>ヘッダーに移動する。

タイトル下と書かれたところに、先ほどコピーしたHTMLを貼り付ければ、導入完了です。

2.記事で実際に使ってみる。

1の手順が完了していれば、後は簡単に書けるはずです。

決まりがあるようでLaTeXを書きたいときには

[tex:LaTeXで書きたい文字列]

と書かなければいけません。"LaTeXで書きたい文字列"と書かれたところを自分で書きかえてください。

例

[tex:E=mc^2]

E=mc^2

ぜひ皆さんもLaTeXつかって記事を書いてください。LaTeXの文法などは各自自分で調べながら書いてください。

おまけ

[tex:E=mc^2]

のようにコードを記事に書きたいのに

E=mc^2

と数式に変換されてしまって困っている人のために、コードを記事に載せたいときの方法を書いておきます。

編集(見たまま)でコードをかいたあと、HTML編集で

<pre><code>コード</code></pre>

とコードを囲むことで変換されなくなります。