sk か sk%P かという違い。余りをとるコストをケチってかえって Bignum のコストを支払って TLE になっていたのだった。あほ。■F 問題「Operations on a Matrix」(青 diff)。昨日は問題を読みもしなかった。やることは明らかだけどどう効率的に実装するかという問題。□最初の提出 #32096736 は TLE/MLE になった。長さ 20 万になりうる配列を最大 20 万回複製しようとしていたのだから、40 ギガを数倍したコストが予期される。TLE/MLE も当然。□次の提出 #32097180 で AC。クエリ先読みで必要な値だけ覚えるようにした。典型です。最近では ABC202-E「Count Descendants」を解くときに同じことをした>TLE、AC。E 問題を AC してから 50 分だから、%P を %P とタイプするだけの手間で E 問題を AC に持って行けていれば６完もありだった。幸せな皮算用。n 頂点の木から辺を 1 つ取り除いてサイズ n の連結成分を作ることはできません」ので、Sn が 1 の場合も不可。他には、木において辺とは頂点集合を左右２つの連結成分に分けるものなので、Si と Sn-i が食い違う場合も不可。ここから答えの構築を考えた。大きさ１の連結成分から始めて１つずつ大きくして N/2 までの連結成分を作る。N/2 より大きい連結成分は大きさ N/2 以下の連結成分の片割れとして自動的にできあがっているので考えない。Si が 1 の場合、直線状に伸ばすことで大きさ i の連結成分が生じるようにする。Si = 0 の場合、葉を生やして横に大きくすることで大きさ i の連結成分が生じないようにする。最後に余った頂点をすべて葉としてくっつけて始末する。■提出 #31963209 (AC / 403 Byte / 131 ms)。以前に解こうとしたときは、大きさごとに連結成分を分けてプールして、小さい連結成分を組み合わせることでより大きい連結成分をプールするような処理を考えていた。実はプールする連結成分が１つだけでいいことと、大きさ１の連結成分(葉)がすごく便利に使えることに気がついたので今日は解けた。■コメントアウトしてある部分は、解答と入力に矛盾がないことを確かめるために、解答から入力と同形式の文字列を作って比較している。そのために judge.rb27 を書いた。■ブログを読んでいたら、解答のような木には「キャタピラ木 (Caterpillar tree)」という名前がついているらしい。わざわざ名前を付けて区別して嬉しい理由があるのでしょうね(調べない)。
ans -= N if X == 0 がはまりやすい罠に見える。X がゼロの時、同一頂点をペアにして数えてしまうのを除外している。もしやと思って直前の WA 提出 #2757181 を調べてみるとこれが抜けていたのが原因だった。WA から３分半で気がつくかあ。無理だよ。他に Ruby で解いている人はゴルファーが一人いるだけ。古い問題なのもあるだろうけど、一見して面倒くさく見えるのも影響してそう。■ブログ記事を７つ読んだけどどれも LCA で相殺を利用していた。考える前に手を動かしている脳筋はいないのか、脳筋は。2020年7月にサービスを終了しましたアクセスログ解析サービス Visionalist においてログ収集システムとして利用しておりました“tracer.jp”ドメインを、当社が廃止した後、第三者がドメイン管理会社から取得し、セキュリティ上問題があるスクリプトを設置している可能性があることが判明しております。」)、ドメインの所有者が変わって(変わらなくても)中身が変わることがあるわけなので、接続しているサイトと異なるドメインから送られてくるスクリプトは基本的にブロックするよね。tracer.jp ドメインがその例だし、今でも facebook.com とか google-analytics.com から送られてくるのとか必ず。めんどくせー奴。
(a-x)*dy<=(b-y)*dx (遅い) か dx * px + dy * py >= threshold (速い) かに由来している。演算子の数が違うからね。だけど３つのペクトルをどう組み合わせれば引き算部分を事前に済ませておけるのかわからない。もうひとつ 10 行目の offsets.max_by もわからなかったよね。自分は辺と点の関係をあっち側こっち側の２値でしか扱わなかったから、値の大小を比較する max_by が選択肢になかった。外積が平行四辺形の面積なら値の大小は高さの大小であり符号と絶対値は辺のどちら側にどれだけ離れているかを表している。こちら側に一番離れている点が選ぶべき代表点であり、それを max_by で選べると事前準備の M 回の繰り返しがすごくシンプルになる。自分の提出は少なくとも２つの点で遅れをとっていた。■というのを踏まえて整理しました。提出 #31797336 (AC / 333 Byte / 1575 ms)。短く速くなった。速さは同じくらいに追いついたけどメモリ使用量がほぼ例外なく 1.5 倍くらいあるのがよくわからない。とくに富豪的な無駄遣いはしてないはずだけど……(多重代入？)。事前計算については意味を考えず単純に展開してクエリと無関係な定数部分を括りだして覚えておいた。c+d を文字列の連結のつもりで書いたけど 7 行目で .chars ではなく .bytes を呼んでるので文字コードの足し算になってしまってる。それだと a と d が位置を交換している場合と b と c が位置を交換している場合など、異なる文字コードの組み合わせだけど和が一致する場合を区別できない。