# JOI埋め

https://joi.goodbaton.com/

# 難易度7

## 最悪の記者

大小関係がたくさん与えられて、それに整合する順序があるかを求めるタイプの問題。

今回の問題では、整合する順序の存在は保証されていて、代わりに解が複数あるかどうかを求める必要がある。

$i < j$という関係性をグラフに落とし込み、$i$から$j$に有向辺が張られているとみなす。

条件より必ずDAGが出来るので、トポロジカルソートをしてあげると解の一つが求まる。

解が一つしか無いかどうかは、ノードが交換可能かどうかを調べる。

すべてのトポロジカル順に隣り合うノードの組の間に辺が張られているとき解は一つ。そうでないときは複数ある。

## Fermat

> 素数$p$と自然数$N$が与えられる
>
> $x^N + y^N \equiv z^N \mod p$
>
>を満たす整数$x, y, z$の組の個数を求めよ。
>

$0 \leq x \leq p - 1$に対する$x^N \mod p$の値は繰り返し二乗法で求まる。

### 愚直解 $\mathrm{O}(p^2)$

$x^N$の取り得る値、$y^N$の取り得る値について、それぞれ全探索し個数の積を足していくと求まる。$10^8$だけど間に合ってしまう。

*unordered_map*に繰り返し二乗法で求めた値の個数を保存していった。

### TODO: 計算量改善した解

Not solved yet

---
###### tags: `competitive-programming` `JOI`

## Route

結構難しい、グラフを拡張してダイクストラ法で解く。

3点の関係性があるので、前々回訪れたところまでの情報を持てるようにすればよい。

> $G(i, j):=$前回点$i$を訪れていて、今点$j$にいる状態

とすると、

$G(i, j) \rightarrow G(j, k)$間の状態遷移は

- $i, j$間, $j, k$間に辺が存在する
- 辺$ij$、辺$jk$のなす角が鋭角でない

の条件を満たすとき可能。

このとき、$G(i, j) \rightarrow G(j, k)$間に辺$jk$の重みを持たせた有向辺を張る。

これは$\mathrm{O}(N^3)$で実行可能。

ダイクストラで解くには単一始点にしたいので、特殊な初期状態$G(0, 0)$を考えて、$G(0, 0) \rightarrow G(0, i)$にも辺を張っていく（$0,i$間に辺が存在すれば）。

以上で拡張したグラフ上でのダイクストラ法で解けた。

---

鋭角条件 : $cos\theta > 0$ の求め方は、内積を見るのが一番楽

## Flu

二点間の関係を見ていくのは厳しいけど、条件の距離の範囲が$25$と小さいのと座標が$1000\times1000$の範囲であることに注目。

各都市を予めソートしておく。また、二次元配列に都市のindexを保存しておく。

各都市について$25\times50$の範囲で探索していき、都市が存在すれば２点間に辺を張っていく。

答えは、都市$0$からの距離$dist$が$K - M + 1 \leq dist \leq K$を満たす都市の数。

距離はBFSで求めるのが自然な気がするけど、ダイクストラでも間に合う。