ワクチンの副反応から復活した。
結局接種日の翌日昼～翌々日午前まで続いた感じになる。体温は下がったが頭痛は微妙に残っている感じがする。
昨日～今日解いた競プロの問題。
競プロ典型90問-025 Digit Product Equation: 解説AC。
mでなくf(m)の方を固定して考えるという発想はあったが、なぜか「結局$10^10$通りじゃん」と思い込んでしまった。順序が関係なくなるので実際には$_{10}H_{10}=_{20}C_{10}<2^{20}$になる。組み合わせの数を過大に見積もって可能性を見逃すのそろそろやめたい。
$m-f(m)=B$でなければならないので、同じf(m)ならば条件に当てはまりうるmの値は一意に定まる。f(m)の値が同じになるような異なるmの値について考える必要はない。
$f(B+f(m))=f(m)$となるようなf(m)をカウントすればOK。
EDPC-M: dp[i][j]:=(何人目まで見たか、いくつ既に配ったか)として遷移すれば良い。ナイーブにやると$O(NK^2)$だが、適当に累積和をやれば$O(NK)$で解ける。Kはそこそこ大きいがNが小さいので助かった。
EDPC-N: 区間ごとに「区間内のスライムを全て一つにまとめるために必要なコスト」として区間DPすればよい。$O(N^3)$でなんとか間に合う。
EDPC-O: 最初dp[i][ptn]:=(i番目までの男性を見て、ビットマスクptnに対応する女性とマッチングしたときのパターン数)として$O(N^2 2^N)$で解いたが、これではTLE。マッチングした男性の数と女性の数は対応するので、単にdp[ptn]:=(ビットマスクptnに対応する女性とマッチングした時のパターン数)として普通にbitDPで遷移すれば$O(N 2^N)$で解けた。popcountを添え字にして配列にアクセスするあたり結構特殊な遷移に見えたのだが、典型なのだろうか？
EDPC-P: 単純に木をメモ化再帰すれば良い。「隣り合う点を黒で塗ってはいけない」という縛りは一般のグラフだと厳しいと思うが、木なので最後に塗った頂点の色だけ見ていけば容易に計算できる。
EDPC-Q: dp[i][j]:=(i番目の花まで見て、最後の高さがh[j]であるときの最大スコア)として遷移していけば$O(N^2)$で解けるが、もちろんMLE+TLEする。配列を使いまわせば空間$O(N)$にはなるが時間は$O(N^2)$のままでTLEする。のでセグ木で$O(N\log N)$に高速化して通した。DPコンテストなのにDPじゃないの何？と思って累積chmaxなどが使えないか考えたが、思いつかず。広義のDPという扱いで良いのかな。
EDPC-R: Kの値があまりにもクソデカいのでこれはダブリングだなと思った。
まずdp[b][i][j]:=(頂点iから頂点jへ2^b回で移動するパスの数)としてこれを求める。iからkを経由してjへ移動、というのを全パターンやるので$O(N^3 \log K)$。次にans[b][i]:=(K % $2^b$回移動して頂点iに辿り着くパスの数)として求めれば良い。$O(N^2 \log K)$。出発点も到着点もどこでもいいという問題なので、全てのiについてans[0][i]=1とし、最後に全てのiについてans[max b][i]を足す。結構シンプルに面白い問題で大変気持ちよかった。
競プロフレンズの解説だと行列累乗と繰り返し二乗法を用いていた。K回分の遷移の計算のためにダブリングを使うか繰り返し二乗法を使うかという違い以外は本質的に同じ解法だとは思うが、そうか行列累乗にも見えるんだな…というのが面白かった。
このはカレンダーをめくった。
こいのぼりめっちゃ泳いどる…
乗ってるこのはちゃんはどこを目指しているのかな。
「「ついやってしまう」体験の作りかた」という本を買った。よく出来ててなかなか面白い。少し冗長なきらいはあるが、シンプルに読みやすく書かれている。
心なしか本の中身自体も「つい」めくってしまうような構成になっているような気がした。
いい加減Bootstrap以外のUIフレームワークを何か一つ覚えたいと思い、Vuetifyを学習しだした。
見た目が好みだったので選んだが、v-なんちゃらみたいな要素名でやっていくのはかなり鼻につくな…やっぱ別のにしようかな…
Categories: 未分類