第二回日本最強プログラマー学生選手権 感想

#総合結果
* [Score] 1600 pts
* [Time] 069:46 + <font color="red"> 05:00 $\times$ 0 </font> = 069:46
* [Ranking] 197 th [Rated内: 63 rd]
* [Performance] <font color=#C0C000> 2192　</font>
* [Rating] <font color=#0000FF> 1915 </font> → <font color=#0000FF> 1946 </font> (+31) (Highest!!)

##各問題ごとの詳細, 提出コード
|Question|Score|Time/Result|Penalty|During Contest|After Contest|
|:--:|--:|:--:|:--:|:--:|:--:|
|<font color=#808080> A問題 </font>|100 pts|004:49|<font color="red"> </font>|[■](https://atcoder.jp/contests/jsc2021/submissions/21806202)|[■](https://atcoder.jp/contests/jsc2021/submissions/21833719)<br> ($O(1)$)|
|<font color=#808080> B問題 </font>|200 pts|006:42|<font color="red"> </font>|[■](https://atcoder.jp/contests/jsc2021/submissions/21807420)||
|<font color=#808080> C問題 </font>|300 pts|009:47|<font color="red"> </font>|[■](https://atcoder.jp/contests/jsc2021/submissions/21809234)||
|<font color=#804000> D問題 </font>|400 pts|013:26|<font color="red"> </font>|[■](https://atcoder.jp/contests/jsc2021/submissions/21811008)||
|<font color=#C0C000> E問題 </font>|0 pts|---:--|<font color="red"> </font>|||
|<font color=#0000FF> F問題 </font>|600 pts|<b>069:46</b>|<font color="red"> </font>|[■](https://atcoder.jp/contests/jsc2021/submissions/21811008)||
|<font color=#FF8000> G問題 </font>|0 pts|---:--|<font color="red"> </font>|||
|<font color=#B87333> H問題 </font>|0 pts|---:--|<font color="red"> </font>|||
|<b>Total</b>|<b>1600 pts</b>|<b>069:46</b>|<b><font color="red"> No Penalties </font></b>|||

#問題ごとの略解
##<font color=#808080> A問題 (100pts, diff: 42) </font> [Competition](https://atcoder.jp/contests/jsc2021/tasks/jsc2021_a)

答えるべきは, $\dfrac{Y}{X}>\dfrac{a}{Z}$ を満たす最大の非負整数である. $a=0,1, \dots$ と条件を満たすかどうかを調べれば良い. なお, $\dfrac{YZ}{X}>a$ なので, 答えは $\left \lfloor \dfrac{YZ-1}{X} \right \rfloor$ である.

##<font color=#808080> B問題 (200pts, diff: 51) </font> [Xor of Sequences](https://atcoder.jp/contests/jsc2021/tasks/jsc2021_b)

$A, B$ を集合と見なすと, 求めるべき答えは対称差 $A \triangle B$ である. なお, 愚直に数列として存在性を調べても間に合う.

##<font color=#808080> C問題 (300pts, diff: 343) </font> [Max GCD 2](https://atcoder.jp/contests/jsc2021/tasks/jsc2021_c)

最大公約数について, 以下の性質がある.
$$\gcd(x,y)=\max \\{n \in \mathbb{N}| x,y は n の倍数 \\}$$

よって, $A$ 以上 $B$ 以下の整数のなかに, $n$ の倍数が2つ以上あれば, 答えは $n$ 以上になることがわかる. また, 答えは $B$ 以下であることがわかることから, $n=1, \dots, B$ に対して, $A$ 以上 $B$ 以下の整数のうち, $n$ の倍数がいくつあるかを調べ, $2$ つ以上であるような $n$ に対する最大値が答えになる.

$A$ 以上 $B$ 以下の $n$ の倍数の個数を考えると, $X$ 以下の正の整数で $m$ の倍数であるものは $\left \lfloor \frac{X}{m} \right \rfloor$ である. このことから, $B$ 以下の正の整数で $n$ の倍数であるものから, $A$ *未満* の正の整数で $n$ の倍数を除けば良いので,
$$\left \lfloor \dfrac{B}{n} \right \rfloor-\left \lfloor \dfrac{A-1}{n} \right \rfloor$$
である. よって, 求めるべきは
$$\max \left \\{1 \leq n \leq N \left| \left \lfloor \dfrac{B}{n} \right \rfloor-\left \lfloor \dfrac{A-1}{n} \right \rfloor \geq 2\right. \right \\}$$
であり, 計算量 $O(B)$ で求めることができる.

なお, 答えの範囲はさらなる考察によって, $1$ 以上 $B-A$ 以下であることがわかる.

##<font color=#804000> D問題 (400pts, diff: 743) </font> [Nowhere P](https://atcoder.jp/contests/jsc2021/tasks/jsc2021_d)

第1項目から順に決めていく. ただし, $P$ 未満の整数 $x$ と $R:=\mathbb{Z}/p \mathbb{Z}$ の元 $[x]_p$ を同一視する.

* 第1項目 $A_1$ は, $R^*:=R \setminus \\{[0]_p\\}$ の元を任意に取ることができる.
* 第2項目について, $A_1 \in R^\*$ という条件下で, $A_1+x \neq [0]_p$ ならば, $x \in R^\* \setminus \\{A_1\\}$ であり, 逆も成立する. よって, $A_1$ を固定すると, 第2項目としての候補は $P-2$ 通り考えられる.
* 第3項目について, $A_1+A_2 \in R^\*$ という条件下で, $A_1+A_2+x \neq [0]_p$ ならば, $x \in R^\* \setminus \\{A_1+A_2\\}$ であり, 逆も成立する. よって, $A_1,A_2$ を固定すると, 第3項目としての候補は $P-2$ 通り考えられる.
* $\vdots$

このように考えていくと, 数列 $A$ として可能なのは, 第 $1$ 項が $P-1$ 通り, 第 $2$ 項目以降は, それまでの結果に関係なく, $P-2$ 通りになるので, 求めるべき答えは, $(P-1) (P-2)^{N-1}$ である.

##<font color=#C0C000> E問題 (500pts, diff: 2133) </font> [Level K Palindrome](https://atcoder.jp/contests/jsc2021/tasks/jsc2021_e)

(正解でき次第加筆予定)

##<font color=#0000FF> F問題 (600pts, diff: 1954) </font>[Max Matrix](https://atcoder.jp/contests/jsc2021/tasks/jsc2021_f)

各クエリが来た後, 答えがどのように変化するかを観察する. $a_x$ を $y$ に変更するというクエリによる変更前の答えを $Z$, クエリによる変更後の答えを $Z'$ とする. このとき,
$$Z'-Z=\sum_{j=1}^M \max(y,b_j)-\sum_{j=1}^M \max(a_i,b_j)$$
である. よって, 定数 $t$ において, $\displaystyle \sum_{j=1}^M \max(t,b_j)$ を求めることができればよい.

$b_1, \dots, b_M$ を昇順に並べたものを $b'\_1, \dots, b'\_N$ とする. ここで, $b_i$ のうち, $t$ 以下の個数が $L$ 個であるとする. このとき, $1 \leq t <M$ ならば, $b'\_L \leq t <b_{L+1}$ が成り立つ. よって,
$$ \sum_{j=1}^M \max(t,b_j)=Lt-\sum_{j=L+1}^M b'\_j \left(=Lt+\sum_{j=1}^M b\_j-\sum_{j=1}^L b'\_j \right)$$
となる. よって, $L$ と $\sum_{j=1}^L b'\_j$ を高速に求めることができれば, $Z'=Z+(Z'-Z)$ から求めることができる.

ここで, クエリを先読みし, $Q$ 個の $y$ を記録し, 座標圧縮する. そして, $L$  と $\sum_{j=1}^L b'\_j$ については, BIT を利用することによって, 1クエリあたり $O(\log Q)$ , 全体でも $O(Q \log Q)$ となり, 高速に求めることができた.

##<font color=#FF8000> G問題 (600pts, diff: 2451) </font>[Spanning Tree](https://atcoder.jp/contests/jsc2021/tasks/jsc2021_g)

(正解でき次第加筆予定)

##<font color=#B87333> H問題 (600pts, diff: 3383) </font>[Shipping](https://atcoder.jp/contests/jsc2021/tasks/jsc2021_h)

(正解でき次第加筆予定)


##<font color=#C0C000> 黄色 </font>になるために
次回のコンテストのPerformanceが <font color=#C0C000>2392</font> 以上ならば, <font color=#C0C000> 黄色 </font> 達成.