進捗
444問 → 473問
1問1問が重くなってきた。1度問題文を見たあと、考察難あるいは実装難に感じて後回しにしていたような問題が増えてくる。有給休暇を取得して丸一日考えるなどして満喫。
- 4/22 [394] [638] [654] [454] [370]
- 4/23 [448]
- 4/24 [441] [615] [604] [649] [418] [595] [593] [509] [640]
- 4/25 [598] [646] [656] [375]
- 4/26 [492] [545]
- 4/27 [538] [653] [386]
- 4/28 [298] [423] [498] [528] [657]
感想、勉強したことなど
・微分方程式が立ったからと言って、scipyの力を借りても、十分に良い精度でシミュレーションするのは難しい（問題作成側が、そういう精度を要求するようにしているとも？）。明示的に解けるときはなるべく解いてしまう、あるいはせめて定積分の計算くらいに帰着してしまう方が、速く正確に計算できる。
・numbaのdocumentをだいたい読む。定数倍くらいで1分切れなかったものを並列処理して1分切るなど。色々な課題が降ってくる分、いろいろな技術を試す機会があるのが良いですね。
・Forumから、Berlekamp Massey algorithmについて学ぶ。「解は線形漸化式を満たすはず」「漸化式自体は小さい解を適当な方法で求めれば推定できる」という思想そのものがそもそも馴染みの少なくて、こういうのが上手く使えると面白いなあと。数学の延長として競プロを初めた人ほど、なるべく論理的に式を作ろうとしてしまいやすいんじゃないかな。
algorithmの目的だけ確認したあと自力で考えて実装したら$O(n^3)$で下手。ちゃんと先人の知恵を勉強し直す。
・（全部自然数として）$an\leq b \iff n\leq \lfloor\frac{b}{a}\rfloor$となることはよく使う。同様に$an\geq b\iff n\geq \lceil\frac{a}{b}\rceil$が成り立つ。天井関数なしに書くならば、$\lceil\frac{a}{b}\rceil = 1+(a-1)//b$である。簡単だけどあまり経験なかった。
・segment木は未だに、基本構造を実装するために、絵を書きながら、デバッグしながらそれ1つで30分60分とかかる。
・[492] 安易な方法でも1日動かせば解けそう。手計算で変形してある程度シンプルな形に。綺麗に解けるとしたらこのくらいしか…と考えていたら解けた。基本的な漸化式の知識はあると思っていたが、これは知らなかった…なるほどスッキリ。
・[653] 日本では（？）某本で有名。
・[667] 速解きに参加。現実問題でもありえそうな雰囲気の、絵に描けるような有限の大きさの計量を1つさせるだけの問題、他の競技プログラミングサイトではあまり見ない面白い問題だと思います。
やるべきことは大体分かる。1時間でコードも書けて、正解者は誰も居ない。1位チャンス？とか意識してしまった。そこからひたすら答が合わない。制約条件が抜けてて変な解を出してしまったり、それを解消したはずなのに答が合わない。4時間ほど格闘してちょっと苦手意識がついたため、しばらく放置ｗ
