2024/10/28~11/3

# 2024/10/28~11/3 ## 10/28 ### yukicoder 2950 Max Min Product https://yukicoder.me/problems/no/2950 monotonic stackとかは初手の初手 $\sum_{i = l}^{r - 1} A_{i}\times B_{i}$ の計算及び $A_{i}, B_{i}$　の区間更新が遅延セグ木に載るのが本質だった。ABCの参加しなかった回に出たテクに丁度やられてしまった。 [提出](https://yukicoder.me/submissions/1023302) https://yukicoder.me/submissions/1022920 を見る感じ、分割統治でもできそうだ。確かに。 $\sum_{l}\sum_{r} \text{hoge}_{i = l}^{r}$ ってやってることがパスの数え上げだから、分割統治でできそうという気持ちにならないとだめだな。 ### 3rd UC Stage 8-J Even or Odd Spanning Tree https://contest.ucup.ac/contest/1780/problem/8941 本番中に提出したコードの`min`を`max`にしたら通った。笑った。チーム揃って考察ガバガバじゃねぇかよ。 UCの提出は本名がばれるので貼らない。 ## 10/29 ### AOJ2559 Minimum Spanning Tree https://onlinejudge.u-aizu.ac.jp/problems/2559 https://www.slideshare.net/slideshow/ss-17402143/17402143 にある通り凸なので、一本見れば良い。木上のパスをchminする問題に帰着する。双対スパーステーブルを書いてライブラリに追加した。 [提出](https://onlinejudge.u-aizu.ac.jp/status/users/zawakasu/submissions/1/2559/judge/9796117/C++20) ## 10/30 ### 3rd UC Stage 8-J Team Arrangement https://contest.ucup.ac/contest/1780/problem/8936 全部の分割を試していいのアハ体験だったな。これ本番で気づけ無いの愚かすぎた。すみません。判定問題にlogつけたが余裕で通った。助かった。 ## 10/31 ### 3rd UC Stage 14-J New Energey Vehicle https://contest.ucup.ac/contest/1817/problem/9528 結局の所、駅で回復する燃料の量を最大化する問題だと言える。これは「現在地の先にあってかつもっとも近い駅の燃料を使用する」貪欲が正当となる。考察も実装もグダグダしてしまった。大量にペナを生やしてしまった。手を動かさず考える時間をもう少しとるべきだった。反省 ## 11/01 ## AOJバチャ AOJ上で[バチャ](https://onlinejudge.u-aizu.ac.jp/services/room.html#batya_20241101/info)を走った。3hでA, B, C, E, Fの5問をACできた。 ### A: AOJ3308 (N + 1)-legged race https://onlinejudge.u-aizu.ac.jp/problems/3308 レースに出場させる $N$ 人を固定させたとき、人の並びは $H$ の昇順とするのが最適である。$H_{r_i}\le H_{r_{i + 1}}$を仮定すると、$\sum A_{r_i} + H_{r_1} - H_{r_N}$を最大化する問題に帰着する。 $(A_i, H_i)$を$H_i$の昇順にソートしておく。$\text{dp}[i][j] :=$ ith/$j$人選んだとする。一人目と$N$人目を選ぶときだけちょっと注意して、あとはシンプルなdpである。 [提出](https://onlinejudge.u-aizu.ac.jp/solutions/problem/3308/review/9808568/zawakasu/C++17) 難易度200でも普通に考察要素がある。Regional埋めは大変そうだ。 ### B: AOJ1232 Calling Extraterrestrial Intelligence Again https://onlinejudge.u-aizu.ac.jp/problems/1232 長々とストーリーが書いてあるが、本質は > In other words, you will receive an integer m and a fraction a/b . It holds that m > 4 and 0 < a/b ≤ 1 . You should find the pair of prime numbers p, q such that pq ≤ m and a/b ≤ p/q ≤ 1 , and furthermore, the product pq takes the maximum value among such pairs of two prime numbers. You should report p and q as the "most suitable" width and height of the translated picture. と制約のみ。 $m$ が小さいので、篩を貼れる。 $pq\le m\rightarrow p\le \sqrt{m}$なので、$p$で全探索できる。$q$は$\lfloor\min(\frac{pb}{a}, \frac{m}{p})\rfloor$以下の最大の素数とすれば良い。素数砂漠は対して広くないので、これも愚直に探して良い。 [提出](https://onlinejudge.u-aizu.ac.jp/solutions/problem/1232/review/9808591/zawakasu/C++17) ストーリー読み飛ばしたけど正しく題意を解釈できて良かった。本番とかでストーリーをどう扱うか(飛ばすか、読むか)悩みどころ ### C: AOJ3353 Sloppy city planning https://onlinejudge.u-aizu.ac.jp/problems/3353 sccした後のグラフについて考える。DAGだが、全部の頂点間に(一方向に)有向辺が張られている状態となる。グラフ全体が強連結で無いならば、出次数0/入次数0の強連結成分がただ一つ存在する。$N\ge 3$という制約から、入次数0の強連結成分から出次数0の強連結成分へ行くパスを一つとってreverseすると全体が強連結になる。以上よりダイクストラに帰着した。 [提出](https://onlinejudge.u-aizu.ac.jp/solutions/problem/3353/review/9808618/zawakasu/C++17) 取り組んでいるときはSCCせずともグラフ全体が強連結で無いならば出次数$0$の頂点が存在すると考えてそのように実装したが、嘘であることに気づいた。 hack > 6 > 1 -1 1 1 1 > 1 1 1 1 > 1 1 1 > 1 -1 > 1 実際全然見当違いな値を出力しているのだが、ACしてしまった。テストケースよわ... ### E: AOJ1437 Incredibly Cute Penguin Chicks https://onlinejudge.u-aizu.ac.jp/problems/1437 $\text{dp}[i] :=$ prefix$i$項を考慮したときの解答えは$\text{dp}[N]$である。普通にやると$\Theta(|S|^2)$かかるので頑張って高速化する。「IとPが同じ数で、CがI, Pの数より多いのでICPC-ishである(★)」ような状態を考える。「$B_{i} =$$i - 1$項目までのIの数-Pの数」とすると区間$[l, r)$が★ならば$B_r - B_l = 0\rightarrow B_r = B_l$が成り立つ。よって$B_i$が同じ値の$i$毎に独立に考えて良い。次に「Cの数がI, Pの数より多い」という条件を考える。$i - 1$項目までのCの数を$\text{cnt}_{i}$とすると、区間$[l, r)$が★ならば$\frac{r - l - (\text{cnt}_{r} - \text{cnt}_{l})}{2}\lt \text{cnt}_{r} - \text{cnt}_{l}$が成り立つ。これを式変形すると$3\text{cnt}_{l} - l\lt 3\text{cnt}_{r} - r$ あらかじめ$3\text{cnt}_{i} - i$を前計算し、座標圧縮しておくことで、各$i$に対して$j < i\land 3\text{cnt}_{j} - j\lt 3\text{cnt}_{i} - i$を満たす$\text{dp}_{j}$の総和をFenwick Treeで計算できるようになる。以上を組み合わせると$\Theta(|S|\log |S|)$で解くことができた。私にとっては辛い処理ゲーに帰着する。 [提出](https://onlinejudge.u-aizu.ac.jp/solutions/problem/1437/review/9808700/zawakasu/C++17) なんとかノーペナで通せた。メモリとかも心配だったが結構余裕。本番でもこういう問題は自分担当なので、頑張っていきたい。 ### F: AOJ2568 Everlasting -One- https://onlinejudge.u-aizu.ac.jp/problems/2568 $N = 1$ならば2、$M = 0$ならば$2^{N}$が解である。そうでないとき、$a_i, b_i$を無向辺とみたてたグラフにおいて連結成分数を$C$とすると、$2^C + 1$が答えになる。 - 各連結成分についてstateが同じならば、どの他のcharacterに移動することもできない - これ以外のcharacterは相互に移動可能。とエスパー.... [提出](https://onlinejudge.u-aizu.ac.jp/solutions/problem/2568/review/9808756/zawakasu/C++17) 時間が無くて適当考察を投げたが、ACが取れた... ## upsolve ### AOJ1395: What Goes Up Must Come Down (解説AC) https://onlinejudge.u-aizu.ac.jp/problems/1395 一番小さい要素は最左か最右に移動させる必要がある。移動距離が小さい方に移動させて良い。後はサイズ$N - 1$の問題に帰着する [提出](https://onlinejudge.u-aizu.ac.jp/solutions/problem/1395/review/9812093/zawakasu/C++17) $[l, m)$を昇順ソート、$[m, r)$を降順ソートすれば良いので、$m$を全探索という嘘から全然抜け出せなかった。 ### 3rd UC Stage 14 - L A Game on Tree https://contest.ucup.ac/contest/1817/problem/9530 重心分解で、ある頂点 $v$ をまたぐパスのみを考えることにする。頂点$v$を根としたときの各頂点の深さ・部分木のサイズ・部分木のサイズの2乗・その頂点で枝分かれするような２つのパスの選び方の通り数を前計算する。これらのガッチャンコで欲しい物が求まる。途中で「頂点$r$を根としたときの頂点$v$の部分木の頂点数は？」というクエリを答える必要が生じた。有名な方法が何かしらありそうだが、再発明してしまったので書き残しておく。 1. はじめに、適当な頂点($r'$とする)で木を根付けしてオイラーツアーと、部分木のサイズの計算をしておく 2. 各頂点の隣接リストをオイラーツアーの訪問順が早い順番にソートしておく。頂点$v$の訪問時間を$L_{v}$、退出時間を$R_{v}$とする 3. $r = v$ならば、自明に$N$である。 4. そうでなくて、$L_{r} \lt L_{v}$または$R_{v}\lt R_{r}$ならば、答えは$r'$を根としたときの$v$の部分木の頂点数に一致する -> 既に計算済 5. そうでなければ、$r$は$r'$を根とみたとき$v$の部分木内に存在する。$v$の子であって$r$の先祖であるような頂点を$x$とすると、$N - \text{size}(x)$が解になる。$x$は隣接リストを$L_{v}$をキーに二分探索すると計算できる前計算$\Theta(N)$、クエリ毎$\Theta(\log N)$でできた。定数倍高速化バトルをすると、ACできた。 [定数倍高速化バトルの知見](https://x.com/zawakasu/status/1852316659186622905)