ユユユユユ

webエンジニアです

C++

背伸びして『Effective C++ 第3版』を読んだ

ある Googler の投稿を読んでいて、見かけた本である。題字のフォント、表紙のデザインなど、飾り気はないのに力強いオーラを持つ装丁がただちに印象に残った。名著という評判も高いおかげで安心して読むことができたし、翻訳も丁寧な印象で、自然に読める心…

『江添亮のC++入門』でC++の基本を学び直す

競技プログラミングに触れるようになって、自己流ながら少しずつC++が使えるようになってきた。しかしきちんとした参考書を読んだことがなく、体系立てた学習もしたことがないのが気にかかっていた。学習といえば、AOJの教育コンテンツを少しやったばかりで…

C++の整数リテラルに桁区切りを加える

Ruby であればこういう書きかたが許されている。ゼロを列挙するよりもはるかに視認性が高く、お気に入りの記法である。 a = 1_000_000_000 a # => 1000000000 C++ を書くとき、ここにほのかなもどかしさを感じることはあった。1000000000と書くのは読みづら…

任意の累乗数をみちびくアルゴリズム

例えば Ruby はユーザーが特に意識せずとも無限に大きな整数値を扱うことができる。 jnsato.hateblo.jp C++では long long 型を利用してもたかだか 64-bit までしか扱うことができない。ビルトイン型として提供されているのはこれが最大となるから、それより…

循環小数を検出して表記する

1/3 や 1/7 のような循環小数を数値型を使って表現しようとすると、普通は有効桁数の範囲でしか表記できない。そうではなく、次のように循環小数であることが一目瞭然となってほしい。 1 / 3 = 0.(3) 1 / 7 = 0.(142857) そこで単純に、分子と分母を引数に受…

std::map と std::unordered_map

map というデータ構造は連想配列にあたるものと単純に理解していた。unordered_map について追って知ることとなり、初めて map のキーが自動的にソートされることを知る。 #include <map> #include <unordered_map> int main() { std::map<int, int> mymap1; std::unordered_map<int, int> mymap2; in</int,></int,></unordered_map></map>…

配列の先頭と末尾を管理できる deque 型

AtCoderの過去問より、この問題を解いていた。 atcoder.jp やりたいこと 任意の数列を、空の配列の先頭と末尾に交互に追加していきたい。Ruby であれば、これは Array#unshift と Array#push を使って簡単に書ける。例えばこう。 n = 10 ans = [] 1.upto(n) …

最大公約数を利用して最小公倍数を求める

「最大公約数」と問われると「ユークリッドの互除法!」とただちに着想が湧くようにはなってきた。 その一方で「最小公倍数」と問われたら、「おや...」と思いながら調べ直さざるをえない自分がいた。 この記事できちんと整理して、記憶に定着させたい。 定…

2^n 通りのbit全探索を m^n 通りの深さ優先探索に一般化する

以前の記事で bit 全探索を利用して冪集合を作った。 jnsato.hateblo.jp これは任意の有限集合の各要素について、部分集合に含めるか含めないかを表すフラグの組み合わせを総当たりする方法であった。各要素が 0 or 1 の二元のいずれかに振り分けられるため…

任意の集合のすべての部分集合を列挙する

任意の集合について、すべての部分集合を列挙したい。これはつまり、ある集合から冪集合を作りたい、と言い換えられる。 たとえば 3 つの要素からなる集合 X = {1, 2, 3} に対してP(X) = {{}, {1}, {2}, {3}, {1,2}, {1,3}, {2,3}, {1,2,3} }であるような写…

深さ優先探索と std::next_permutation でそれぞれ n! 通りの順列を生成する

長さ n の順列 [1, 2, ..., n] を並べ替えて n! 個の順列を作りたい。 2<=n<=8 程度として、二通りのやり方を試してみた。 深さ優先探索 与えられた順列を末尾の要素から再帰的に swap して前通りの組み合わせを試す。ループごとに添字が 1 ずつ増えていくの…

ループイテレータの型を思考停止で int 型にしてはならない

y = f(x) = x^5 となるような写像 f を作ろうとして次のようなコードを書いてハマった。 unsigned long long N[1000]; for (int i = 0; i < 1000; i++) { N[i] = i*i*i*i*i; } Nは unsigned long long と定義しているが、 i^5 の i を int としてしまってい…