今日解いた競プロの問題。
ABC265-E: 全探索すると当然時間が足りない。Nはそれほど大きくはないので、基本方針としてはいかに考慮する状態数を限定してワープ1回の計算を少なくするかを考えていくことになる。
座標の範囲は最大10^12オーダーと結構広く、また足し算が行われるので、座標圧縮の類は厳しい。Nが小さいことに目を付けると、具体的な座標を記録せずとも3種類の移動のうちどれを何回やったかということだけ記録すれば良いことが分かる。状態数は$O(N^3)$オーダーとなり十分メモリに記録でき、DPをやっていくことができる。
k回目のワープ時においてはすでにk-1回ワープしたはずなので、$_3H_{k-1}$通りの状態についてそれぞれ3通りのワープを試してみればよい。障害物の位置はsetの類を使って管理する。これで1回のワープ当たり$O(N^2\log M)$、全体$O(N^3\log M)$で解けた。ハッシュセットなら$\log M$つかないのか。最悪計算量がアレだからあまり積極的に使わんのだが。
早起きして、朝ご飯を食べて、昼ご飯を食べて、夕方かなりグースカ寝て、めちゃめちゃまったりしてしまった。作業はそれほど進まなかった。
とりあえずCMakeの勉強が進んだ。TheolizerのCMake講座を読み切れた。
CMakeにおける主な登場概念は以下の通り。
- プロジェクト
- もっとも大きな管理単位
- 1つのCMakeLists.txtに対応
- CMakeコマンド
- CMakeLists.txtに記述
- 1種のスクリプト言語として実行されるものと考えて差し支えない
- どれも例外なく
コマンド名(引数1, 引数2, ...)の形式で記述される
- 変数
- CMakeスクリプト上で扱える変数
- 型は文字列のみ
- ちゃんと関数などでのスコープもある
- ターゲット
- CMakeスクリプトによって定義されるビルド対象
- 実行ファイル、ライブラリ、カスタムターゲットの三種がある
前に「変数」とは別で「プロパティ」とかあるのを聞いた気がしたのだが出てこなかったな？まあ必要ならそのうち出てくるだろう。
目的はfind_packageで読み込めるライブラリを作成することなのでこの第10回が主な目当てだったのだが、部分的に当てが外れた。ライブラリを読み込む側視点のことしか書かれていなかったのだ。
～～-config.cmakeというのを書いて「これを読み込んでね」ということにすれば良さそう、という大前提は理解できたので良かった。～～-config.cmakeの書き方自体は別所を頼ることになる。
https://qiita.com/osamu0329/items/134de918c0ffa7f0557b
8年前の記事だが、CMakeほど古いソフトならこうした基本的なあたりの使い方は変わっていないものと信じて良いだろう。
筋トレをした。今日はスクワット。
今日摂取したコンテンツ。
http://ribon.shueisha.co.jp/manga/seiri_kanpeki_book/index.html
りぼん編集部による「生理カンペキBOOK」。普通にためになった。
こう、生物学的というか、理科的な知識でなら自分もある程度生理とかについて分かっているつもりなのだが、実際に女性がどう対処しているのかとかどう感じてどう受け止めているのかみたいな部分になると一切分からんとしか言えないので、こういう資料とかこういう資料が出されてありがたがられてる状況とかはすごく勉強になる。
https://yukariasano.blogspot.com/2022/08/20228.html
翻訳家視点での機械翻訳の話。ポストエディットというのは初めて聞いた。機械翻訳の訳し直しが正規より安いというの、マジ？という感じがする。クソコードに手を入れて動くようにするよりもゼロから書く方が遥かに楽なので、プログラマ的には直観に反する。
https://www.leon.jp/health/12624
筋肉体操に関するインタビュー記事。当たり前かもしれないが「筋肉を付ける」ことと「脂肪を落とす」ことをちゃんと別軸で語っていて良い。
有酸素運動も大事ですよーというの
Categories: 未分類