# TUATPC2024Summer (Algorithm) 解説

## 前書き

### 難易度の意図について

- A 問題と B 問題 (難易度 Milk) は「学部1年生のプログラミング初心者でも解ける問題にしろ」という前部長の要望に応えた問題になっています。ちなみにこの要望が出た理由は[去年の夏合宿コンテストの 1 問目](https://mofecoder.com/contests/mccpc2023/tasks/mccpc2023_a)が難しすぎたから(要するに自分のせい)です。
- C 問題から F 問題までは競プロをやっていなくても楽しめそうな問題にしました。特に外部参加者のほとんどは競プロを普段からやっている方で、おそらくほとんどの人は G 問題の方が簡単と感じたと思いますが、グラフ関連の話は競プロをやっていないとあまり触れる機会ないしな…と思ってこの位置に置きました。

---

## A - MCC (Milk)

Tester : kichi2004

### 問題概要

$2$ つの英大文字 $A, B$ が与えられるので、同じ文字なら `MCC` と、違う文字なら$1$ 文字の $A$ と $2$ 文字の $B$ をこの順に繋げた文字列を出力しろ。

### 解説

> A 問題と B 問題 (難易度 Milk) は「学部1年生のプログラミング初心者でも解ける問題にしろ」という前部長の要望に応えた問題になっています。

この問題は単純な `if` 文を用いることで解くことができます。

#include <iostream>
using namespace std;

int main(){
    char A, B; cin >> A >> B;
    
    if(A == B) cout << "MCC" << endl;
    else cout << A << B << B << endl;
}

### 統計

- Accpted / Attempt : xx / xx
- First Accepted (Overall) : olphe / 0:37
- First Accepted (MCC) : (ngng_marunage) / 2:11

### 余談

前回のコンテストの原案で出した問題を使いたかったんですが、Writer 陣(1人)が僕以外 Contestant だったので使えず新たに生やしました。

---

## B - Worship (Milk)

Tester : kichi2004

### 問題概要

非負整数 $A, B, C$ が与えられるので、

- $A$ 行 `bow`
- $B$ 行 `clap`
- $C$ 行 `bow`

をこの順に出力しろ。

### 解説

> A 問題と B 問題 (難易度 Milk) は「学部1年生のプログラミング初心者でも解ける問題にしろ」という前部長の要望に応えた問題になっています。

この問題は単純な `for` 文を用いることで解くことができます。

#include <iostream>
using namespace std;

int main(){
    int A, B, C; cin >> A >> B >> C;
    
    for(int i = 0; i < A; ++i) cout << "bow" << endl;
    for(int i = 0; i < B; ++i) cout << "clap" << endl;
    for(int i = 0; i < C; ++i) cout << "bow" << endl;
}

### 統計

- Accpted / Attempt : xx / xx
- First Accepted (Overall) : (a01sa01to) / 1:03
- First Accepted (MCC) : (揚げ豆腐) / 1:22

### 余談

いつかのソロセットで使おうとしていた問題を起用しました。代わりの問題生やさないとですね。

---

## C - Multiplication Table (Assam)

Tester : kichi2004

### 問題概要

$N, M$ が与えられるので、 $N \times N$ の九九の表みたいなものを出力しろ。

下 2 桁だけでいいけど必要なら 0 埋めすること。

### 解説

#### Easy

やるだけです。やりましょう。ちなみに Easy の制約では0埋めをする必要もないです。

#### Hard

下2桁を出力すればよいので、$(M + i - 1) \times (M + j - 1)$ の下2桁が求まればよいです。

これは $(M + i - 1)$ と $(M + j - 1)$ の下2桁同士を掛け算することで求めることができるので、予め $M$ の下2桁だけを取り出しておけばよいです。

巨大な数の入力は、整数型としてでなく文字列型として受け取るとよいです。

0埋めをする必要がありますが、大抵のプログラミング言語は0埋めのフォーマット指定くらいできるはずなので調べましょう。C/C++ならprintf関数を使うのが楽だと思います。

#include <bits/stdc++.h>
using namespace std;

int main(){
    int N; cin >> N;
    string M; cin >> M;

    int m = (M.size() >= 2 ? stoi(M.substr(M.size() - 2)) : stoi(M));
    for(int i = 0; i < N; ++i){
        for(int j = 0; j < N; ++j){
            printf("%02d%c", (m + i) * (m + j) % 100, j == N - 1 ? '\n' : ' ');
        }
    }
}

### 統計

- Accpted / Attempt : xx / xx
- First Accepted (Overall) : (t9unkubj) / 3:48
- First Accepted (MCC) : (ngng_marunage) / 9:12

### 余談

そういえば0埋めさせる競プロの問題ってないな～って思ったので出しました。

プログラミングの講義とかで0埋めは出てくる記憶があったので、未経験者でも解けるだろ！と思って出しました。検索 OK だし。

---

## D - Addition and Division (Assam)

Tester : Nerve

### 問題概要

整数 $A = N^M+K$ がある。$A$ が $N$ の倍数なら $N$ で割り、そうでないなら $N-1$ を足すという操作を $A$ が $N$ 未満になるまで行うとき、操作は何回行われるか。

$T$ ケース与えられるのでそれぞれについて求めろ。

### 解説

#### Easy

実際に $N ^ M + K$ を予め計算したうえで、愚直にシミュレーションしましょう。

操作回数は $\textrm{O}(KM)$ 回（後で示します）で、追加制約より $M \le \log_N 10^9$ から雑に見積もっても操作回数は $500$ 回以下となります。

$T \le 100$ より、最大で $50000$ 回程度しか操作されないため、十分高速に動作します。

#### Hard

シミュレーションの過程をよく観察すると、$K$ 回加算して除算する、という一連の操作を $M$ 回繰り返していることが分かると思います。

実際、$0 \le K \lt N$ より $N^M+K \equiv K \pmod N$ で、$K$ 回加算操作を行うと $K + K (N - 1) \equiv K + NK - K \equiv NK \equiv K \pmod N$ となります。

よってこの一連の操作を**セット**と呼ぶことにすると、1セット操作をすると $N^M+K$ は $N^{M-1}+K$ に変化することが分かります。

従って $M$ セット操作をすると $N^{M-M}+K=1+K$ に変化します。

ここで、$K = N - 1$ のとき $1+K = N$ なのでこのときに限り追加で1回除算操作を行います。

以上より、答えは $\displaystyle M(K+1) + \left\lfloor \frac{K + 1}{N} \right\rfloor$ です。これは $\textrm{O}(1)$ で計算できるため、全体では $\textrm{O}(T)$ で答えることができます。オーバーフローには注意しましょう。

#include <bits/stdc++.h>
using namespace std;

using ll = long long;

void solve(){
    ll N, M, K; cin >> N >> M >> K;
    
    cout << M * (K + 1) + (K + 1) / N << endl;
}

int main(){
    int T; cin >> T;
    while(T--) solve();
}

### 統計

- Accpted / Attempt : xx / xx
- First Accepted (Overall) : (potato167) / 8:59
- First Accepted (MCC) : (北島組) / 59:12

### 余談

この問題で $N = 4, M = 1 \ (A = 4^9 + 1)$ としたときの答えを求めさせる算数の問題があって、それを一般化させました。

$K = N - 1$ のときがコーナーケースで面白かったので、誰かしら引っかかってくれたらいいな～と思って敢えてサンプルをめちゃくちゃ弱くしました。ちなみに Writer も引っかかりました。

---

## E - MCC Sequence (Calculate Version) (Benihuki)

Tester : totori

### 問題概要

長さ $n$ の数列 $a = (a_1, \dots, a_n)$ に対し、$f(a)$ を次の条件をすべて満たす整数 $(i, j, k)$ の組の個数と定義する。

- $1 \le i < j < k \le n$
- $a_i \ne a_j$
- $a_i \ne a_k$
- $a_j = a_k$

長さ $N$ の数列 $A = (A_1, \dots, A_N)$ に対して $f(A)$ を求めろ。

### 解説

#### Easy

すべての $(i, j, k)$ の組み合わせを試す全探索をします。

$N \le 100$ より、$\textrm{O}(N^3)$ が間に合います。

[C++ による実装](https://mofecoder.com/contests/tuatpc2024summer_a/submissions/12443)
[Python(PyPy3) による実装](https://mofecoder.com/contests/tuatpc2024summer_a/submissions/12442)

#### Normal

$(i, j, k)$ の組について、$k$ を固定して考えてみましょう。

このとき、$(i, j)$ に対して $(A_i, A_j)$ が取りうる値は $N^2$ 通りあります。$N \le 1000$ のとき、このすべてを列挙することが可能です。

これを踏まえて、行列 $C_{i, j}$ を $A_x = i$ かつ $A_y = j$ を満たす $(x, y)\ (x < y)$ の組の個数と定義して、これを更新しながら答えを求めればよいです。

計算量は $\textrm{O}(N^2)$ となります。

[C++ による実装](https://mofecoder.com/contests/tuatpc2024summer_a/submissions/12444)
[Python(PyPy3) による実装](https://mofecoder.com/contests/tuatpc2024summer_a/submissions/12445)

#### Hard

$i$ を固定したときに条件を満たす $j, k$ の個数を考えます。
$i < j < k \le N, A_j = A_k$ より、$i$ 以降で $2$ 回以上出現する数字が対象になります。

例えば $A = (1, 2, 2, 4, 3, 2, 3)$ について $i = 1$ と固定したとき、$A_2$ から $A_7$ の間に $2$ 回以上出現する数字は $2, 3$ の $2$ 種類です。(それぞれ3回、2回出現しています)
そして実際に条件を満たす $(j, k)$ の組の数は各数字について出現回数を $x$ としたとき、$x$ 個の中から $2$ 個選ぶ場合の数と同じです。

これを踏まえて、各数字について $i < m \le N$ の間に何回出現するかを管理する配列とその総和を管理する変数を用意し、$i = N, N - 1, \dots, 1$ の順に配列と総和を更新しながら答えを計算することができます。

計算量は $\textrm{O}(N)$ となり、十分高速です。

[C++ による実装](https://mofecoder.com/contests/tuatpc2024summer_a/submissions/12446)
[Python(PyPy3) による実装](https://mofecoder.com/contests/tuatpc2024summer_a/submissions/12447)

### 統計

- Accpted / Attempt : xx / xx
- First Accepted (Overall) : (pitP) / 7:37
- First Accepted (MCC) : (ngng_marunage) / 29:52

### 余談

「TUAT String」に対抗して作りました。

---

## F - MCC Sequence (Construct Version) (Benihuki)

Tester : totori

### 問題概要

長さ $n$ の数列 $a = (a_1, \dots, a_n)$ に対し、$f(a)$ を次の条件をすべて満たす整数 $(i, j, k)$ の組の個数と定義する。

- $1 \le i < j < k \le n$
- $a_i \ne a_j$
- $a_i \ne a_k$
- $a_j = a_k$

長さ $200000$ 以下の数列 $A$ であって、$f(A) = M$ を満たすものを $1$ つ求めよ。

### 解説

#### Easy

想定では手元でいくつかの $M$ について構築してもらい、それをソースコードに埋め込んで解答してもらう部分点でした。また、手元で構築する途中で一般の構築方法を思いついてくれるかなと思って敢えて $M$ は多めに用意し、手でやるにはそこそこ大きな値を用いました。

#### Hard

実は、次のような方法で AC することができます。

- $i = 1, \dots, 190000$ に対して、$X_i = \frac{i(i - 1)}{2}$ とする。また、$m = M$ とする。
- $1$ を $190000$ 個並べた数列を $B$ とする。
- $i = 2, \dots, 10001$ の順に、次の処理を行う。
- $X_j \le m$ を満たす最大の $j\ (1 \le j \le 190000)$ を見つける。
- $B$ について、右から $j$ 個目の $1$ の左に $i$ を挿入する。
- $m \leftarrow m - X_j$ とする。
- $B$ は $f(B) = M$ を満たす長さ $200000$ の数列で条件を満たす。従って $B$ は条件を満たす $A$ のひとつである。

例えば、$M = 35$ のときの構築の様子を見てみます。

- $X_i = (0, 1, 3, 6, 10, 15, 21, 28, 36, \dots)$
- $X_j \le m = 35$ を満たす最大の $j$ は $j = 8$ より、$B$ の右から $8$ 個目の $1$ の左に $2$ を挿入します。
- $B$ は $(\dots, 1, 2, 1, 1, 1, 1, 1, 1, 1, 1)$ となります。
- $X_8 = 28$ より、$m = 35 - 28 = 7$ となります。
- $X_j \le m = 7$ を満たす最大の $j$ は $j = 4$ より、$B$ の右から $4$ 個目の $1$ の左に $3$ を挿入します。
- $B$ は $(\dots, 1, 2, 1, 1, 1, 1, 3, 1, 1, 1, 1)$ となります。
- $X_4 = 6$ より、$m = 7 - 6 = 1$ となります。
- $X_j \le m = 1$ を満たす最大の $j$ は $j = 2$ より、$B$ の右から $2$ 個目の $1$ の左に $4$ を挿入します。
- $B$ は $(\dots, 1, 2, 1, 1, 1, 1, 3, 1, 1, 4, 1, 1)$ となります。
- $X_2 = 1$ より、$m = 1 - 1 = 0$ となります。
- これ以降の $i = 5, \dots, 10001$ はすべて $B$ の最も右の $1$ の左に順に挿入されます。最終的に $B = (1, \dots, 1, 2, 1, 1, 1, 1, 3, 1, 1, 4, 1, 5, 6, \dots, 10000, 10001, 1)$ となります。

以下ではこの構築例の正当性を説明します。

E 問題の解説より、条件を満たす $(i, j, k)$ の組の $i$ に注目したとき、$j, k$ の選び方は $i$ 以降の同じ数字の中から $2$ つを選ぶ選び方に等しいです。そしてある数字が $n$ 個あるときに、その中から $2$ つの数字を選ぶ選び方は $X_n$ に等しいです。

$X_n$ は**三角数**と呼ばれる数です。ここで、三角数に関する次の定理があります。

> 任意の自然数は、$3$ つ以下の三角数の和で表すことができる。

この定理の主張を少し弱め、$0$ も三角数と見做すと次のことが言えます。

> 任意の自然数は、いくつかの三角数の和で表すことができる。

さて、示した構築例では $M$ を三角数の大きなものから貪欲に分割していました。実はこの方法では任意の自然数を $3$ 個以下の三角数に分割できるとは限らない(例 : $20$ をこの方法で分割すると $20 = 15 + 3 + 1 + 1$ となりますが、$20 = 10 + 10$ と表せます)のですが、この構築例では $M \le X_{190000}$ であれば十分少ない個数に分割できることが知られています。

三角数を貪欲に選択して分割するとき、$n$ 個の三角数を要求する最小の数字は [OEIS - A006893](https://oeis.org/A006893) に示されています。これによると、$7$ 個を要求する最小の数字は $359{,}026{,}205$ であることが、$8$ 個を要求する最小の数字が $64{,}449{,}908{,}476{,}890{,}320 > X_{190000}$ であることが分かるので、$M \le X_{190000}$ の範囲では貪欲に分割しても高々 $7$ 個の三角数に分割できることが言えます。

$M > X_{190000}$ のとき、貪欲法で適切な個数 $X_{190000}$ を選択することで $M \le X_{190000}$ に帰着させることができます。$X_{190000} \approx 1.8 \times 10^{10}$ より、$M \le X_{190000}$ に帰着させるために必要な $X_{190000}$ の個数は、$\left\lfloor \frac{10^{14}}{1.8 \times 10^{10}} \right\rfloor \approx 5555$ より雑に見積もっても $6000$ 個もあれば十分です。

以上より、この構築法で $M \le 10^{14}$ を構築する際に必要になる三角数の個数は高々 $6000 + 7 = 6007$ 個となります。この構築法では $10000$ 回($0$ を含む)三角数に分割するので、この方法で本問題を解くことができます。

余談ですが、恐らくこの方法で分割するときに必要になる三角数の個数の最大値は $M = 99{,}996{,}832{,}726{,}205$ のときで、$5547$ 個になると思います(証明はしていません)。

### 統計

- Accpted / Attempt : xx / xx
- First Accepted (Overall) : (Loosened Chord) / 18:47
- First Accepted (MCC) : (アイス食べたい) / 1:55:59

### 余談

一見こんな方法で良いのか？な構築法で構築可能なのが個人的に面白かったので出しました。
「任意の自然数を貪欲に三角数に分割したとき、$n$ 個の三角数を要求する最小の数字からなる数列」が OEIS に存在していたことに驚きました。なんであるんですか？

Easy の部分点は MOFE の最近のアップデートで追加された動的採点機能のおかげでやりたいことができて良かったな～と思います　kichi さんありがとう

---

## G - Let's Meet by the Promised Time (Ceylon)

Tester : qLethon

### 問題概要

$N$ 頂点 $M$ 辺の重み付き単純連結無向グラフ $G$ が与えられる。頂点 $1$ と頂点 $N$ のどちらからでも時間 $K$ 以内に移動できる頂点数を答えるという質問に $Q$ 回答えよ。

### 解説

#### Easy

すべての路線が駅 $2$ に接続しているので、任意の $2$ 駅間は高々 $2$ つの路線を使用することで移動が可能です。

すなわち、Alice と Bob がそれぞれ駅 $1$、駅 $N$ から時刻 $K$ までにどの駅に行けるかは駅ごとに $\textrm{O}(1)$ で計算できるため、$\textrm{O}(N)$ で答えを求めることができます。

$Q$ 個のクエリに対してこれを行うと $\textrm{O}(NQ)$ となります。$N \le 100, Q \le 100$ より十分高速に解くことができます。

#### Normal

与えられる位置関係がいわゆるグラフ理論における木になります。木における $2$ 頂点間の距離は、片方の頂点から深さ優先探索や幅優先探索をすることで求めることができます。

あとは Easy と同様に答えを求めればよいです。よって $\textrm{O}(NQ)$ で解くことができます。

#### Hard

与えられる位置関係がいわゆる一般の無向グラフになります。一般の無向グラフでは、$2$ 頂点間の経路は $1$ 通りとは限りませんが、本問においては明らかに待ち合わせ場所にしたい駅に最速で到着することが最善なので、最短経路のみを考慮すればよいです。無向グラフにおける単一始点最短経路問題は Dijkstra 法で $\textrm{O}(M \log N)$ で解くことができます。

Alice が駅 $1$ から駅 $i$ に移動するために必要な最小の時間を $A_i$、Bob が駅 $N$ から駅 $i$ に移動するために必要な最小の時間を $B_i$ とします。このとき、$2$ 人が駅 $i$ で会うことができる最速の時間は $\max(A_i, B_i)$ です。以降、$C_i = \max(A_i, B_i)$ とします。

よって、本問題は各 $K_i$ について $C_j \le K_i$ を満たす $j$ の個数を数える問題に帰着できます。今回は $C_j$ の値はクエリ全体で不変なので、予めすべての $C_j$ を求めソートしておくことで、クエリ毎に二分探索で $\textrm{O}(\log N)$ で求めることができます。

以上より、本問題を $\textrm{O}((M + Q) \log N)$ で解くことができます。

### 統計

- Accpted / Attempt : xx / xx
- First Accepted (Overall) : (akua) / 7:12
- First Accepted (MCC) : (アイス食べたい) / 8:48

### 余談

たまにはど典型な問題を出したっていいだろと思って出しました。競プロに馴染みのある人にとっては F 問題より簡単に感じる人も多そうです。

ABC で出たら茶 diff くらいになる気もします。

---

## H - Second Shortest Path in Pseudotree (Ceylon)

Tester : qLethon

### 問題概要

$N$ 頂点 $N$ 辺の無向グラフが与えられる。

$2$ 頂点 $A, B$ 間の第 $2$ 最短パス長を求めろ。存在しない場合はその旨を報告しろ。
$Q$ クエリそれぞれについて求めろ。

### 解説

#### Easy

実は Easy では常に第 $2$ 最短パスが存在することが制約から保証されています。

Easy では入力例 1 のように1本道なグラフに1つ、頂点 $N$ を端点とする辺を加えたようなグラフが与えられます。この辺のもう片方の端点の頂点を仮に頂点 $M$ としておきましょう。(入力例 1 では $M = 2$)

$A$ は制約より $N$ で固定なので、$B$ と $M$ の大小関係により答えは次のようになります。

1. $B \le M$ のとき
- 第 $2$ 最短パスは常に頂点 $N \rightarrow$ 頂点 $N - 1 \rightarrow \dots \rightarrow$ 頂点 $B$ となります。よって答えは $N - B$ です。
1. $B > M$ のとき
- 第 $2$ 最短パスは頂点 $N \rightarrow$ 頂点 $N - 1 \rightarrow \dots \rightarrow$ 頂点 $B$ か頂点 $N \rightarrow$ 頂点 $M \rightarrow$ 頂点 $M + 1 \dots \rightarrow$ 頂点 $B$ のどちらかです。前者のパスの長さは $N - B$ で、後者のパスの長さは $B - M + 1$ です。よって小さい方を出力すればよいです。

以上より軽い場合分けで $\textrm{O}(1)$ で解くことができます。

#### Normal

実は Easy より考えることが少ないかもしれません。

$Q = 1$ より、クエリに $1$ 回答えられれば良いです。そのため、次の単純な解法で正解できます。

1. パスの長さを保持する空の配列 $P$ を用意する。
1. 頂点 $A$ より、現在のパスの長さを保持しながら深さ優先探索を行う。
- 探索途中で頂点 $B$ に到達したら、その長さを $P$ の末尾に加える。
1. $|P| \ge 2$ ならば $P$ の $2$ 番目に小さい値を出力し、$|P| < 2$ ならば `-1` を出力する。

計算量は $\textrm{O}(N)$ です。

#### Hard

与えられるグラフは高々 $1$ つの閉路を持ちます。また、閉路に含まれない頂点集合は $1$ つ以上の列を成しています。便宜上各列を枝、枝が閉路と接続している閉路上の頂点を節と呼ぶことにします。

例えば、入力例 3 のグラフでは閉路は頂点 $(1, 2, 3, 4, 5, 6)$ 、枝は頂点 $(7, 8)$ と頂点 $(9)$ の 2 つで、それぞれの節は頂点 $4$ と頂点 $6$ となります。

結論から述べると、次のいずれかを満たすとき、第 $2$ 最短パスが存在しません。

1. $A$ と $B$ が同じ枝に属する頂点である場合
2. 片方の頂点が枝に属する頂点で、もう片方の頂点がその枝の節である場合
3. 両方の頂点がそれぞれ異なる枝に属する頂点で、それらの枝が共通の節を持つ場合

逆に、これらのどの場合にも当てはまらない場合、第 $2$ 最短パスが存在します。
具体的な計算方法を次に述べます。

1. 両方が閉路上の頂点である場合
- 閉路を構成する頂点集合を、適当な頂点を始点として閉路を構成する順になるように列に変換します。この列を $C$ とし、その要素数を $|C|$ と表記します。また、閉路上の頂点 $v$ が $C$ の先頭から何番目に位置するかを $C(v)$ と表記します。例えば $C = (2, 7, 1, 8)$ のとき、$|C| = 4, C(2) = 1, C(1) = 3$ です。
- 頂点 $A$ から頂点 $B$ へは閉路上を時計回りに回るか反時計回りに回るかの2通りの方法があることは明白です。2通りの長さ $d_1, d_2$ はそれぞれ $d_1 = |C(A) - C(B)|$ と $d_2 = |C| - |C(A) - C(B)|$ で表されるため、$\max (d_1, d_2)$ が答えです。
3. 片方の頂点が枝に属する頂点で、もう片方の頂点がその枝の節でない閉路上の頂点である場合
- $A$ と $B$ を逆にしても答えは変わらないため、$A$ が枝に属する頂点として考えます。
- 頂点 $A$ が属する枝の節を頂点 $A^\prime$ とします。このとき、$A^\prime$ と $B$ 間について1.と同様の問題に帰着できます。
- したがって $A$ と $A^\prime$ の距離を $d_A$ とすると、$d_A + \max (d_1, d_2)$ が答えです。
5. 両方の頂点がそれぞれ異なる枝に属する頂点で、それらの枝が共通の節を持たない場合
- 2.と同様に同様に頂点 $B$ が属する枝の節を頂点 $B^\prime$ とすれば、$A^\prime$ と $B^\prime$ 間について1.と同様の問題に帰着できます。
- したがって $B$ と $B^\prime$ の距離を $d_B$ とすると、$d_A + d_B + \max (d_1, d_2)$ が答えです。

以上を高速に求めるために、次を事前に知っていればよいです。

- 各頂点が閉路に属しているか、属しているなら $C$ において何番目か
- 各頂点が枝に属しているか、属しているならどの枝に属し、節からどれくらい離れているか

これらは予め深さ優先探索などを用いることで $\textrm{O}(N)$ で前計算することができます。
よって、各ケースについて $\textrm{O}(1)$ で答えることができ、全体で $\textrm{O}(N + Q)$ で答えることができます。

### 統計

- Accpted / Attempt : xx / xx
- First Accepted (Overall) : (potato167) / 21:46
- First Accepted (MCC) : (user) / xx:xx

### 余談

本問のグラフ、競技プログラミングを普段から嗜んでいる皆様の中には「なもりグラフ」という名称で馴染みがある方もいらっしゃると思うのですが、"preudotree" という名称で書いたのは「なもりグラフって書くの嫌だな～」という Writer の思想です。

問題名をどうしようか悩んでいるときにちょうど[2020年のchokudaiさんのツイート](https://x.com/chokudai/status/1266980205123350528?lang=ja)を見つけて "preudotree" という名称を知りました。ハイフンが無いのは Wikipedia 準拠です。

---

## I - Passing Trash (Darjeeling)

Tester : kichi2004

### 問題概要

人 $1$ から人 $N$ の $N$ 人に $M$ 個のお菓子が入った箱を回す。
人 $i$ は箱を受け取ると、$P_i$ 個のお菓子を取る。このとき、箱に $P_i$ 個以下のお菓子しかなければ、お菓子をすべて取り、箱を持ち帰る。そうでなければ、人 $Q_i$ に箱を渡す。
最初に誰に渡すかによって、箱を持ち帰る人が変わる。箱を持ち帰る可能性のある人の番号をすべて挙げよ。

### 解説

#### Easy

愚直にシミュレーションを行うことで、$\textrm{O}(NM)$ で解くことができます。

#### Normal

この部員たちの一連の行動は、部員を頂点、お菓子をとる部員から渡す相手への、とるお菓子の数を重みとした有向辺と捉えると、Functional Graph になります。

Functional Graph において、ある頂点から $k$ 回辺を辿ったときの重みの総和および最終的に到達する頂点はダブリングを用いて $\textrm{O}(\log M)$ で求めることができます。

ある部員に箱を初めに渡した後、その箱を持ち帰る部員は Functional Graph 上の通った辺の重みの総和が $M$ 以上になる最初の頂点に対応する部員となります。お菓子は必ず毎回の操作で $1$ 個以上減少するので、このような部員は二分探索を用いて $\textrm{O}(\log M)$ で求めることができます。毎回ダブリングで総和を求めることで $\textrm{O}((\log M)^2)$ で求められます。

以上より、全体の計算量は $\textrm{O}(N (\log M)^2)$ です。

#### Hard

実は、ダブリングの結果を用いた本問のような二分探索は $\textrm{O}(\log M)$ で実行可能であることが知られています。

具体的には、部員 $i$ に箱を渡したとき、$m = 0, r = i$ として次の処理を $k = \lceil \log_2M \rceil, \dots, 1, 0$ の順に行えばよいです。ここで、$c_{i, j}$ は部員 $i$ から $2^j$ 回箱が回されるときに減るお菓子の数、$n_{i, j}$ は部員 $i$ から $2^j$ 回箱が回されたあとに箱を持っている部員です。

- $m + c{r, k} \le M$ なら $m \leftarrow m + c_{r, k}, r \leftarrow n_{r, k}$ とする。

これにより、全体の計算量は $\textrm{O}(N \log M)$ となり、問題を解くことができます。

### 統計

- Accpted / Attempt : xx / xx
- First Accepted (Overall) : (potato167) / 27:58
- First Accepted (MCC) : (アイス食べたい) / 2:20:43

### 余談

Functional Graph のこういうタイプの問題絶対どこかであるだろって思ったらあまりなさそうだったので出しました。ダブリングの二分探索が対数時間でできるのすげ～って思っていたんですが、ダブリングで LCA を求めるときにも使用されているらしいです。

---

## J - Agricultural Expression (Darjeeling)

Tester : qLethon

### 問題概要

※長いので省略

### 解説

#### データセット 1

連結算は `+` 記号を文字列から取り除くことと同じなので、文字列を読んでいき `+` 以外はそのまま出力するようなコードを書けば通ります。

#### データセット 2

データセット 2 は単純な成長算なので、1 文字目は必ず `G` です。よって 1 文字目が `G` ならば `)` が来るまで数字を 1 ずつ増やして (`9` に注意) 出力すればよいです。

#### データセット 3

データセット 3 は単純な収穫算なので、データセット 2 と同様の要領で 1 文字目が `H` ならば収穫算の処理（数字の輪を取る）を行うようにすればよいです。

#### データセット 4・5

データセット 1 ~ 3 のコードを上手く組み合わせることでデータセット 4 に対するコードを実装できます。さらに、これを今見ている文字が文字列の末尾に到達するまで連結算と成長算または収穫算を繰り返すように処理をすることでデータセット 5 に対するコードを実装できます。

#### データセット 6

成長算／収穫算の中に単純な演算が入っているタイプです。このデータセットでは入れ子が 1 段階しかないので、初めに 1, 2 文字目を読んだ後、データセット 4・5 で用いたソースコードを流用するなどすれば実装できます。

#### データセット 7

データセット 6 で実装したコードを、データセット 4 と同じ要領で連結算で繋げてあげればよいです。

#### データセット 8

データセット 7 までのコードを再利用して解くことも大変ですが可能だと思います。（再帰関数に直す部分が大変）

いわゆる構文解析の問題ですが、実装上で注意する点があまり多くない比較的シンプルな構文解析の問題だと思います。ただ、PyPyなど一部の言語では文字列を都度コピーすると TLE する可能性があります。

### 統計

- Accpted / Attempt : xx / xx
- First Accepted (Overall) : (potato167) / 33:20
- First Accepted (MCC) : (ngng_marunage) / 58:45

### 余談

最初 `<number>` の長さを制限していなかったのですが、そうすると `G(G(G(...)))` みたいな形式のときに高速にできる方法が浮かばなくてこの制約を追加しました。

**(2024/9/27 0:50)** 追記開始

本問題の Writer 解・および問題設定に不備があることを指摘いただきました。

また、Writer 解よりも計算量の良い解法を Tester の shinchan さんが実装していたため、ここに掲載させていただきます。

https://mofecoder.com/contests/tuatpc2024summer_a/submissions/12217

**(2024/9/27 0:50)** 追記終了

---

## K - TUAT String 4 (Darjeeling)

Tester : Nerve

### 問題概要

長さ $N$ の数列 $C = (C_1, C_2, \dots, C_N)$ が与えられる。次のすべての条件を満たす整数 $(i,j,k,l)$ の組の個数を $998244353$ で割った余りを求めろ。

- $1 \le i < j < k < l \le N$
- $C_i = C_l$
- $C_i \ne C_j$
- $C_i \ne C_k$
- $C_j \ne C_k$

### 解説

#### Easy

制約が $N \le 50$ と小さいので、$(i,j,k,l)$ の組を全探索して答えを求めることができます。

計算量は $\textrm{O}(N^4)$ です。

#### Normal

次のような動的計画法を考えます。

$dp_{i,j,k,l} := S$ の $i$ 文字目までに含まれる、$1$ 文字目が $j$ で $2$ 文字目が $k$ であるような長さ $l$ の文字列の個数(ただし、$l = 0$ のとき $j, k$ は任意、$l = 1$ のとき $k$ は任意)

このとき、答えは $\displaystyle \sum_{1 \le j \le M}\sum_{1 \le k \le M, j \ne k} dp_{N,j, k, 4}$ です。

この動的計画法を適切に遷移させることで、$\textrm{O}(NM^2)$ で答えを求めることができます。

#### Hard

実は E 問題がかなりヒントになっています。E 問題を解いた人はこの問題も似たような発想で解けたかもしれません。

$(i, j, k, l)$ の $k$ を固定して考えます。このときの $(i, j)$ に対して $(C_i, C_j)$ が取りうる組み合わせは $\textrm{O}(M^2)$ 通りあるのですべて列挙することが可能です。この列挙は E 問題の Normal と同様の要領で数えることで $\textrm{O}(NM)$ で列挙することが可能です。$A_{i,j}$ を $C_x = i, C_y = j$ を満たす $(x, y)\ (x < y)$ の組み合わせの個数とします。

次に $l$ ですが、$C_l$ に対して $\sum_{1 \le j \le M, j \ne k}A_{C_l, j}$ が条件を満たす組み合わせになります。従って $k$ を固定したときの答えは $\sum_{k < l \le N} \sum_{1 \le j \le M, j \ne k}A_{C_l, j}$ となります。内側のシグマについては E 問題の Hard と同様の要領で、予め $\sum_{1 \le j \le M}A_{C_l, j}$ を求めておくことで $A_{C_l, k}$ を引けば良いです。また外側のシグマについても、右側から $C_i$ の出現回数を数えながら計算すれば $\textrm{O}(M)$ に計算量を落とすことができます。

結局、初めに $A_{i,j}$ を計算した後、右側から各 $C_i$ の出現回数を記録しつつ数えることで $\textrm{O}((N + M)M)$ で求めることができます。

### 統計

- Accpted / Attempt : xx / xx
- First Accepted (Overall) : (akua) / 40:05
- First Accepted (MCC) : (user) / xx:xx

### 余談

タイトルにあるように「TUAT String」という名前は過去 3 回([AOJ - 3236 (ACPC2021 Day 1 - H : TUAT String)](https://onlinejudge.u-aizu.ac.jp/challenges/sources/VPC/TUATPC/3236?year=2021), [AOJ - 3345 (HUPC2023 Day 2 - I : TUAT String 2)](https://onlinejudge.u-aizu.ac.jp/challenges/sources/VPC/TUATPC/3345?year=2023), [東京農工大学MCCプログラミングコンテスト2023 - E : TUAT String 3](https://mofecoder.com/contests/mccpc2023/tasks/mccpc2023_e))登場しているのですが、単純な数え上げ問題がなかったので作っておきました。初代と 2 代目みたいに一捻りある問題が作れるようになりたいですね。

ところで「String じゃねえじゃん！」というツッコミが飛んできそうなので言い訳をしておくと、最初は $\textrm{O}(NM^2)$ 解法に気付いておらず、別の解法($\textrm{O}(NM)$ だが定数倍が重い)を用意していて、$N \le 100000, S$ は英小文字からなる文字列という制約で出していたのですが、Tester の Nerve さんに DP で破壊されたのでこのような制約に変わりました。

<details>
<summary>
おまけ : 最初用意していた解法
</summary>
<img src="https://hackmd.io/_uploads/Sy3CMpciR.jpg">
</details>

---

## L - Emotional View (Earlgray)

Tester : Nerve

### 問題概要

二次元平面上に $N$ 個の円が与えられる。原点からちゃんと見える円を列挙せよ。

### 解説

※ Easy と Normal については後で書きます。

#### Hard

まず、エモスポット $i$ に対応する円の原点を通る接線と、その接点を求めましょう。原点と接点を結ぶ線分の長さを $d_i$ とすると、三平方の定理を用いることで $d_i = \sqrt{x_i^2 + y_i^2 - r_i^2}$ と求められます。これと $x_i, y_i, r_i$ の値を用いて、余弦定理などを用いることで接点の座標が $\displaystyle P_i = \left( \frac{d_i}{x_i^2+y_i^2} (d_ix_i \pm r_iy_i), \frac{d_i}{x_i^2+y_i^2} (d_iy_i \mp r_ix_i) \right)$ と求められます。接点の座標を用いることで、接線の偏角を求めることができます。接線の偏角を $\alpha_i, \beta_i \ (-\pi \le \alpha_i < \beta_i < \pi)$ とします。

ある $2$ つのエモスポット $i, j\ (i \ne j)$ の位置関係について考えましょう。エモスポット $j$ がエモスポット $i$ を覆い隠している状況について考えます。本問題の定義では、このような状況であるとき、原点を中心、半径を $d_i$、弧の両端点を $P_i$ とする扇形 $S_i$ とエモスポット $j$ に対応する円が正の共通面積を持つことを指します。エモスポット同士が正の共通面積を持たないことから、次のように言い換えることができます。

- エモスポット $j$ がエモスポット $i$ を覆い隠しているとき、開区間 $(\alpha_j, \beta_j)$ と開区間 $(\alpha_i, \beta_i)$ の共通部分が空でなく、また $d_j < d_i$ が成り立つ。

逆に、あるエモスポット $i$ に対してこの $2$ つの条件を満たす $j\ (i \ne j)$ が存在するとき、エモスポット $i$ はエモスポット $j$ に覆い隠されていると言えます。

以上を踏まえると、エモスポットを $d_i$ の短い順に見えるかどうかの判定を行えばよいことが分かります。判定パートは、偏角の区間を `set` などのデータ構造で持つ（いわゆる区間を `set` で持つテク）か、遅延セグメント木などを用いることで重複しているかを $\textrm{O}(\log N)$ で判定することができます。よって、この問題を $\textrm{O}(N \log N)$ で解くことができました。

> なお、この問題では無理数が接点の座標に含まれる場合があります。そのため、誤差を慎重に扱う必要があります。Writer 解では `atan2l` で求めた偏角を $10^{12}$ 倍して小数点以下切り捨てした整数として持っています。（つまり、有効数字 $12$ 桁で判定しています）これは $x,y,r$ の値を動かしたときに偏角の変化量が $10^{-10}$ 以上であることを踏まえて設定していますが、この処理方法の**正当性の証明はできていません**。ただし、Tester による他の偏角ソートの方法と比較して答えが一致したこと、さらに多倍長浮動小数型を用いて有効数字 $90$ 桁で比較した場合とのコードを、ランダムテスト $150$ ケースで検証してすべてで答えが一致したことから上手くいっているだろうとして出題しました。（反例が見つかったらごめんなさい）

**(2024/9/27 1:10)** 追記開始

上記の議論が不十分であるという指摘をいただきました。

なんとか整数型で比較できないかをコンテスト前まで考えていたのですが思いつかず、このような不十分な根拠のもと出題することになってしまいました。申し訳ありません。

**(2024/9/27 1:10)** 追記終了

---

## M - Subtree Flip Path Count (Earlgray)

Tester : totori

### 問題概要

頂点に重みが付けられた $N$ 頂点の根付き木 $T$ がある。$T$ に含まれる「重みの総和と辺の数が共に偶数であるパス」を数えろ。

さらに、$i = 1, 2, \dots, N$ について、$T$ の頂点 $i$ を根とした部分木に含まれるすべての頂点の重みの偶奇を変更した木を $T_i$ としたとき、$T_i$ に含まれる「重みの総和と辺の数が共に偶数であるパス」を数えろ。

### 解説

※ Easy・Normal・Hard については後で書きますが、Hard は Final で説明している DP を都度 $T_i$ を構築する $\textrm{O}(N^2)$ 想定です。

#### Final

まず、$f(T)$ を求めることを考えましょう。次のような DP を考えます。

- $dp_{i, j, k} :=$ 頂点 $i$ を根とする部分木で、片方の端点が頂点 $i$ であるようなパスのうち、重み $\textrm{mod}\ 2$ が $j$ で、長さ $\textrm{mod}\ 2$ が $k$ であるようなパスの数

このとき、$dp_{i, j, k}$ は頂点 $i$ の子頂点から容易に計算することができます。よってこの DP は $\textrm{O}(N)$ で解くことができます。この DP テーブルを用いることで、「頂点 $i$ を根とする部分木に含まれる、頂点 $i$ を含む重みと長さが偶数であるパス」を数え上げることができます。具体的には、そのようなパスは「頂点 $i$ が端点である」「頂点 $i$ が LCA となる」のいずれかであり、前者は $dp_{i, 0, 0}$、後者は頂点 $i$ が頂点 $c_1, c_2, \dots, c_n$ を子に持つとき、$V_i$ の値に応じてうまく $dp_{c_x, j, k}$ から計算することができます。

したがって、DP をしながら答えを求めていくことで $f(T)$ は $\textrm{O}(N)$ で求めることができます。

それでは $f(T_i)$ を求めましょう。いちいち再計算するのは無駄なので、$f(T)$ との差分を計算することで高速に求めます。

$T$ から $T_i$ に変化したとき、条件を満たさなくなるパスと条件を満たすパスの $2$ つが存在します。それぞれを考えましょう。

まず、条件を満たさなくなるパスは次の $2$ 種類あります。

- パスが頂点 $i$ を根とする部分木に含まれる
- パスの端点が部分木に含まれ、もう片方の端点が部分木に含まれない

前者は DP の値を利用して計算できます。後者は部分木に含まれないパスについて同様の DP を計算することで求めることができます。この DP は最初の DP を計算した後頂点 $1$ から全方位木 DP の要領で計算することができます。

条件を満たすパスについても同様に計算することができます。結局、全方位木 DP の要領ですべての $f(T_i)$ を $\textrm{O}(N)$ で計算することができます。よってこの問題を $\textrm{O}(N)$ で解くことができます。

### 統計

- Accpted / Attempt : xx / xx
- First Accepted (Overall) : (potato167) / 1:12:15
- First Accepted (MCC) : (user) / xx:xx

### 余談

実はこの問題は一度改題されていて、当初の問題は部分木更新のないパスの数え上げでした。
式変形を頑張って二重シグマを外して～とかやって実装が重い！辛い！と思ったのでボス枠に置いたのですが、Tester にもっと軽い実装で解かれた上にボス枠としては弱いという指摘を受けたので強化してこうなりました。~~(強化後を解くのに 1 ~ 2 時間くらいかかったんですが、Tester に強化案を見せたら 5 分くらいで解かれました　そんなことある？)~~

最初は木上の重み一点更新とパスの数え上げに強化しようとしたんですが解けず、調べたら似たようなタイプの問題がとある問題で最高難易度として出ていたのを見つけて考えるのを止めました。

ちなみにこれって Static Top Tree とやらに載るのでしょうか。履修できていないので強い人教えてください…。

---