ユユユユユ

webエンジニアです

C++

clang: error: invalid version number in '-mmacosx-version-min=11.1'

C++

homebrew でインストールした gcc@9 が表題のエラーを吐いて失敗する。 g++ だと言っているのに clang とか言ってくるのがいらつく。 使う頻度より壊れているのを直す頻度のほうが高くさえなっていそう。でも真面目に環境を整備するのも面倒なので、直し方だ…

gcc-9 を使うようにした

C++

昨晩の ABC-202 への参加中に、コンパイラが動かないという自体に直面した。先週のコンテストまでは普通に動いていたコンパイルタスクがこういうログを吐いて停止してしまう。 command not found: x86_64-apple-darwin19-gcc-10 コンテスト中は AtCoder のコ…

浮動小数点数のビットレベル表現を print する

C++

浮動小数点数は IEEE-754 という規格で標準化されている。たとえば32ビットで表現するとき、上位1ビットが符号に、次の8ビットが指数部に、残りの下位23ビットは仮数部として割り当てられ、これら3つのフィールドが合同してひとつの浮動小数点数を表現する。…

整数オーバーフローをコントロールすることの難しさ

C++ で競技プログラミングをやっていて、整数オーバーフローに泣かされたことのない者はいないだろう。僕とてそうである。ちょっとしたケアレスミスにすぎないのだが、些細なミスであるからこそ、それを繰り返してしまうとことさら不甲斐なく感じる。 オーバ…

C++ のコンパイル環境を変更した

C++

vscode の devcontainer で debian コンテナを立てて、その上でコンパイルしていた。こうしていたのは単に <bits/stdc++.h> を楽に使いたかったからにすぎない。いろいろカスタマイズを頑張るより先に、手っ取り早くコンパイルできる環境を用意したかったのである。こうして</bits/stdc++.h>…

gcc のインクルードパスを確認する

C++ のライブラリをローカルの開発環境でインクルードできるようにしたい。また #include <aws/dynamodb> のように、相対パスではなく <> でインクルードしたい。 正しいインクルードパスにヘッダファイルを配置してあげればいいはずだが、そのインクルードパスを忘れてし</aws/dynamodb>…

合同式におけるモジュラ逆数 (mod_inv) の求め方

C++

合同不定式 を について解く。 という不定方程式であれば、両辺に の逆数 をかけて としてあげればよい。 同じように合同式 においても両辺に の逆数をかければ が求められる。ただしこの文脈では、単に「 の逆数」と言うよりも「 を法とする の逆数」と呼ぶ…

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

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

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

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

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

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

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

C++

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

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

C++

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 としてしまってい…