Knuth

子どもが百均で買ってきたパズルをやってみたら、全然うまく出来なくて悔しかったのでプログラムで解を探すことにした。 Pentominoとは 探索アルゴリズムと実装 計算量概算 効率的な探索の方針 backtracking Bitboardによる検索と判定 候補の事前計算 実装と実行結果 反転・回転での重複の除外 高速化 短辺から埋める X を最初に配置する Bitboardの反転/回転 Delta Swap による手法 巨大テーブルによるループ効率化 もう一方のループ効率化 孤立点検出による枝刈り その他の実装・手法 WebAssembly化してWebAppで使う 参考 まとめ Pentomin…

｜文字列処理のアルゴリズム ｜配列（テーブル）と添え字（ポインタ） ｜文字列探索処理のアルゴリズム ｜部分文字列の置換処理 ｜文字列圧縮処理 Kindle Unlimitedにサインアップして無料体験に登録する Amazon.co.jp: Amazon Prime Amazon.co.jp: Audibleブック・オリジナル Amazon.co.jp: Amazon Music Unlimited 令和05年 イメージ＆クレバー方式でよくわかる 栢木先生の基本情報技術者教室 情報処理技術者試験 作者:栢木 厚 技術評論社 Amazon ｜文字列処理のアルゴリズム 文字列処理アルゴリズムは、テキ…

Clang が $\sum_{i=0}^n i$ を $n(n+1)/2$ にしてくれることは有名です*1。 また、$\sum_{i=0}^n i^2$ も $n(n+1)(2n+1)/6$ にしてくれます。 その過程では、 unsigned v1 = n * (n - 1) * (n - 2) / 2 * 1431655766u; unsigned v2 = n * (n - 1) / 2; return 3 * v2 + v1 + n; のような計算をしていました。ここで、$1431655766 = (2^{32}+2)/3$ であり、 $$ x\equiv 0\pmod{3} \impl…

2023年4月から基本情報技術者の試験制度が変更されたものの科目B（旧：午後問題）の重要さは変わりません。 出題方式は「多肢選択式」で以前と同じですが、データ構造及びアルゴリズムが8割、情報セキュリティが2割の割合で出題される点が大きく変わっています。 合格基準点は600点以上/1000点満点中、つまり6割以上取れれば合格になります。 そんな科目Bのデータ構造及びアルゴリズムについて、基本となる探索の問題について考えてみましょう。 目次 文字列探索アルゴリズムとは？？ KMP法とは？？ どんなときに使う？ KMP法の実装例（プログラム） 最後に.... 文字列探索アルゴリズムとは？？ 文字列探…

Pythonでのクヌース・モリス・プラット法の実装クヌース・モリス・プラット法 (Knuth-Morris-Pratt algorithm) は、部分文字列検索において、与えられた文字列の中に特定のパターンが現れるかどうかを効率的に調べるアルゴリズムです。このアルゴリズムは、O(n + m) の時間計算量を持ち、n は検索対象の文字列の長さ、m は検索するパターンの長さです。ここでは、Pythonを用いてクヌース・モリス・プラット法を実装する方法について説明します。 クヌース・モリス・プラット法とは まず、クヌース・モリス・プラット法の概要を説明します。このアルゴリズムは、検索するパターンのプ…

2023/05/04初版公開 atcoderやってます。緑です。python使ってます。アルゴリズムの紹介・解説は書きません。これから実装しようとしている人向けに感想・役に立つかもしれない情報を記します。まず、これらのアルゴリズムを実装するのは大変でした。解説をみればやってることはなんとなくわかりますが、実装するとなると難易度が上がりました。 seg木を実装した時の5倍の時間 × 3(種類のアルゴリズム) がかかりました。初歩的なアルゴリズムなのに実装できない!ってなってる人はこの記事を見て安心してください。実装したアルゴリズムが正しく動くかどうかは AOJ-ALDS-14-Bで確認できます。…

今年の三が日は shukutoiya と『$\TeX$ ブック』のゼミをしていましたが、得られた結論は「この本はまったく説明になっていない」でした。 はっきりいって、Knuthは、コンピュータ・サイエンティストとしてはセンス・ゼロ、要するに馬鹿である。それは、あのTeXという処理系を見ればわかる。いったい、世の中に、毎日TeXで泣かされ続けている人は何人いるのだろうか。あんなふざけた処理系で、これほど多くの人に使われているものは他にはない。あんなもの、学生が演習で作ってきたら、不可になるに決っている。とにかく機能だけを追及した処理系である。使い難い処理系がどれほど世の中の人的なリソースを無駄に…

satob.hatenablog.com 同じ分野で国ごとの記載を比較すれば、分野ごとの違いを無視して国ごとの違いが分かるのでは？*1と考えて、UEFA所属の55カ国（＋地域）について、トップリーグの選手名の表示を調べてみたところ、以下のような結果になった。 FIFA各国の選手名簿の姓の大文字小文字 - Google スプレッドシート フランス・チェコ・オーストリア・アイルランドなど10カ国が姓をすべて大文字、名を先頭文字のみ大文字で表記（日本の公文書表記と同じ） イタリア・オランダ・ギリシャなど16カ国が姓・名ともすべて大文字で表記 ドイツ・ノルウェー・スペインなど26カ国が姓・名とも先頭文…

はじめに ダイクストラの「構造化プログラミング」について歴史を年表としてまとめてみた。 技術革新は基礎研究の積み重ねによるものだ。このことをもっと理解してもらいたいという考えが、この年表をつくった私の動機である。(初版2023/02/02) 注意事項として、 年表の正確さは保証できない 年表に関する質問は一切受け付けない 事実を裏付ける当事者のヒアリング調査はやっていない 内容が後日修正されることがある 引用は自由、ただし、それで発生する問題について責任は持たない 年表 (1957年～1978年) 1957年、ジャクソンが「待ち行列ネットワーク（待ち行列*1網、queueing network…

どうもお久しぶりです！ 諸事情により全然ブログが更新できず、ぐぬぬって感じです。 まぁあと2,3年はこんな感じが続きそうですが、すきを見て書ければと思います。 で、今回はChromebookに論文執筆環境を設定するお話です。 今時Overleafもあるので普通にブラウザだけあればなんとかなるのでは？ という声も聞こえてきそうですが、 やはりVScodeが使えると何かと便利だったりするのでね。 あと、最近はノートPCを持ち歩いて開発したりすることもあんまりなかったので 今までのノートPC＝macbook pro生活からChromebookに乗り換えてみようとも思いまして。 なお、今回の虎の巻は以…