忙しく感じる

なんか最近忙しくないはずなのに、忙しいような気がしています。 たぶん原因は、塊として認識できない、こまごましたやらないといけないことが多いことのような気がします。 あとは、それをやることのできる時間が限られている(持ち時間が少ないという意味…

cat a.out を防ぐ

今日は七夕だったようですが、あいにくの雨でした。 出力ファイルを全部つなごうとcat *.outと打ったところ、a.outも巻き込まれてコンソールが大変なことになりました。 このミスは二回目なので、対策することにしました。 あまりうまい方法が思いつきません…

異世界とか

ちょっと違う世界に行っていました。 そこの住人は親切で、 いや、不親切な対応もあったような気がしますが、トータルでは親切だったなぁという印象でした。 それ以外はあんまり印象に残っていないってことは、そんなに違わなかったってことなのでしょう。

テンプレートメタプログラミングでQuineを書いた

最近テンプレートメタプログラミング (Template meta programming, TMP) から離れているなぁと思ったので、また書いてみました。 Quine(クワイン)とは、自分のソースコードを出力するプログラムのことです。 ソースコードは以下に公開してあります。C++11…

gcc9.1.0をソースコードからコンパイルした

gcc8以前と比較して、gcc9はバイナリ生成部分が更新されているようです。 既存のコンパイラのバイナリ生成に不満を持ったため、gcc9.1.0をビルドすることにしました。 前回gcc8.2.0をソースコードからコンパイルしました。 その時の知見が生かせたので、今回…

干し柿落としゲームのGrundy数を求めてみた

干し柿落しゲームは、takaken氏の作成した対戦ゲームで、石取りゲーム(Nim)を拡張したものです。 遊んだことがなければ、この記事を読む前に遊ぶことをおすすめします。ぜひ、自分で必勝戦略を構築してみてください。 干し柿落としゲームはNimより複雑であり…

AtCoderを退会するための問題(ABC077/ARC084のD問題)を別解法で解いた

AtCoderを退会するための問題、の元ネタは以下のツイートです。 本当に退会しますか?※botではないことの確認のため、以下の問題を解き、ソースコードを提出してください。問題文K の正の倍数の 10 進法での各桁の和としてありうる最小の値を求めてください…

二重かっこの高さを中身に合わせるtexマクロを解読する

のような二重角かっこは、\[\!\[3\]\!\]と入力すれば出すことができます。 nath.styを導入すると、\double[とか\lBrackなどと書けるようです。 しかし、このままでは中身に高さのあるもの(分数など)を入れた場合に見栄えが良くありません。 中身に応じた高…

128bit除算のやり方

五月祭お疲れさまでした。私はクイックソートのメモリアクセス系列の可視化の展示をしていましたが、楽しんでいただけたでしょうか……。 C言語には多倍長整数のような便利なものがありません。unsigned long longを使えば64bit整数までは取り扱えますが、それ…

C言語における移植性のある算術シフトの記述方法

多くのCPUには、算術シフト演算命令が含まれています。そのため、多くのコンパイラは、符号付き整数に対する右シフトを算術シフトにコンパイルします。 しかし、C言語において、符号付き整数を右シフトした場合の挙動は処理系定義です。処理系定義というのは…

テンプレートクラスを継承したクラステンプレートを作るときの罠

何回も言われていることだけれど、つまづくことが多いところなのでメモしておきます。 以下のようなコードで、コンパイルエラーになるときの対処法です。 template<class U> class Base { public: int f() { return 1; } }; template<class T> class Derived : Base<T> { int g() </t></class></class>…

循環的な構造の中で大小関係を推定する

3時より8時の方が後にあり、8時より11時の方が後にありますが、11時より3時の方が後にありそうです。 時計のように巡回している場合、局所的には大小関係のようなものがありそうでも、推移律が成り立つような大小関係はうまく定義できません。 その巡回周期…

最近使った固定要素数を保持する配列の作り方

よく使うデータへのアクセスを高速化するために、そういったデータを高速な記憶媒体に保持しておくことを、キャッシュすると言ったりします。 高速な記憶媒体はそれ相応に高い*1ので、大容量と両立することはできません。 そこで、よく使うデータを選別して…

累積和を使っても二分探索を使っても解ける問題

先週話題にした、ABC(AtCoder Beginner Contest)122のC問題は、累積和を用いて解くのが想定解のようですが、二分探索を用いても解けるという話を、少し一般化して考えてみます。 なお、以下では何も言わずに空間計算量だけ書いた場合、時間計算量も同じオー…

AtCoder Beginner Contest 122に参加した記録

忘れないうちに書いておきましょう、と思って既に二週間が経過しました……。 この日はちょうど私の所属しているサークルの合宿の日で、サークルのメンバーのうち何人かがAtCoder Beginner Contest (ABC) に参加するという感じで盛り上がっていました。 私はコ…

近況とか今年度の反省とか

今週は無理しすぎて風邪をひいてしまいました。つらい。 来年度からはもっと規則正しい生活をするようにしたいです。 それから、「いつまでにやるか明確に決まっていないけれど、いずれやらないといけないこと」は3月に片づけようと思っていたのに、いろいろ…

最大公約数をもっと高速に求める(その4)

先週の記事の続きです。 最大公約数をもっと高速に求める(その3) - よーる 前回示したコードは、以下のようなものでした。 uint64_t gcd_impl( uint64_t n, uint64_t m ) { constexpr uint64_t K = 5; for( int i = 0; i < 80; ++i ) { uint64_t t = n - m…

最大公約数をもっと高速に求める(その3)

先週の記事の続きです。 最大公約数をもっと高速に求める(その2)【cmova命令は遅い】 - よーる 前回示したコードは、以下のようなものでした。 uint64_t gcd_impl( uint64_t n, uint64_t m ) { for( int i = 0; i < 10; ++i ) { uint64_t t = n - m; bool …

最大公約数をもっと高速に求める(その2)【cmova命令は遅い】

先週の記事の続きです。 最大公約数をもっと高速に求める(その1) - よーる 前回示したコードは、以下のようなものでした。 uint64_t gcd_impl( uint64_t n, uint64_t m ) { for( int i = 0; i < 10; ++i ) { uint64_t t = n - m; bool q = m > t; n = q ? …

最大公約数をもっと高速に求める(その1)

最大公約数を求める非常に有名なアルゴリズムとして、ユークリッドの互除法が知られています。 このアルゴリズムは、二つの入力を十進法で表したとき、小さいほうの桁数の高々五倍の回数の剰余演算で最大公約数が求まることが知られています(ラメの定理)*1…

完全精度 expf 関数の作り方

C言語では、expf関数などの超越関数の精度は一切保証されないことになっています*1。 そうは言っても、数学的な結果に近い結果が返ってくることが、常識的に信じられています。 数学的な結果に最も近いfloatやdoubleが返ってくることを、完全精度(丸め誤差0…

C++におけるinline指定子の誤解

C++にはinline指定子があります。しかし、このinline指定子は、その名前から誤解されがちです。 (誤解)inline指定子を付けると、その関数はインライン展開される これは誤解であり、正しくありません。正しくは、以下のような意味になります。 inline指定子…

いろいろなボードゲームの複雑性クラスとその直感的説明

いろいろなボードゲームの複雑性クラスは語られることはありますが、多くの場合直観的説明がなく、論文を読むしかない状況にありました。調べたことをまとめておきます。 チューリングマシンの機能 決定性チューリングマシン 普通のコンピュータのことだと思…

DAGのトポロジカルソートのうち最適なものを見つけたい

DAG (Directed acyclic graph) のトポロジカルソートは一般にΟ(V!)通りありますが、その中で特定の評価関数を最小にするものを見つけたい、という問題群を考えています。 最適化コンパイラを作るときに出てきた問題やコードゴルフに関連する問題も含まれてい…

「正規表現の積」に関する考察

元問題はこちらです。 i-i.hatenablog.jp 準備 用語の定義 一般的な形式言語の用語 アルファベットΣ は、文字列に含まれてよい文字の集合のことです。元問題では小文字ラテンアルファベット26文字ですが、一般化しておきます。 言語とは、文字列の集合のこと…

『VisualStudioを使っていると「移動したか、名前が変更されたか、またはコンピュータに存在しません。」と出る 』を解決した

タイトルの通りです。 症状は先々週の記事を参照してください。 lpha-z.hatenablog.com 「c1xx C1083」でググったところ、以下のウェブサイトを見つけ、そこに書かれていることをやったところ解決できました。 developercommunity.visualstudio.com 解決法は…

文脈自由言語の階層について

去年もこんな話を書いた気がします。 文脈自由言語の階層についての情報ってネット上ではまとまった形ではあまり手に入らないような気がします。調べたことをまとめておきます。 文脈自由文法と文脈自由言語の違い 文脈自由文法と文脈自由言語という、二つの…

VisualStudioを使っていると「移動したか、名前が変更されたか、またはコンピュータに存在しません。」と出る

タイトルの通りです。 具体的な症状は以下のような感じでした。 エクスプローラーからそのファイルをドラッグアンドドロップでVisualStudioに持ってくると、「(そのファイルのフルパス)は移動したか、名前が変更されたか、またはコンピュータに存在しません…

makeの並列オプションは何を指定するべきか

最近何の縁があってか 鬼斬弐 というオープンソースのプロセッサシミュレータの開発を手伝っています。 github.com ここ数日でRISC-VのRV64Gへの対応が急速に進められ、ベンチマークプログラムも動くものが増えてきたようです。 私はちまちま細かいバグを取…

RISC-Vのシミュレーション環境を構築した

そろそろクリスマスですね。ltmpcを作ってからもう一年たってしまったのかという思いでいっぱいです。 github.com さて、前回作ったRISC-V用のgccですが、残念ながら手元にRISC-Vの命令セットが動くコンピュータがないため、コンパイルしたプログラムを動か…