uchidama

'''
[問題]
https://atcoder.jp/contests/abc165/tasks/abc165_d

[解説]
https://blog.hamayanhamayan.com/entry/2020/05/02/225827
'''

import sys

uchidama

'''
[問題]
https://atcoder.jp/contests/abc159/tasks/abc159_d

[参考]
https://blog.hamayanhamayan.com/entry/2020/03/22/235319
　C(個数,2)、つまり、個数×(個数 - 1)/2の総和を取れば答えになる。

[結果]
PyPy3(7.3.0) AC 249ms

uchidama

'''
[問題]
https://atcoder.jp/contests/abc169/tasks/abc169_d

[解説]
https://blog.hamayanhamayan.com/entry/2020/06/01/210704
　素因数分解は計算量 O(sqrt(N))　
　制約条件N=10^12なので計算量は10^6
　計算量から素因数分解をメタ読みできる。
　

uchidama

'''
[問題]
https://atcoder.jp/contests/abc166/tasks/abc166_c

[結果]
PyPy3(7.3.0) AC 180ms
Python(3.8.2) AC 272ms
'''

import sys

uchidama

'''
[問題]
https://atcoder.jp/contests/abc209/tasks/abc209_d

[解法]
https://youtu.be/FEDp2Kzc7jk?t=3245
　二分木の問題。
　c,d間の距離の偶奇が答えになる。
　最小共通祖先（Lowest Common Ancestor）を求めなければならない気がするが、偶奇の判定はc,dの深さだけで問題ない。
　depを深さと考えて、最短距離は

uchidama

'''
[問題]
https://atcoder.jp/contests/abc210/tasks/abc210_c

[解法]
しゃくとり法で解けた

[参考]
AtCoder Beginner Contest 032 [ C - 列 ]をPythonで解く。しゃくとり法をやってみる（💧水色diff）
https://uchidama.hatenablog.com/entry/2021/07/16/002834

uchidama

'''
[問題]
https://atcoder.jp/contests/abc210/tasks/abc210_d

[解説]
https://youtu.be/_mhHn_o6b3Y?t=3093　
　基本、snukeさんのこのコードをPythonコンバート

https://atcoder.jp/contests/abc210/editorial/2298
https://kanpurin.hatenablog.com/entry/2021/07/17/232213

uchidama

'''
[問題]
https://atcoder.jp/contests/abc172/tasks/abc172_c

[参考]
https://blog.hamayanhamayan.com/entry/2020/06/27/230511
　変形？しゃくとり法で数列A、Bを走査する

[結果]
PyPy3(7.3.0) AC 146ms

uchidama

'''
[問題]
https://atcoder.jp/contests/abc032/tasks/abc032_c
　しゃくとり法の練習問題

[解法]
Pythonでしゃくとり法（尺取り法）を実装してみる-ABC032
https://nashidos.hatenablog.com/entry/2020/02/02/165319
　ここ参考

uchidama

'''
[問題]
https://atcoder.jp/contests/abc162/tasks/abc162_c
'''

import sys
import functools
import math

sys.setrecursionlimit(10 ** 6)  # 再帰上限の引き上げ