2021-10-08

セミ

セミが鳴いている
冬が一瞬姿を見せる十月の秋空、それでもセミは絶えず鳴き続けている
昼夜を問わず鳴いている

1週間ほど前の夜、急に大きな耳鳴りがしたので翌日の朝に耳鼻咽喉科に向かった
聴力検査を行い「2000Hz ~ 4000Hz帯の軽度の感音性難聴」という結果だった
薬を処方してもらい飲み続けはや一週間が過ぎているが、未だに改善の兆しすらない

突発性難聴は、明確に原因がわからない唐突に起こる感音性難聴の総称である
内耳の血液循環障害説やウイルス感染説などが考えられているが、現状の医学ではその明確な原因すら突き止められていない
いずれにせよ、内耳内の有毛細胞が死ぬことによって引き起こされているようである
しかし、有毛細胞は48時間程度の周期で髪の毛のように生え替わりが起こるようである
そして、髪の毛のように生え替わりが起きなければ有毛細胞はハゲる、つまりその部分の音を感じる有毛細胞がなくなり聞こえなくなるようである
ハゲている人の頭に急に髪が生えてこないように、有毛細胞に対して再生の循環が失われてしまったら、それは戻ることのない事実である
そのため、突発性難聴はできるだけ早くからの治療が要求され、治る可能性は時間と共に大きく減少していくようである
できれば48時間以内、特に1週間以内からの受診が要求され、1ヶ月程度で聴力は完全に固定されてしまうようである
早くからの受診ができたからといって1/3は回復し、1/3は部分的に回復、1/3は変わらずとされているようである
突発性難聴の原因や機序すら特定できていないのであるから当然だろう
自然治癒能力に対して補助輪をつけることしかできないのである

自分の場合は、もうすでに投薬1週間を超えて変化がないのでここからの回復は絶望的である
そこで次に期待するのは再生医療であるが、これはできたとしても数十年単位の話になるだろう
iPS細胞などで有毛細胞自体を生成するのは現状においても可能であるようであるが、聞こえるようになるまで機能的に長さや立体的構造を保って移植することは非常にハードルが高い
簡単に実験を行えるハゲの治療がiPS細胞などの再生医療が実現されてすらいない現状では、再生医療という希望は遥か彼方にある恒星のようである
確かに見え、その存在を感じ取れる輝かしい未来ではあるものの、それは限りなく遠い
最も突発性難聴に罹ったからといって生命に関わるような事態ではないし、それでいて生身の人間から有毛細胞を観察することができない以上その発展速度でさえもかなりの疑問符が残っている

残されている治療法はないだろうか
今後二十年で期待の持てる技術とすれば、strekin AG、Frequency Therapeutics、Otonomy社といった難聴治療薬の研究に取り組む創薬会社にかけるしかないだろうと私は考える
もっとも、各社ともにその研究進捗は、(基礎研究自体が進んでいないのであるから当然ではあるものの)芳しくないようである

調べれば調べるほど近い将来治ったり、症状が改善される希望はないことがわかってくる
宝くじが当たることを待つようにブレイクスルーが起きることに期待するしかない
少なくとも今後20年程度はこの耳鳴りは止まないのである

セミは突然鳴いた
季節外れの日から一切泣くことを止めずに
耳の中で泣き続ける
食事をするときも、お風呂に入るときも、スマホを使うときも、布団に入ってもなお鳴き続ける
一切構わずに鳴き続ける、私の頭の中でだけ
ほんのついこの前まであった安らぎはもはやこの世のどこにもない
この休まる場所がない苦痛は誰にも伝わらない
1万人に3人がかかる病気にかかり、1/3のハズレくじを引いてしまった
運がなかったけれど、くやしい、くやしい、くやしい、このやるせなさをどこにぶつければ良いの
誰か僕らを助けてくれ
セミは今も鳴いている

参考

2021-02-27

2021年の東工大数学の解答 (案) を作ってみた

解答(案)のpdf
[http://:title]

問5のグラフのgif
f:id:mathematicsian:20210227013253g:plain

gifをpdfに貼り付けようとしてかなり時間をかけのですが, 結局貼れずそのままあげることにしました. (そのせいであげるのが遅くなってしまいました.)

感想として, 去年, 例年と比べても考察難易度が低いように感じました

計算ミスが命取りになりそうで, 試験場では個人的には嫌な問題だと思います.

2020-08-01

個人的メモ

微分 積分関連

積分と極限の交換条件

Arzela の定理

有界閉集合 $[a, b$ ] 上の Riemann 積分可能な関数列 $\{f_{n} (x) \}_{n=1}^{\infty}$ が Riemann 積分可能な関数 $f(x)$ に各点収束しているとする.
このとき, 関数列 $\{f_{n} (x) \}_{n=1}^{\infty}$ が一様有界 ( $n$ に依らない定数によって抑えられる ) とき, 積分と極限は交換可能. すなわち

$\displaystyle{ \lim_{n \rightarrow \infty} \int_{a}^{b} f_{n}(x) \, dx = \int_{a}^{b} \lim_{n \rightarrow \infty} f_{n}(x) dx = \int_{a}^{b} f(x) \, dx }$

が成り立つ.
上の条件は一様でも良い ...
広義積分の場合, 可積分な優関数があればよかったハズ...

https://www.math.ucdavis.edu/~gravner/MAT125B/materials/Luxemburg-Arzela.pdf

線形代数関連

有名事実1

実対称行列の固有値は実数である
(証明) $\lambda \in \mathbb{R}, \, x \in \mathbb{R}^{n}$ を固有値と対応する固有ベクトルとする. このとき, 共役転置をとったものに関して二次形式から $\displaystyle{ \overline{x}^{t} A x = \overline{x}^{t} (\lambda x) = \lambda \| x \|}^{2} = (\overline{x}^{t} \overline{\lambda}) x = \overline{\lambda} \| x \|^{2}$ が成り立つので $(\lambda - \overline{\lambda}) \|x\|^{2} = 0$ から $\lambda = \overline{\lambda}$ : 実数

有名事実2

実対称行列の異なる固有値に対する固有ベクトルは互いに直交する
(証明) 固有値 $\lambda, \, \mu \in \mathbb{R}$ に対応するベクトルをそれぞれ $x, \, y \in \mathbb{R}^{n}$ とする. このとき, $\displaystyle{ x^{t} A y = x^{t} (\mu y) = \mu x^{t} y = (\lambda x)^{t} y = \lambda x^{t} y}$ から $(\lambda - \mu) x^{t} y = 0$ が成り立つので, 固有値が異なれば $\lambda \neq \mu$ より $x^{t} y = 0$ . すなわち直交する.

有名事実1

実対称行列は対角化可能

2020-04-29

精進記録 : Educational Codeforces Round #55 E. Increasing Frequency

問題概要

$n$ 個の正の整数からなる数列 $\{a_{i} \}_{i = 1}^{n}$ が与えられる.
このとき, 区間 $\left[ l, r \right] \, \left( \, \subseteq \left[1, n \right] \, \right)$ と整数 $k$ (負の数でも, 0でもよい) をそれぞれ好きに選んで, 区間上の各 $a_{i} \, \, \left( i \in \left[ l, r \right] \right)$ に対して $k$ を加えるという操作を1回だけ行う. (いわゆる区間加算)

このとき, 最大でいくつ数列の値を与えられる正の整数 $c$ に等しくすることが可能かを求めよ.

制約

$1 \leq n, \, c \leq 5 \cdot 10^{5}$
$1 \leq a_{i} \leq 5 \cdot 10^{5} \, \, \left( \, \forall \, i \, \in \, \left[l, r \right] \right) \,$

codeforces.com

考察

まず, はじめに浮かぶのは選ぶ区間の全探索だろう. しかし当然これは区間を走査するだけで $O(n^{2})$ かかってしまい間に合わない. そこで, 一旦操作を観察することにする.
もし, 区間 $[l, r$ ] に整数 $k$ を加えたとき, $k$ に等しくなるものは, 元の数列 $\{a_{i} \}_{i = 1}^{n}$ で区間 $[0, l )$ 上で $c$ と等しくなるもの, 区間 $[l, r$ ] 上で $c - k$ に等しくなるもの, 区間 $(r, l$ ] 上で $c$ に等しくなるものの3つに分けられる. すると定式化しやすそうなので定式化してみることにする. (ただし, 区間は半開区間で扱うことにする)

$S_{r}(a) := \text{半開区間 } [0, r) \text{ 上で整数 } a \text{ に等しいものの個数}$

と各整数 $a$ に対しての出現回数の累積和を表すことにすると半開区間 $[l, r)$ に対して整数 $k$ を加えた操作のときに $c$ に等しいものの個数は

$\begin{aligned} Count \, (l, r) &= \text{区間 }[0, l) \text{上の } c \text{ の個数} + \text{区間 }[l, r) \text{上の } c - k \text{ の個数} + \text{区間 }[r, n) \text{上の } c \text{ の個数}\\ &= (S_{l}(c) - S_{0}(c))+ ( S_{r}(c-k) - S_{l}(c -k) ) + (S_{n}(c) - S_{r}(c))\\ &= ( \, S_{l}(c) - S_{l}(c - k) \, ) + ( \, S_{r}(c - k) - S_{r}(c) \, ) + ( S_{n}(c) - S_{0}(c)) \\ \end{aligned}$

と, ( $k$ の選び方には依存するが ) 目的関数 $Count\, (l, r)$ を $( \, l \, \text{に依存する部分}) + ( \, r \, \text{に依存する部分}) + ( \text{定数部})$ に分解することができた.
これにより, 最適性を満たす区間のみを探索することにより探索範囲を狭めることができることができる.
ここで, 区間の右端を全探索することを考える. このとき, $k$ の値すなわち $c - k$ の値を定めると選ぶべき左端は即座に定まる. では, どのような値を選ぶべきか. それは明らかに右端の値を $c$ に変えるような値である. (そうでないと, 右端を左に1つずらすことで悪化させずに同様の問題に帰着でき, もし右端が $c$ の値と等しければより良い値を得られるからである)
したがって, $l, \, k$ は $r$ により定まっているので, 各整数について $l$ に依存する部分の最適値を適切に更新していくことによって, 時間計算量 $O(n)$ , 空間計算量 $O(max\, (c, \, a_{max}))$ で計算することができた.

実装例

codeforces.com

2020-02-26

2020年の東工大数学の解答 (案) を作ってみた

あってるかはわからないけど....

[http://:title]

感想として, 去年よりも難易度が平坦で計算がめんどくさいなという問題が多いという感想を抱きました.

試験場的には解きたくないという問題も多く, 去年ほどクソ楽という問題もないので, 平均点はさほど変わらないが得点分布が広がる感じ？(適当)

2020-02-10

ABC154-F をやった

問題概要

正の整数 $r_{1}, r_{2}, c_{1}, c_{2}$ が与えられる.

$f(x, y)$ を 2次元グリッド上の $(0, 0) \rightarrow (x, y)$ への最短経路の経路数とする. $f(x, y) = 0$ ( $x \lt 0$ or $y \lt 0$ のとき) このとき,

$\displaystyle{ \sum_{r_{1} \leq x \leq r_{2} } \sum_{c_{1} \leq y \leq c_{2}} f(x, y) }$

を求めよ.

atcoder.jp

個人的解法

基本的数学知識(数A程度) から明らかに, $f(x, y) = {}_{x + y} C_{y}$ であるが, その前に得られる自明な漸化式

$f(x, y) = f(x-1, y) + f(x, y-1)$

に注目して議論を行うことにする. (ただし, $x = y = 0$ のときの式であり, $f(0, 0) = 1$ とする.)

元の問題は, 2次元グリッド上の値と見ればの長方形型の値を求める問題とみなすとき, この問題は累積和を求めることと同値である. (累積和は部分問題であるし, 累積和を使って2次元累積和の基本的な使い方をすれば求められる.)
したがって, 二次元累積和 $\displaystyle{ S(a, b) := \sum_{0 \leq x \leq a} \sum_{0 \leq y \leq b} f(x, y) }$ を考えることにする.
すると, このとき, 上の $f$ に関する漸化式から次の関係式が成り立つ (+1の部分は $f(0, 0)$ の寄与分)

$S(a, b) = S(a, b-1) + S(a-1, b) + 1$

この式は線形っぽいが, 定数が扱いにくいので, $T(a, b) = S(a, b) + g(a) + g(b)$ の形であって $T(a, b) = T(a, b-1) + T(a-1, b)$ の形になる関数 $g$ があれば嬉しい. 所望の $T$ の関係式に, $T$ の定義式を代入すると

$S(a, b) + g(a) +g(b) = S(a, b-1) + g(a) + g(b-1) + S(a-1, b) + g(a-1) + g(b)$

Sの関係式を用いることで

$g(a-1) + g(b-1) = 1$

より, $T(a, b) = S(a, b) + 1$ とおくと嬉しいのではないかという予想がつく.

このとき, $T(a, b) = T(a, b-1) + T(a-1, b)$ および $T(a, 0) = a + 1, T(0, b) = b + 1$ が成り立っているが, $T(a, b) = f(a+1, b+1)$ となっていることがわかる. (パスカルの三角形を考えたら明らか ; 初項が1ずれているだけと思えば簡単)

したがって, 求める答えは

$\begin{aligned} (\text{答え}) &= S(r_{2}, c_{2}) - S(r_{2}, c_{1}-1) - S(r_{1}-1, c_{2}) + S(r_{1}-1, c_{1}-1) \\ &= ( T(r_{2}, c_{2}) - 1 ) - ( T(r_{2}, c_{1}-1) - 1 ) - ( T(r_{1}-1, c_{2}) - 1 ) + ( T(r_{1} -1, c_{1} - 1) - 1 )\\ &= T(r_{2}, c_{2}) - T(r_{2}, c_{1} - 1) - T(r_{1} - 1, c_{2}) + T(r_{1} - 1, c_{1} - 1)\\ &= f(r_{2} + 1, c_{2} + 1) - f(r_{2} + 1, c_{1}) - f(r_{1}, c_{2} + 1) + f(r_{1}, c_{1}) \\ \end{aligned}$

であり, $f$ は二項係数の計算で求められるのであったから, 二項係数を求める部分がボルトネックとなり $O(r_{2} + c_{2} + \log{mod} )$ で求めることができた.

感想

解けなければいけない難易度だったので, 計算ミスなどとても悔しい.

2020-01-28

ツイッターで見た問題について

ツイッターを眺めていると ABCのwriterをなさっている競プロフレンズさんが問題を出しておりましたので, その問題について個人的に考えたことを記します. (問題はツイッターを参照)

シロサイ「わたくしも前回のABCのために問題を用意していたんですけど、難しすぎると却下されてしまいました。ここに置いておくので、良かったら解いてくださいまし」 pic.twitter.com/1SZ0w0Ky1q
— 競技プログラミングをするフレンズ (@kyopro_friends) January 28, 2020

考察1

まず, 言えることは「モンスターを1度攻撃したなら, そのモンスターのHPが0以下になるまで攻撃をするべきである」ということである. 明らかもしれないが, 簡単にそのことを示す.
モンスター $i$ を攻撃した後まだモンスターがHP1以上であり, その後にモンスター $j (\neq i)$ を攻撃したとしよう. このとき, 倒れるまでの回数はモンスター固有であることを考えると, モンスター $i, j$ に関する攻撃の順序をどのように入れ替えようとも両方が倒れる時点は変わらない. ここで, モンスター $i$ が $j$ よりも先に倒される場合, 攻撃対象をモンスター $i, i, ..., i , j, ..., j$ の順に攻撃順序を入れ替えるとモンスター $i$ は元の攻撃よりも早く倒れ, 結果モンスター $i$ から食らうダメージが減り, $j$ からのダメージは変わらないので結果として被ダメージは減少する. 同様に, $j$ が先に倒される場合は $j, j, ...., j, i, i, ..., i$ の順序に入れ替えることで被ダメージを減らすことができる. これを全てのモンスターに関して倒される前に別の攻撃対象に変わっているなら前述のように並び替えることをすると, 上記で述べた戦略がある種「局所最適解」として得られる.

考察2

したがって, 上記の戦略からどのモンスターを順に倒すかを探索すれば良いということになる. これをもし全探索するとすると, 計算量 $O(n!)$ かかってしまい間に合わない. そこで, 順序を全探索する際の典型 bitDPを使うことで計算量を $O(n \cdot 2^{n})$ に抑えることができ, 間に合うようなコードが作ることができる.

考察3

TLを見ると, もっと大きい制約で解くことができるという旨のツイートがあったのでそれについて考える.
各モンスター $i$ に対して体力 $H_{i}$ とその攻撃力 $D_{i}$ があるが, 倒すために必要な回数を $S_{i} := \lceil \frac{H_{i}}{A} \rceil$ とすると, このとき受ける総被ダメージは

$\displaystyle{ \sum_{i = 1}^{n} \left( \sum_{j \leq i} S_{j} - 1\right) D_{i} = \sum_{i = 1}^{n} \left( \sum_{j \leq i} S_{j} \right) D_{i} - \sum_{i}^{n} D_{i} }$

と書けることに注意する. もし最適解を与えるような倒す順序が得られているとし, その順番に添字を並び替えて以降は考える. そのとき, $i, i + 1$ 番目を交換したとすると, その被ダメージは $- S_{i} D_{i+1} + S_{i+1} D_{i}$ 増加する. したがって, 全ての $1 \leq i \lt n$ に関して $- S_{i} D_{i+1} + S_{i+1} D_{i} \leq 0$ , すなわち $\frac{D_{i}}{S_{i}} \leq \frac{ D_{i+1} }{ S_{i+1} }$ である必要がある. つまり, $c_{i} = \frac{D_{i}}{S_{i}}$ と表す時 $c_{1} \leq c_{2} \leq ... \leq c_{n}$ が成り立っている. すると, 順序が"ほとんど一意"になるような条件が必要条件から得られた.
次に, この等号の中でどのような順序を選択するべきかを考えなければいけない、と言いたいところが, 上記の式を考えると、等号が成り立つどの隣り合う2要素の順序を交換しても被ダメージは変わらない. したがって, 等号内がどのような順序であろうと, 等号内で隣接swap操作を行うことで値を変えることなく想定した最適解を与える順序に並び替えることができる, すなわちソートされているならば最適解と同じ値が得られるのである. ゆえに, ソートして累積和を用いて計算すればよく, 答えが $O(n \log n)$ で求めることができた.