アルゴリズムと数学

アルゴリズムと数学079 - ModSum 解法 上界を見積もる． 各\(i \in [1,N]\)に対して， \(i\)で割ったあまりは \(i-1\)以下． よって，答えは \(\sum_{i \in [1,N]} (i-1)\) 以下． 実際に，これを実現する例が存在する． 1-indexed で \(p_{i} = i+1\) とおけばよい． ただし\(p_{N} = 1\)とする． 使っている記号，マクロ等 "https://ecsmtlir.hatenablog.com/entry/2022/12/23/131925" int main() { ll n; cin >> n; ll…

アルゴリズムと数学089 - Log Inequality 2 解法 式を同値変形すると， \(a < c^{b}\). 桁あふれに注意して冪を計算する． \(a\)より大きいかだけが問題になるので， \(a\)の最大値よりも大きい値は区別する必要がないので， 気持ちとしては \(\infty\) の様にまとめてしまう． 実装では，\(\infty\)の代わりに定数で扱う． 実装 \(c\)の冪を計算するが， \(pow*c \leq inf\) としてしまうと， \(pow\)と\(c\)が \(10^{18}\)に近い場合等に桁あふれが起きる． 代わりに，同値な式 \(pow \leq \…

アルゴリズムと数学094 - Maximal Value 解法 \(a_{i}\)の和の最大を求める． まず，各\(i \in N\) に対して \(a_{i}\) の最大を見積もる． \(b_{i} \geq max(a_{i}, a_{i+1}) \geq a_{i}\) かつ \(b_{i-1} \geq max(a_{i-1}, a_{i}) \geq a_{i}\) であるから， \(min(b_{i}, b_{i-1}) \geq a_{i}\). ただし，\(b_{-1} = b_{n-1} = \infty\)とする． 逆に，各 \(i \in N\) に対して \(a_{i}…

アルゴリズムと数学057 - Domino Tiling 解法: 行列冪乗 これも遷移が線形になるので，行列冪で解ける． 状態を \(2^{K}\) で持っておき， 次数\(2^{K}\)の行列を考える． まず\(N\)が小さい場合で考えてみる． DP による全探索をすると， 左から \(i\) 列目を決めるときは， \(i-1\) 列目の配置によってのみ影響を受ける． 実際，\(i-1\) 列目を敷き詰めるとき， \(i\) 列目においてどの場所にはみ出したかで， \(i\) 列目の敷き詰め方が決まる． (\(k \in K\) 列目においてはみ出しているか) \(\in 2\) と考えれば…

アルゴリズムと数学062 - Teleporter 解法0: 周期性を用いる \(i \rightarrow a[i]\) と遷移を繰り返すと，あるところでサイクルに入る． \(i_{0}\)からスタートするとして， \[ i_{0} \rightarrow \cdots a \rightarrow b \rightarrow \cdots \rightarrow c \rightarrow a \rightarrow \cdots \] の形となる． サイクルの部分の長さを調べれば，そのサイクル部分を減らせるので， 最悪で\(O(N)\)のシュミレーションで解ける． 解法1: ダブリング こ…

こんにちは。ふかふかです。CTRLアドベントカレンダー2024 12/19ということで、バイトで小中学生にプログラミングを教えて感じた事を書いていこうと思います。せっかくなのでなるべくキャッチーなタイトルにしてみました。 前の人はマキアさんです。 mak1a.hatenadiary.com adventar.org 記事の内容 教えてわかった世間の偏見とは異なる興味深い傾向を紹介する。プログラミングが不得意な人間にどうやってプログラミングを教えるかを考える。 今しているバイト ロボット制作・プログラミング教室卒業まで続けるつもりなので、あと3か月くらい勤務する予定です。三年程度続けたことになり…

ABC374Gの公式解説を自分なりに解釈したものです。憶測が含まれているので、注意してください。公式解説の方が分かりやすい人もいると思うので、先にこちらをどうぞ。公式解説：Editorial - KEYENCE Programming Contest 2024（AtCoder Beginner Contest 374） 必要な知識（解説を省略します） ・強連結成分分解 ・最大流 ・二部グラフの最大マッチング 強連結成分分解：強連結成分分解の意味とアルゴリズム | 高校数学の美しい物語ACLのSCCのドキュメント (C++)：https://atcoder.github.io/ac-librar…

前回、神について聞いてみたのでもう少し情報を集めてみた。（少し慣れてきた模様） 自分今回は神について考えたいと思います。 Copilotそれは興味深いテーマですね！「神」について考えると、宗教や文化によってさまざまな解釈があります。例えば、日本の神道では、自然や祖先を神として崇拝することが多いです。神道の神々は、山や川、木々など自然の中に宿るとされ、日常生活の中で身近に感じられる存在です 。 一方、キリスト教やイスラム教などの一神教では、神は宇宙と人類を創造し、全知全能の存在とされています 。これらの宗教では、神は唯一であり、絶対的な存在として信仰されています。あなたはどのような神について考え…

前回、AIとは何かを簡単に説明しました。じゃあ、次は使ってみよーう！ と言うことでAIを使うのに、また副業として使うために、何をしたら良いのか？という話をしましょう。まずは1. 目標を設定する 何を達成したいかを明確にします。 何故それが必要なのかと言うと、この目標が定まっていないと何をしたら良いのか解らないとなりやすいためです。なので、例えば、データ分析をしたい、チャットボットを作りたいなど。やりたい事をハッキリとさせておくのが良いです。2. 必要なツールを準備する 先ほどの例えでだしたデータ分析やチャットボットなどを作りたいとなれば、AIだけでは足りません。ですからPython（プログラミ…

今日も今日とてこゃーそということで先日こちらの記事を書かせていただきました。 amentorimaru.hatenablog.com こちらの記事では競技プログラミングをしている方々向けにVRChatの紹介とVRC競プロ部の紹介を行いました。 そしてさらに昨日こっそりタイトルに追記を行いました。競プロer向け。と というわけで、今度はVRChatter向けに対称的な記事を書いていこうかなと思います。

tomboです。マージソートを、書きます。（書くので） 安定して速いです マージソートは安定ソートで、ソートしたいデータ数 に対して最悪ケースの時間計算量が です。例えばクイックソートは不安定ソートで、ピボットの選び方によってはマージソートより遅く なったりします。色々な言語のソート関数でも、内部でマージソートが実装されているんじゃないかなーと思っています。（思っているだけ） 実装の方針 分割統治法をします。「困難は分割せよ」の精神で (DP的な) 、分割してソートしながらマージしていって、最終的に全体のソートを達成します。分割は二分木のようにします。今回は再帰関数を使います。(他の実装をしら…

ゲーム開発で学ぶC言語入門 プロのクリエイターが教える基本文法と開発技法 人気ジャンルのゲーム開発を通して、C言語の基本文法・開発技法が学べる「ゲーム開発で学ぶC言語入門 プロのクリエイターが教える基本文法と開発技法」 160以上のサンプルを無償提供！ 動作を確認しながら学べる「ゲーム開発で学ぶC言語入門 プロのクリエイターが教える基本文法と開発技法」 「ゲーム開発で学ぶC言語入門 プロのクリエイターが教える基本文法と開発技法」紙面イメージ 「ゲーム開発で学ぶC言語入門 プロのクリエイターが教える基本文法と開発技法」対象読者 「ゲーム開発で学ぶC言語入門 プロのクリエイターが教える基本文法と開…

ウイルス学者さん、うちの国ヤバいので来てください。 古瀬 祐気中央公論新社 ウイルス学者さん、うちの国ヤバいので来てください。 (中公新書ラクレ 808)作者:古瀬 祐気中央公論新社Amazon 地元の医者は逃げ、インフラは停まり、遺体が道に転がる中、僕はアフリカに派遣された――。引継ぎゼロ、報酬１ドルもなんのその！ ウイルスでパニックになった世界を救う感染症専門家のドキドキ・アウトブレイク奮闘記。 詳細を読む 読書メーターブクログ チェコのヤポンカ 木村 有子かもがわ出版 チェコのヤポンカ作者:木村 有子かもがわ出版Amazon 豊かな森で友だちと遊んで過ごした日々と、帰国して待ち受けていた…

AtCoderからアルゴリズムを勉強するようになりました。アルゴリズムの勉強から数学が気になり、数学から数学の歴史が気になりました。数学史について調べていたら、世界史の勉強になっていました。 私は、学生時代に歴史が苦手でした。数学史からのアプローチで世界史を勉強できることに学生時代に気付きたかったです。 アルゴリズムから数学、数学から世界史 数学史から世界史へのアプローチ 算数の文章問題 副産物 数学ブームを期待する アルゴリズムから数学、数学から世界史 私は、数学はわりと好きです。問題を解くのは楽しいです。しかし、文章問題には親近感が湧きません。文章問題にあるような状況に遭遇したことがないの…

ベスト3 雑評 読んだ本リスト 今年読んだ本は37本 ベスト3 1. ワセダ三畳青春期 高野さんといえば奇異な体験をするルポルタージュの印象だが、この本はそうではなく、高野さん版トキワ荘物語。といった感じ。 青春期でしか味わえない生活がそこにあって、笑いながらほっこりできる。また、最後は確実に青春期の終わりを告げていてちょっぴり切ないような寂しいような気持ちになる。 「まんが道」のように、これからも時折読み返したくなる作品。2. ピョンヤンの夏休み 柳美里が実際にピョンヤンを複数回に渡って訪れた時のエピソードをまとめた本。 柳美里さんの作品はどれも、いかにただ生きていくということがハードゲーム…

https://atcoder.jp/contests/typical90/tasks/typical90_oこれは、アルゴリズムと数学 101と同じ問題です。