日報
2022年4月21日 by
2022/4/21(木)

今日は割とタスクを決めていた通りに取り組めた。

一昨日あたりから「寝る前に明日の予定(具体的なタスク)を決める」ということをやっている。予定を決めるのは前にもやっていたが、例えば「明日はこの問題を解く」「明日はこの本を読む」といった粒度では決めていなかった。そのために上手く区切りをつけることが難しかった。

昨日は思いっきり寝坊してしまったので午前中まともに活動できず、予定を決めておいたのが上手く効いてくれなかったが、今日は早起きしたのでいい感じに活動できた。具体的な予定の前決めは上手く効いているように思う。しばらく続けてみる。

今日解いた競プロの問題。

競プロ典型90問

026 Independent Set on Tree: 適当な頂点から距離が偶数になるものと奇数になるもので分ける。多い方はかならずn/2個以上あるはずなのでそこからn/2個取れば良い。なんとなく木を思い浮かべたら自然と思いついたのであまり意識しなかったが、二部グラフに関する教育的問題だったようだ。言われてみれば確かに、二部グラフでさえあれば木でなくても同じ論法が使えるな。

最大独立集合とやらも求められるらしいが、単純に奇数距離頂点と偶数距離頂点のうち「多い方」ではだめなのか？

023 Avoid War: なかなか凶悪な問題だった。解説を見たのにバグり散らかした。いっぺんちゃんと理解して実装したので次回以降はそれなりにパパっと書けるかもしれない。「細かく決めるDP」と「状態削減」はこれを機に血肉にしたいな。

当たり前だが、DPでは1要素づつ決める場合でも多数の既に決めた要素を持つ場合が多い。今まで決めた全ての要素の中で、これから決める要素を限定する全ての情報を持つ必要がある。逆に言えば、その分の情報さえ持っていれば細かく決めていくことが可能になる。もっと色々な問題にこれを見出して頭を慣らしたい。

なんで自力でこれが思いつけなかったのだろう？と考えると、「『次』を決めるのには必要ないが『次の次以降』を決めるのには必要な情報」をDPテーブルに持つという意識がなかったからであるように思う。「今見る情報」だけでなく「後でいつか見なければならない情報」は持っていなければならない。

それから状態削減。実は原理的にありえない状態が含まれていないか、というのを頭の隅に置いておくだけでずいぶん発想の幅が違いそう。新しいものを学べた。しかし原理としてはかなり単純な話だが、実装にかなり手間取ってしまった。

この問題の本質とはあまり関係のないことだが、std::unordered_mapよりもstd::mapの方がイテレータによる走査だけは速いということを学んだ。たまに役立ちそう。なんでこうなるのかは分からない。

検索や挿入削除ならともかく全走査なんて何使っても同じだろうと思っていたけれど、データ構造の取捨選択だけで4倍高速化するのヤバいな…

今日摂取したコンテンツ。

https://qiita.com/usagi/items/fc329895cebd3466910e

もっとRustぢからを付けてから読めば大変ためになりそうな記事だと思った。

いつになく平穏だな…

今日は腹筋をした。

Categories:

  • アーカイブ