---
# System prepended metadata

title: 2024/10/28~11/3
tags: [精進報告]

---

# 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)

