OpenXR入門をちょっと書き進めた。
ジョギングをした。2.5km。
ABC304に出た。
A: C++ならmin_elementを使うと最小の場所がすぐに取れて実装しやすい
B: 面倒なので文字列として扱うと良い、最初3文字はそのままであとは’0’に置換
C: sqrtとかやるもんじゃないので距離は整数で処理する。あとはUFで繋げる。BFSでも行けるらしい。
D: にぶたんで縦横どこのブロックに入るか判定してカウントすればよい。W,Hの値次第ではブロック数がクソデカになるのでmapで記録する。
E: とりあえずUFで最初のグラフGを作る。各xi,yiの組についてUFでの根を見て「この2成分がくっついてはいけない」というのを記録する。各pi,qiの組について「くっついてはいけない対」に含まれているかどうかをsetなどで判定すればよい。
F: 要するに各約数Mについて周期Mのシフトを作れる。
とりあえずNの全約数を求める。それぞれの約数Mについて、考えられるシフトのパターンは2^(M日のうち働かなくてもよい日数)であるが、M日の内働かなくてもよい日というのは要するにi,i+M,i+2M,…日目の全てで高橋君が働いている日ということである。これは$O(N)$かかるが、約数の数は高々$O(N^1/2)$なのでそれと合わせても$O(N^3/2)$で収まる。
ここで問題文にも書かれている通り、Mが違っても同じシフトになる場合を除く必要がある。異なるMで同じシフトになるのはどんな場合がありうるかを考えると、片方がもう片方の倍数であるケースが考えられる。より定量的に考えて、異なる複数のM(仮にm1,m2,m3,…とする)で同じシフトになる場合、miの内の最小値をpとすると全てのmiはpの倍数であることが分かる。なので最小値のところだけでカウントすればよい。
あるMについて上記のやり方でパターン数を求めた上でその全ての約数についてパターン数を引けばよい。約数はわざわざ求めなおさずとも最初の約数テーブルを使えばよい。計算量がきつそうに感じるが、約数の数は実際は$O(N^1/2)$よりだいぶ緩やかなことが知られているので間に合う。
G: なにも分からず。
Ex: 解説とほぼ同じ(左から決めるか右から決めるかの違いだけ)っぽく見えるのだが通らなかった。何が間違ってるんだ…
今日摂取したコンテンツ。
https://hayatoito.github.io/2020/investing/
投資に関する記事。こう見ると「真っ当なことをすれば全員得する」システムはよくできてるな～と思った。
scarletfireboltという競プロ界隈思い出話を偶然聞いた。
Categories: 未分類