Lilliput Steps

小さな一歩から着実に. 数学やプログラミングのことを書きます.

数学

ネイピア数の定義の数列の有界性と単調性の検証

問題 数列$$a_n = \left(1 + \dfrac{1}{n}\right)^n \hspace{1.0cm} (n \in \mathbb{Z}^{+}) $$を考える。① $a_n$ は単調に増加することを示せ。すなわち,$$a_n を示せ。② $a_n$ は上に有界であることを示せ。

積分記号の下での微分で遊ぶ

名古屋大学での演習問題 の 8 番を解いていたらすごく悩んだので解法をメモすることにします.

よく見る微分方程式とその解法

はじめに こんにちは, kagamiz です.最近は編入試験に向けて勉強しています. 編入試験の数学では, よく微分方程式が出題されます.出題されるものは簡単なものから, 見たことがないと厳しい物まで多岐に渡ってあります. その中で出会った微分方程式の解法を, …

Gamma 関数の相反公式

問題 Gamma 関数の相反公式$$\Gamma(z)\Gamma(1-z) = \dfrac{\pi}{\sin(\pi z)} (z \in \mathbb{C}, 0 を示せ.ここで, $\Gamma(z) = \displaystyle\int_{0}^{\infty} t^{z-1}e^{-t}\,dt$ です.たとえば, この公式を認めると$$ \left\{\Gamma\left(\dfrac{1}{…

最近の 45 度回転事情

こんばんは, kagamiz です! ちょうど 1 歳老けたところです :).この記事は Competitive Programming Advent Calendar 2014 の 21 日目の記事として書かれました.この記事では, 最近ぼくが見た範囲で出題された 45 度回転の問題を紹介していこうと思います.ち…

Codeforces 235B - Let's Play Osu!

問題文 : Let's Play Osu!概要$n$ 個のマスがある. マス $i$ は確率 $p_i$ で "○" になり, 確率 $1 - p_i$ で"×"になる. $n$ 個のマスのうち, "○"で繋がったそれぞれの連結成分の大きさを$S_i$ とすると, スコア $\displaystyle\sum_{i = 1}^{連結成分数}S_i…

正単体の超体積

問題$\mathbb{R}^n$ にあって互いの距離がすべて $1$ であるような $n+1$ 個の点のなす図形を$n$ 次元の 1 辺の長さが $1$ の正単体という. 正単体の超体積を $n$ の式で表わせ.

回転体の表面積

問題曲線 $x = f(t),\ y = g(t) \ (g(t) \geq 0)$ $(\alpha \leqq t \leqq \beta)$ をx 軸の周りに回転して得られる図形の表面積を求めよ.

楕円積分

問題 楕円 $\dfrac{x^2}{a^2} + \dfrac{y^2}{b^2} = 1$ の弧長を求めよ. ただし $a > b$ とする.

Vieta の公式

問題 :Vieta の公式$$\dfrac{2}{\pi} = \sqrt{\dfrac{1}{2}} \cdot \sqrt{\dfrac{1}{2} + \dfrac{1}{2}\sqrt{\dfrac{1}{2}}} \cdot \sqrt{\dfrac{1}{2} + \dfrac{1}{2}\sqrt{\dfrac{1}{2} + \dfrac{1}{2}\sqrt{\dfrac{1}{2}}}} \cdot \cdots$$を証明せよ.

二階微分のラプラス変換

問題 : $\mathcal{L}\left[\dfrac{d^2}{dt^2}f(t)\right]$ を求めよ.

$\sin (\omega t)$ のラプラス変換

神から $\mathcal{L}[\sin (\omega t)]$ を求めるように言われたので, 神が仰っていた方法で求めます.

sin の積の変形

$n$ が$2$ 以上の整数のとき,$$ \displaystyle \prod_{k=1}^{n-1} \sin \dfrac{k\pi}{n} = \dfrac{n}{2^{n-1}}$$となることを示せ.この問題の証明をしている方がいて, 解答をすぐに追えなかったので反省を込めて自分でも証明を書きます.

Cauchy-Riemann の微分方程式の極座標表示

(1) $z=re^{i\theta}=r(\cos\theta+i\sin\theta)$としたとき, Cauchy-Riemann の微分方程式は, 実部を$u(r,\ \theta)$, 虚部を$v(r, \theta)$ とすると $\dfrac{\partial u}{\partial r} = \dfrac{1}{r}\dfrac{\partial v}{\partial \theta},\ \dfrac{\parti…

ARC 004D - 表現の自由

問題文 : 表現の自由

ARC 016 C - ソーシャルゲーム

問題文 : ソーシャルゲーム

Codeforces 359D - Pair of Numbers

問題文Pair of Numbers概要長さ$n$ の列が与えられる. 次の性質を満たす最長の部分列をすべて求めよ. $a_l,\ a_{l+1},\ \cdots,\ a_r$ を全て割り切る$a_j\ (l \leqq j \leqq r)$ が存在する. $1 \leqq n \leqq 3 \times 10^5,\ 1 \leqq a_i \leqq 10^6$

Codeforces 359C - Prime Number

問題文Prime Number概要$x$ を素数とする.$\dfrac{1}{x^{a_1}} + \dfrac{1}{x^{a_2}} + \cdots + \dfrac{1}{x^{a_n}}$ を$\dfrac{s}{t}$ とするとき(ここで$t=x^{a_1 + a_2 + \cdots + a_n}$), $\text{gcd}(s, t)$ mod $10^9+7$ を求めよ.$1 \leqq n \leqq 1…

連続する正整数の和について

"連続する正整数の和" に関する問題を2 題考えたのでそれについて.

AOJ 2372 - IkaNumber

問題文 : IkaNumber

AOJ 1056 - Ben Toh

問題 : Ben Toh

Codeforces 356B - Xenia and Hamming

問題 : Xenia and Hamming概要 :文字列$x$ を$n$ 回繰り返した文字列$a$ と, 文字列$y$ を$m $ 回繰り返した文字列$b$ がある. $a$ と$b$ のハミング距離を求めよ. ただし, ハミング距離とは$\displaystyle \sum_{i=1}^{n} [a_i \neq b_i]$ で定義され, $a_i…

IOI 2008 Day2 - Linear Garden

問題文 : 直線状の庭園 (pdf 注意)

Codeforces 336D - Vasily the Bear and Beautiful Strings

問題文 : Vasily the Bear and Beautiful Strings問題概要 :つぎの性質を満たす文字列$s$ の総数をmod $10^9+7$ で求めよ.・$0$ が$n$ 個, $1$ が$m $ 個から成る文字列である. ・$s$ にmodification を0 回以上行うことで最終的に文字列$s$ が文字$g$ にな…

AOJ 2142 - Bitwise Kingdom

問題文 : Bitwise Kingdom解法 : $n$ bit 中$k$ bit が$1$ の市民の人数は$_{n}\text{C}_{k}$ 人である. よって, $_{n}\text{C}_{k} \geqq m$ となるまで$m$ を減らす. あとは, 先頭に$1$ を入れたときに自分より速い組み合わせが幾つあるかをたどりながら$0…

(Old) NPCA #33 : 濁流

問題文 : 濁流きつねの曲大好きな身としては, 解かなければと思い意を決して取り組みました. concon 好きです.解法 : 算数, しよう.(提案) 明らかに(x, y) と(y, x) を押す順番は一緒なので, x > y なら折り返してしまいましょう. その後, マスの斜め上半分…

JOI 春合宿 2008-day4 Ruins

問題文 : 最古の遺跡2解法 :dp[i][j] : 辺ij を最後に使った時の頂点数の最大値, とする. このとき, 以下のような図を考える.ここで, 現在赤の辺から水色の辺に遷移しようと考えていたとすると, 赤の辺と水色の辺のなす角θが180 度以下であれば, dp[水色の辺…

RUPC Day2 I - One

問題文 : One解法 :放物線の長さは, で求まる. (ここで, とおいた.)交点を列挙してこの関数を適用していけば良い. 誤差に気をつけて計算すべし...コード : #include <cstdio> #include <cstring> #include <cmath> #include <vector> #include <algorithm> using namespace std; const long double EPS =</algorithm></vector></cmath></cstring></cstdio>…

Codeforces 258D - Little Elephants and Broken Sorting

問題文 : Little Elephants and Broken Sorting解法 :dp[i][j] : 場所i, j の数をA[i], A[j] として, A[i] > A[j] となる確率, とすると,この配列の初期値はA[i] > A[j] なら 1, A[i] k 回目において,1 / 2 の確率でa[k] 番めの数とb[k] 番目の数が交換され…

Codeforces 226E - More Queries to Array...

問題文 : More Queries to Array問題概要: 配列 $ \normalsize a$ が与えられるので, 区間 $ \normalsize [l,\ r] $ の値を $ \normalsize x$ に変更する. $ \normalsize \displaystyle \sum_{i = l}^{r} a_{i} \cdot (i - l + 1)^k$ (ただし $\normalsize 0…

IOI 2005-day1 Mean Sequence

問題文 : 平均数列解法 : 数列の初項を決めると, 残りの数列の値も一意に定まる. 更に, 初項k の平均数列が作れなければ, 初項をk + 1 とする平均数列(またはk - 1 とする平均数列, あるいは両方) が作れないことが分かる. ゆえに, この数列の初項の値は連続…

JOI春合宿 2007-day4 lines

問題文 : 直線解法 :オイラーの多面体定理です."V(頂点数) - E(辺数) + F(面数) = D(次元) - 1"が成立するので, D=2から, F = E + 1 - V が求まります. EだったりV だったりは入力から簡単にもとまるので, 愚直に計算しても O(N^2 log N) で解を得ることが出…

準急さんの問題

問題:k<=100, N<=10^18, M<=1,000,000,007のとき、1^k+2^k+…+N^k mod M を1秒で求めるプログラムを作成せよ— 編集の都合上省略さん (@semiexp) 12月 19, 2011昔semiexpさんがこんな問題をつぶやいていたので、解いてみました. 結論から言うと, 僕の環境だ…

ファレイ数列のいろいろ

JOI春合宿や各種コンテスト, JJMOでたまに出題されるファレイ数列についていろいろ書きます. 面白い性質がたくさんあります.・ファレイ数列とは? 約分された分数を昇順に並べた一群の数列であり、正の整数 n に対して、n に対応する (または、属する、深さn…

JOI春合宿 2007-day3 Anagram

問題文 アナグラム(pdf注意, 1枚目)解法 : 元の文字列sの各文字を昇順にソートしたs'を考える. 目的の文字列の前にある順列の総数は, s'の先頭から文字を選んでいき, 元の文字列の接頭辞にならない文字列の組み合わせを全て求めれば求まる. もとの文字列と現…

JOI春合宿 2011-day2 keycards

問題文 : カードキー解法 : 包除原理のようなものをつかう.この問題は, "0 ~ 2 ^ (N - K)までの数から, すくなくとも1つ数をつかって論理積を0にする組み合わせの総数はいくつか", という問題に置き換えられる.数の選び方は, U = 2 ^ (2 ^ (N - K)) - 1 通り…