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

DDCC2020予選D: なんか最初色々最適な順序について考えたがこれ順序関係なさそうだなと途中で勘付いた。もっと早く気付け。大雑把なイメージとしては、スコアは文字数+和が9を超える回数であって、9を超える回数はどうやっても変わらないので多分順序無関係。端から順に足していくことだけ考えればよい。

単純にシミュレーションすると当然TLEする。数式的に解こうかとも思ったが色々なケースの処理に厳しそうなものを感じたので、ダブリングで通した。ダブリングはなんか同じような操作をすごい回数やる＋回数から数式的に頑張るのは厳しいという場合に選択肢として使いやすい気がする。以下のようなDPテーブルを定義してやった。

dp[k][i][j]:=(数字iに数字jを$2^k$個まとめて数字1つにまとめたときに辿り着く数字、および操作回数のペア)

本格的に解ける問題が少なくなってきた。こう、解ける問題が少なくなってきたら解説ACを増やしてそしたらまた自力ACできるのがワッと増えるみたいなのを夢想しているのだが、あまりそうなっているか分からない。じわじわとは増えているかもしれないみたいな気はするのだが。

---

boost::asioの研究を進めた。主にUDPの実験をした。そもそもチュートリアルとしてはどこを見れば良いのか分からなかったが、ここを見れば良いようだ。

https://www.boost.org/doc/libs/1_80_0/doc/html/boost_asio/tutorial.html

receive_fromは何かしら受け取るまでブロックするが、async_receive_fromは引数に受信時のハンドラを渡して即座に返る。

ハンドラが動作するのは一回のasync_receive_from呼び出しにつき一回だけらしい。なので、持続的に受信し続けるには受信ハンドラ内で再度async_receive_fromを呼び出す必要がある。また、プログラムがすぐ終わってしまうので、io_service::run()を呼ぶ必要がある。(run()をしないとそもそも非同期待ち受け処理自体行われなかったりする？そこは良く分かっていない)

---

筋肉体操をやった。今日は腹筋。