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

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

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

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

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

多くの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 (ABC) に参加するという感じで盛り上がっていました。 私はコ…

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

先週の記事の続きです。 最大公約数をもっと高速に求める（その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…

先週の記事の続きです。 最大公約数をもっと高速に求める（その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 …

先週の記事の続きです。 最大公約数をもっと高速に求める（その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…

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

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

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

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

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

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

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

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