昨日電子工作をやっていたら2時くらいの就寝になってしまったので、今朝は大変に寝坊してしまった。電子工作は簡単に作業の中断がしにくいためか、どんどん時間を吸われる。
主に道具の後片付けに時間がかかるせいで作業中断の意思を決定するコストが高くなるので、部品を片付けやすくなるよう整理を頑張ってみている。今まで大きい鞄にほぼ全てをぶちこんでいたが、最近は仕切り箱に順々に移している。今日は100均で箱を2つ購入し、マイコンチップとピンヘッダ・ピンソケットを収めた。そのうち良く片付くようになれば作業の切り替えも多少なり楽になるだろう。
(関係ないことだが、休み期間中でも「寝坊」という認識が発生するのに結構自慢というか感慨深いものを感じている。)
基板の切り出しのためにこの前買ったバンドソーを引っ張り出した。まさにこういう用途のために買ったのだ！今まで切断砥石とかで大量の粉をまき散らしてひいひい言いながら切っていたのが、もう嘘か幻だったかのようにサックサク切れる。シュイーと切ってすぐ終わり。粉はまあ出るが、構造的に台の上に打ち付けられて積もっていく形になるのでほとんど舞わない。最高の気分だ。
切れたのはまあ良かったのだが、使っていない間にほこりが積もっていたため、使い始める前に少し掃除をしなければならなかった。そこで、次回以降こんな手間を被らないために、100均で適当なサイズのシートを買ってきてかぶせた。これでかなりマシになるだろう。
今日解いた競プロの問題。
ABC228-E 一応自力ACか。解説見ても自力で分かったことしか書いてなかったので、ずっとコードを見直してみたら間違いを発見した。
フェルマーの小定理から$M^{K^N} mod P\equiv M^{K^N mod P-1} mod P$なのでそれを実装するだけなのだが、なぜかバグりちらかした。最終的な原因はmodの取り忘れだった。
自分のライブラリのmodintはグローバル変数にMODの値を持っていて、そこに10^9+7なり998244353なりを代入して使うという設計なので、複数のmodを同時に取り扱う設計になっていない。なので仕方なくmod998244354のpowだけ書いたのだが、こいつにmodの取り忘れのバグがあった。
どの計算についても直後にmodをとるように気を付けていたのだが、そもそも一番最初にmodをとるのを忘れていた。そりゃバグる。悔しいが、頭から完全に抜けていた。
ABC231-F 自力AC。2次元空間の矩形領域の中の点の数を数える問題だが、広いので工夫が必要になる。スパースなのは座圧するとして、座圧してもN^2オーダーの空間になってしまい、まともにメモリに収めることも数えることも難しい。
「DPの計算途中らへんの値を使う」感じの発想を使えばどうにかなりそうだということに気付き、プレゼントをAiでソートしてBITに順次Bi軸上での点の数を追加しつつ走査して勝った。面積N×Nの矩形領域の点を数えると考えると難しそうだが、長さNの区間の点を数えるならば難しくはない。そして、途中まで点を追加した状態で区間の点を数えるならそれは矩形の中の点を数えたことになる。
別の問題の教訓を生かして前なら解けなかった(であろう)問題が解けると気持ちいい。道具的なアルゴリズムではなく抽象的な発想レベルの教訓が生かせた場合は特に。今回はABC216-Fの経験が生きた気がする。
ABC234-F 自力AC。「種類」と「数」にしか意味がないことには真っ先に気付けたので、アルファベットの数が高々26種類しかないことを利用する可能性にはすぐに思い当れた。DPの遷移の方法にはやや悩んだが、dp[今まで考慮したアルファベット][文字数]として、どこに何文字挿入するかで遷移するので行けた。若干歯ごたえがない気はするがまあ楽しい問題。
なんとなくDPで時間計算量がO(N^2)だと空間計算量もO(N^2)になるような気がするけど、今回はそうではなかった。この思考バイアスのせいでDPテーブルの定義を考えるのに時間がかかってしまったな。
ABC240-F 自力AC。ちゃんと数学的に(というかほぼほぼ算数だけど)詰めたらどうにかなる感じの楽しい問題。詰めるところは詰めなければならないけど、頭が爆発するような厳しい場合分けとかが必要になるわけではないのでちょうどいい難度の問題だったな。
今日で水diffは自力AC出来そうなABCの問題はほとんど終わってしまった。後に残っているのはARCの魔境の問題ばかりだ。正直青埋めに行ってもいいかもしれない。
作りたいと思っているアニメの絵コンテを書いた。全体の3割くらい。脚本は出来たつもりでいたが、絵コンテに直してみるとテンポとかが速すぎたり場面の説明が不十分だったりする部分がかなり多いことを感じる。映像って難しいな。
Categories: 未分類