筋トレやった。今日は腹筋。
久しぶりにジョギングした。
最近何やら、思いっきり息を吸い込もうとすると咳きこんでしまうというちょっと良くなさげな状態が続いていた。しかし今日、走っていて息が荒くなってきたときに咳をするのをちょっと我慢してみたら、まるで詰まりが取れたかのようにいきなり治って普通にある程度激しく呼吸できるようになった。一体全体なんだったんだ。
今日解いた競プロの問題。
競プロ典型90問
038 Large LCM: $(A/gcd(A,B)) \times B \leq 10^{18}$かどうかを調べる。整数の範囲では$x \times y \leq z \Leftrightarrow x \leq \lfloor z/y \rfloor$であることを利用する。これの証明やるたび忘れるからいつも不安なんだよな。ちゃんと覚えておこう。
$$z/y – 1 < \lfloor z / y \rfloor \leq z / y$$
なので、
$$x \leq \lfloor z / y \rfloor \Rightarrow x \leq \lfloor z / y \rfloor \leq z / y$$
が成り立つ。また整数の範囲では
$$p<q \Leftrightarrow p \leq q – 1$$
なので、
$$x \leq z/y \Rightarrow x-1 \leq z/y-1 < \lfloor z/y \rfloor \Rightarrow x \leq \lfloor z/y \rfloor $$
という風に逆も成り立つ。
ARC140
A: 長さNの文字列Sに操作をk回施したものを$g_k(S)$と書いてみる。当然のことながら$g_0(S)=g_N(S)$である。
仮に$g_a(S)=g_b(S)$ならば$g_{a+1}(S)=g_{b+1}(S)$でもあり、$k=b-a$とすると任意の自然数iについて$g_a(S)=g_{a+ki}(S)$でもある。
$g_0(S)=g_N(S)$であることを考えると、仮にある整数$a$が存在して$g_0(S)=g_a(S)$かつ$0<k<a$なるkについて$g_0(S) \neq g_k(S)$が成り立つならば、そのような$a$はNの約数でなければならない。
この$a$は要するに周期となる。周期が短い、つまり$a$が小さいほど求める$f(S)$の値も小さくなるので、小さい$a$から順に試して可能かどうかを調べていけばよい。
可能かどうかの判定は、文字列Sからmod aの等しいi番目の文字を全て揃えようと思った時の最小コストを調べればよい。これはO(N)で判定できる。約数の数は$O(\sqrt{N})$なので全体$O(N\sqrt{N})$で解ける。
最初判定処理を変なやりかたでやってバグらせた…
B: Rの両肩にAとCがくっついている限り操作が出来る。なので各Rについて左のAの数と右のRの数のminを調べればよい。AとCを使いつくした、あるいはRを消してしまったあとの残骸はゴミであり、そこから新たに可能性が生まれる心配はない。
奇数番目の操作(ARC->R)は単にAとCを一つ消費する。使いつくした場合はゴミになる。なるべくmin(A, C)の多いやつから使っていけばよい。
偶数番目の操作(ARC->AC)はその塊をまるごとゴミにする。腹立たしい。なるべくmin(A, C)の少ないやつを生贄に捧げる。
Dに少し喰らい付けたが駄目だった。とりあえず確定済みの辺を全部張り、連結成分ごとに未確定の辺の数を持って未確定の辺をDPで決めていって…みたいなことを考えたが、解く道筋にはつながらなかった。解説読んだらサイクル検出をしており、要するになもりグラフなことを利用するっぽかった。N頂点N辺ということでなもりグラフなこと自体は気づいていたんだが活用する発想がなかった…
今日見たコンテンツ。
https://medium.com/@evanwallace/rendering-realtime-caustics-in-webgl-2a99a29a0b2c
波だった水面に光が差し込んだ時に水中で出来る独特のあの模様を「コースティクス」と呼ぶらしい。それの近似シミュレートの技法に関する記事。上手いこと考えるものだ。
https://zenn.dev/mmomm/articles/525253649e0a227989d9
https://zenn.dev/mmomm/articles/c5de7cbfef7788a7ccbb
フロントエンドの(ある程度)網羅的な知識の記事。テストについて調べてたら見つけたのだが、テスト以外の分野に関する記述もなかなか良かった。
HTMLの基本くらいはさすがに大体知っていると思っていたのだが、WAI-ARIAとかは全然知らなかったな。確かにrole=””みたいな記述あるけど、なんかjavascriptのライブラリでそういう目印を付けるやつがいるんだろうくらいにしか思っていなかった。標準規格があってそれに従って付けてるものだとは思わなんだ。
https://toyokeizai.net/articles/-/589234
ONKYO破産の背景に関する社説記事。音楽は良く分からないが、生き残ってるものとそうでないものの違いに関する一考察としてまあまあ面白かった。
https://note.com/museifudeiijan/n/ne91a26a51941
なんか面白かったから読んだ。
自分は政治に対して「面倒だけど文句言わなきゃいけないところは文句言わないと後々さらに面倒だからなあ」くらいの感覚で興味を持っている人間であり、他の大体の人間もそんなもんだと思っていたのだが、funやinterestingの方面で興味を持っている若者って存在するんだ…というのがちょっと衝撃だった。
Categories: 未分類