数独自動ソルバのしくみ

はじめに数独というパズルがあります。まあこんな感じのものです。数独の例（画像はwikipediaより） https://ja.wikipedia.org/wiki/%E3%83%95%E3%82%A1%E3%82%A4%E3%83%AB:Sudoku-by-L2G-20050714.svg これをコンピュータに自動で解かせるにはどうすれば…

2022-10-27

地球上の2点における距離と角度の計算方法

概要とあるプログラムを書くときに必要になったので。設定地球の半径は$R$ 地球上の2点$P_i(i=1,2)$は緯度が$\theta_i$で経度が$\varphi_i$である。このとき、 $$-\pi/2\lt \theta_i\lt \pi/2$$ $$-\pi\lt \varphi_i\lt \pi$$ とする。原点$O$を地球の…

2022-09-04

これ急に見て三角関数やんとはならないやろ

自己満足数学記事

きっかけいつものようにボケーっとしながらツイッター見てたら面白そうなものを見つけた。これ急に見て三角関数やんとはならないやろ【画像】画像の内容は、とある参考書を写したものである。「$x^2+y^2=4$のときの$2x^2+3xy-y^2$の最大値・最小値を求…

2022-08-27

F_q係数多項式をq乗すると…？

はじめに任意の$\mathbb{F}_2$係数多項式$f$において $$f(x^2)=\{f(x)\}^2$$ が成り立つ。これは比較的簡単に示せる。 $$f(x)=a_0+\cdots+a_{n-1}x^{n-1}$$ なら、 $$\{f(x)\}^2=\sum_{i=0}^{n-1}a_i^2x^{2i}+2\sum_{i\lt j} a_ia_jx^{i+j}$$ となるが、$\m…

2022-07-17

二項係数 mod 素数のあまり見かけない計算方法

競技プログラミング

atcoder.jp これを頑張って計算すると以下の式（を998244353で割った余り）を出力すればいいことがわかります。 $$\sum_{M=0}^{N}\binom{N}{M}\cdot \binom{K+M+1}{N+1}$$ この式の導出方法はこの記事の本筋からそれるので省略します。解説参照！さて、制約…

2022-07-09

日本地図を（隣り合う都道府県が違う色になるように）3色で塗り分けることは可能か？

数学関係ない記事

（過去ツイートの再掲です）四色定理により、地図は四色で塗り分けることができることが保証されている。*1では、日本地図は三色で塗り分けることはできるだろうか？補足日本地図を見ると、群馬・栃木・埼玉・茨城あたりの県境が密集していて見にくくなっ…

2022-06-21

n!がpで割り切れる個数

概要 pを素数としたとき、 n!がpで割り切れる個数は $$v_p(n!)=\dfrac{n-S_p(n)}{p-1}$$ である。ここで、$S_p(n)$とは、$n$を$p$進数表記したときの各桁の総和である。証明帰納法でやる。とりあえずルジャンドルの定理は既知とする。知らない場合は高校…

2022-05-24

ブランコからジャンプ

物理

ブランコからジャンプするとき、最も遠くに飛ぶにはどこで手を離せばよいか

2022-04-16

問題文を少し変えるだけで解法が大きく変わる問題（ソートをするために必要なコスト）

競技プログラミング

以下の2つの問題があります。それぞれどう解くでしょうか？問題1 $N$を正の整数とする。$0,\ldots,N-1$を並び替えた順列を$a_0,\ldots,a_{N-1}$とする。このとき、以下の操作を行うことができる操作：$0\leq i\lt N-1$を一つ選んで、$a_i$と$a_{i+1}$をス…

2022-03-18

ラプラシアンの三次元極座標変換

計算過程 $$\dfrac{\partial^2}{\partial x^2}+\dfrac{\partial^2}{\partial y^2}+\dfrac{\partial^2}{\partial z^2}$$ $$x=r\sin{\theta}\cos{\phi}$$ $$y=r\sin{\theta}\sin{\phi}$$ $$z=r\cos{\theta}$$ $(0\leq \theta\leq \pi,0\leq \phi\lt 2\pi,0\leq…