脳log[20250125]

2025年01月25日 (土) [AtCoder] F 問題までけりがついたので今日あった ABC390 について。今回も前回と同じく F まで解けない問題ではないけど、すっごく時間がかかる。A 問題から５分かかったし。■A 問題 12435。１回転倒を直してみて 1,2,3,4,5 になるかどうか。最初からソート済みの場合が No であることに注意。■B 問題 Geometric Sequence。解答を書いてからサンプルを試してサンプルの３でひっくりかえった。公比 0.8 の等比数列ですって。３項で分数で等式を作って通分すればいいのかもしれないけど、そこは Ruby なので Rational におまかせ。■C 問題 Paint to make a rectangle。黒のマスを囲む上下左右の大枠を求めたら、その内部がすべて黒か？であるか。■D 問題 Stone XOR。N が 12 以下だけど、12 の階乗が 4.7 億 (470 メガ) を超えるので愚直 DFS は通らない。少なくとも Ruby では望みがない。愚直 DFS を書いて１分以上かかるのを確認してからどうやって処理量が減らせるか考えた。１の袋を２の袋に足してから２の袋を３の袋に足した場合と、１の袋を３の袋に足してから２の袋を３の袋に足した場合は区別する必要がない。どうやって同じことの繰り返しが防げるか。すでに混ぜ物がされている袋は他の袋に混ぜる必要がないのではないかと考えた。■E 問題 Vitamin Balance。ビタミンごとに３回処理をして、カロリーから摂取量への換算表を作る。摂取量で二分探索をして答えを求める。答えの二分探索の中で換算表を二分探索で逆引きすると TLE (と WA と RE) が出たので、ありうる摂取量のリストを作ってからどの摂取量が答えになるかを調べた。これだと支配的な要素はソートの O(NlogN) になる。■F 問題 Double Sum 3。間違った問題を解いていた時間がほとんどといっていいほど長かった。問題文中の大文字の L,R は数列の区間を表す数字だけど、小文字の l,r は数列の値の範囲を表す数字。自分は x 座標が上下で y 座標が左右を表していてもそんなのは便宜的な区別だからどうでもよくて、第１軸第２軸以上の意味を勝手に持たせて直感や慣例に反すると文句を垂れるつもりはないつもりでいたけど、大文字小文字が異なるだけで同じアルファベットに異なる意味を持たせるのは罠だと文句を言いたい。そういう誤読も含めて試行錯誤したことの結論だけ書く。小さい値から順に処理をして、自身が連続した値グループ(f 関数の内部で l,r で表される範囲)の中で最小の値である場合に限って、主客転倒で L,R の選び方を数えて操作回数を計上する。自身が値グループの中で最小の値であるとは、左右にある同値と -1 した値のどちらでも最も近くにあるものを含まず、自身を含む区間が選ばれた場合に、そのようなグループが発生する。l,i,r の３つの値を使って (i-l)*(r-i) の簡単な式で数えられる。■自分のすべての提出。宿題が多すぎるんよ。D から精進でした。いつまで水色かわからんで。