黄色difficultyとき直し - ferinの競プロ帳

黄色difficultyあたりの適正難易度帯を昔やって忘れてるのもったいないので2周目

D - Ears

0, 偶数, 奇数, 偶数, 0 の5個の領域のどこにいるか？をDPのkeyに持つ
耳DP，DFAの状態をkeyに持つやつの一種だと認識している

D - No Need

dp[i枚目][総和がj] のナップサックDP
i枚目を加えたときにK以上になるならばiは必要
左右からDPしてi枚目がDPの最後にくるようなのを全てについて試す

C - Best-of-(2n-1)

高橋くん/青木くんが勝つ場合，それぞれについて計算して足す
A％がn-1回，B％がi回，C%がj回起きた後にA％が起きる確率 * (n+i+j) の総和
wolfram alphaに突っ込むと閉じた形の式が出てくる

C - +/- Rectangle

a a a a a
a -3a-1 a -3a-1 a
a a a a a
a -3a-1 a -3a-1 a
a a a a a
みたいな雰囲気でh*wの右下に負を突っ込む

D - Modulo Operations

自分より大きい数でmodをとっても何も起きないので降順sortしておく
dp[i番目まで][黒板の数がj] = 期待値

F - Small Products

dp[i番目まで][最後がj] = 何通り
$N/i$ が変化するのは $O(\sqrt{N})$ 個しかないのでそれだけ考えると間に合う

$\lfloor N/i \rfloor$ は $O(\sqrt{N})$ 個しか存在しない
実装

vector<ll> v;  
for(ll i=1; i<=n;) {  
    ll tmp = n/i;  
    v.push_back(tmp);  
    i = n/tmp + 1;  
}  
sort(ALL(v));

B - Even Degrees

辺数が奇数だと不可能
DFS木で子の数が奇数なら親との辺もつかって偶数にする
偶数ならそのままつなぐ

F - Engines

偏角ソートすると選ぶべきエンジンはある区間になる
$O(N^3)$ で全探索できる

E - guruguru

2周分確保しとく
xを1増やすと押す回数が1減る or a_{i+1}を超えて押す回数が増えるの2択
切り替わるタイミングを持っておいて平面走査みたいな雰囲気

C - Lexicographic constraints

種類数決め打ち二分探索
文字列を持って遷移していく
文字が長くなるなら後ろにaを付け足す
それ以外の場合は prefixの $a$ 個の辞書順+1 を求める

E - Don't Be a Subsequence

辞書順最小を求めるテクとして後ろからDPして前から復元
next[i][j] = i文字目以降で最初に現れる文字jの位置
dp[i] = 部分文字列[i,n)でかかる制約に違反しない最短の文字列の長さ
dp[i] = min(dp[next[i][j]] + 1)
各iについてどこからどの文字で遷移してきたかを覚えておいて復元する

忘れてたこのタイプ苦手
https://atcoder.jp/contests/arc081/submissions/9849717

B - Splatter Painting

上書きされる → 最後に塗られる色しか影響しない
dp[頂点v][距離d以下] = クエリは来たか？というmemo用の配列を持つ
メモ化再帰で計算量を抑えられる

なんかdがでかくても重心分解で解けるみたいなのみたことある気がする解いてないけど

D - Grid game

高橋くんは毎回移動しないといけない
青木くんはうまいこと動かして障害物の上にできるだけ早く当たるようにする
i行目でどの列まで移動できるか？を覚えておくと行ごとに遷移が高速にできる

E - Grouping

dp[i人以下のグループ][j人を振り分けた] = 何通り？
dp[i-1][j+ki] += dp[i][j] * 振り分け方の係数 (c <= k <= d or k = 0)

E - + Graph

全域木を適当に取る
1頂点決めると残りは全部決まる
決めた頂点を+1すると距離が奇数の頂点は-1で偶数の頂点は+1
後退辺とか頂点の重みが正の条件を満たすように+/-を制御

E - Integers on a Tree

とりあえず偶奇の条件がかかる
木DPみたいに部分木ごとに考える
子に置ける範囲から頂点に置ける値の範囲が決まる
この範囲を持ってDP

D - Yet Another Palindrome Partitioning

int型で2²⁶は256MB程度
{A, B, …, Z} をkeyに持つことは可能

https://atcoder.jp/contests/code-festival-2017-qualc/submissions/9864552

E - Independence

クリーク内の辺を最小化するような，素なクリークでの分割を求めろ
補グラフを取ると，クリークは最大独立集合になる
最大独立集合で分割するので二部グラフでないと不可能
連結成分ごとに二択を決めるのをDP

E - Children and Candies

$x_i$ を変動させることを忘れて $f(x_1,x_2,\ldots,x_n)$ を求める
dp[i人目][j個] = 積の総和が3乗
$x_i$ を変動させるとしても遷移に係数がかかるだけ

D - K-th K

$x_i$ 番目に $i$ を置くのは確定
$\lbrack 0,x_i-1 \rbrack$ に $i$ 個， $\lbrack x_i+1,n-1 \rbrack$ に $n-1-i$ 個
$\lbrack 0,x_i-1 \rbrack$ は左に， $\lbrack x_i+1,n-1 \rbrack$ は右に詰めておくべき
実際に置いてみてだめだったらNO

F - Fork in the Road

辺削除がなければ $O(N^2)$ のDPでok
削除する辺は各頂点について高々1本 3乗でできる

$A_i$ が大きい方から決めていくシミュレーションで通した
最大の $A_i$ が $A_i \gt B_i$ となっているのを直す
これは $A_i \leq B_j$ であるような $j$ について $\text{swap}(A_i, A_j)$ をすれば $A_i$ については直る
$(A_i, B_j)$ はok， $(A_j, B_i)$ について $A_j \leq B_i$ となるようにするには $A_j$ が最小の $j$ を選ぶとうれしそう
この操作を繰り返すシミュレーションでswap回数が $N-2$ 回以下ならばYes

B - Holes

凸包の内側の穴 → Rがめっちゃでかいから無視できる
穴の垂直二等分線からなる角度の比がそのまま角度になる

F - Lotus Leaves

最小カットまんま

B - Row to Column

ある行を全部黒にしたあと白がある列を塗る
全部黒にする行を全探索

D - Digit Sum

わからんので「n進数桁和」でググるとn-1で割るとうれしそうなことがわかる
$a_mb^m + a_{m-1}b^{m-1} + \cdots + a_1b + a_0 = n$ から
$a_m + a_{m-1} + \cdots + a_1 + a_0 = s$ を引く
左辺が $b-1$ の倍数になる → $b$ は $n-s$ の約数+1
約数は $O(\sqrt{n})$ 個なのでできる

n=sは気をつけないといけない
n=10¹¹だとi*i<=nでllでもオーバーフローする
3WAしましたが…
https://atcoder.jp/contests/arc060/submissions/9925762

C - Remainder Game

$2^k \gt 2^{k-1} + 2^{k-2} + \cdots + 2^1$ から $k$ を使わないで済むなら絶対に使わない
$k$ 未満のみを用いた遷移で $a_i$ から $b_i$ に移れるか？
$x \bmod i = y$ ならば $x$ から $y$ に辺を貼ったグラフで連結か？を見ればよい
移れない頂点があったら確定で $k$ を使う
$\text{can} \lbrack i \rbrack \lbrack j \rbrack = i$ 番目を $j$ にすることが可能か？を持って遷移していく

30分くらい
$a_i$ を割るときの条件とか考えてたけど冷静に考えて全部持てばいいだけ…
https://atcoder.jp/contests/agc022/submissions/9926136

D - Three Colors

辺の長さから三角形をつくれるかの条件は $R+G \lt B$ かつ $R+B \lt G$ かつ $B+G \lt R$
こういうのは補集合を数えるようにして包除
$R+G \geq B$ もしくは $R+B \geq G$ もしくは $B+G \geq R$ になる
包除で1つ満たす，2つ満たす，3つ満たすをそれぞれ数える
対称性があるので $R+G \geq B$ を満たすのを数えて3倍すればいい
2,3つ満たすのは $R=0, B=G$ みたいなのしかない
$(R,G,B \neq 0$ となる塗り方 $) - (R+B \geq G) \times 3$ を求めればいい

https://atcoder.jp/contests/tenka1-2019/submissions/10043958

E - Connected?

周上にあるやつしか関係なくて，カッコ列みたいなノリで繋げられるかどうかを判定

F - Xor Shift

$a_i \oplus b_i$ が全て一致するような巡回シフトを見つければいい
$a_1 \oplus b_1 = a_2 \oplus b_2$ なので $a_1 \oplus a_2 = b_1 \oplus b_2$ と変形
XORで隣接差分を取ると，巡回シフトをしたときに数列が一致するか？という問題になる
数列を2周分並べると一致する部分列があるか？という問題になる
あとはZ-algorithmではい

D - Game on Tree

grundy[v] = XOR(grundy[c]+1) がgrundyになるのを覚えてた
grundy[v] = XOR(子c側のgrundy) はgrundy数の定義から明らか
子cの部分木 + 辺1本からなるようなグラフのgrundyを知りたい
これは grundy[c]+1 となることが示せる

これは覚えてたけど実際解くとしたら実験grundy エスパーなのかなあ

F - Minimum Bounding Box

左右・上下で独立に考える
max, minになりうるのはL,Rそれぞれで高々1つ
短くなったあと長くなるみたいな感じになる
関数の形が変わる点ごとに考えればいい

F - Pass

$\text{dp} \lbrack i$ 文字目まで $\rbrack \lbrack$ 赤を $j$ 個 $\rbrack =$ 何通り
$i$ 文字目に赤を置けるか？ → 残りの赤の $(S$ の $i$ 文字目までの赤の個数 $) - j$ があるか

https://atcoder.jp/contests/yahoo-procon2019-qual/submissions/10054660

E - Antennas on Tree

木のある高さの頂点集合について考える
頂点を根とする部分木のどこかにアンテナがあれば，その頂点については区別可能
全て区別できるようにする条件で木DP
根の次数が1とか2だと困るのでそうならないようにしておく

https://atcoder.jp/contests/apc001/submissions/10055055

C - Differ by 1 Bit

立ってるビットの数の偶奇が変化していくのでAとBの立ってるビットの数の偶奇が一致すると明らかにNO
それ以外は全部作れそう
全体にXOR Aすればスタートが0でゴールがA XOR Bに帰着できる

0 1 0 2 0 1 0 3 0 1 0 2 0 1 0 みたいに再帰的に v + {i} + v をつくっていくと変化させる桁を書いた列をつくれる
0?????, 10????, 110??? を順番に作っていくと 000000 → 111000 みたいなのをつくれる
この構成で全パターンつくれてるのでok

https://atcoder.jp/contests/agc031/submissions/10057284

D - Friction

コストに関連するのは隣り合うやつだけなので $W=2$ を解きたくなる
これは $\text{dp} \lbrack i \rbrack \lbrack j \rbrack =$ 左が $i$ 段，右が $j$ 段残っているときのコストでよさそう
$\text{dp} \lbrack i \rbrack \lbrack j \rbrack = \min(\text{dp} \lbrack i-1 \rbrack \lbrack j \rbrack , \text{dp} \lbrack i \rbrack \lbrack j-1 \rbrack ) + (i,j$ 段残っているときに同じ文字が隣接している個数 $)$
隣接している個数を $O(1)$ で求められるようにしたい
左の $a$ 番目，右の $b$ 番目が一致するならば， $i-j = a-b$ で $a,b$ 番目がまだなくなってないような $i,j$ のときに $a,b$ が隣り合っている
これは二次元グリッドで斜めの隣接した部分に+1なのでimosの要領で高速に求められる

$\text{dp2} \lbrack i \rbrack \lbrack j \rbrack = i-1$ 列目まで全部沈めて $i$ 列目が $j$ 段残ってる
みたいなDPをやろうとしたけど冷静に考えると全部独立なので $\text{dp} \lbrack h \rbrack \lbrack h \rbrack$ を足し合わせるだけでいい

https://atcoder.jp/contests/code-festival-2016-qualc/submissions/10059798

E - Sorted and Sorted

先頭に来るボールは黒1か白1のどちらか
黒1だけあるときに次に来るボールは黒2か白1のどちらか
先頭から決めていくDPをする

$\text{dp} \lbrack i \rbrack \lbrack j \rbrack = ($ 黒を $i$ ，白を $j$ まで並べるときに必要なswap回数 $)$
chmin(dp[i][j], dp[i+1][j] + (黒i+1を先頭にもっていくのに必要なswap回数))
すでに並べた分はswapしなくていいのでその分を引く
前計算しておけばこれはO(1)で求まる

https://atcoder.jp/contests/arc097/submissions/10083590

F - Enclosed Points

点iが何回数えられるか？
自分より上・下・左・右にある点だけしか選ばないようなパターンはだめ
これを別々に数えると，右上・右下・左上・左下だけを選ぶパターンを重複して数えているので包除の要領で引く

30分かかった…
https://atcoder.jp/contests/abc136/submissions/10084049

C - Nuske vs Phantom Thnook

森の連結成分の個数 = 頂点数 - 辺数
累積和を取っておけば各クエリO(1)
x,yの縦横が一番むずかしい

https://atcoder.jp/contests/agc015/submissions/10097392

B - Removing Blocks

取りうる全ての場合の和を求めるときに確率でやるやつ

https://atcoder.jp/contests/agc028/submissions/10097682

D - Two Sequences

$v$ のk bit目が1 → $T=2^k$ としたとき $v$ が $\lbrack T, 2T), \lbrack 3T, 4T), \lbrack 5T, 6T), \ldots$ の範囲内になる
$k$ bit目を参照するとき $k+1$ bitより上の桁は関係ない → $\text{mod} 2^{k+1}$ してもok
$a_i+b_j$ は高々 $4T$ なので $\lbrack T,2T), \lbrack 3T,4T)$ の範囲内になるのが何通り？を求めれば良い

https://atcoder.jp/contests/arc092/submissions/10118840

E - Weights on Vertices and Edges

重みが小さい順に追加していく
辺 $e$ を追加したとき， $e$ が属する連結成分の頂点の重みの和が辺の重み以上
→ 辺 $e$ の重み以下の辺をたどって到達できる辺は残せる
残せる辺集合の和集合を求める

これ苦手
https://atcoder.jp/contests/nikkei2019-qual/submissions/10120341

F - Distinct Numbers

key-valを交換するやつ
f(長さK) = 何回操作可能？ではなく f(x) = x回操作可能なKのうち最長とする
$f(x) = \sum_{i} \min(x, \text{cnt}_i)$ でこれは二分探索で求まる
$f(x)$ 上を二分探索すれば答えがわかる

これ苦手
https://atcoder.jp/contests/abc143/submissions/10121287

B - RGB Balls

前から貪欲に3色セットをつくっていくのが最小になる
この3色セットの最小が $a_i$ ，最大が $c_i$ となる場合最小値を達成できる（適当にswapしたとしてプラマイ0で変化しないので）
あとは3色セットの真ん中に対応させられるのが何個あるのかをそれぞれ求めて掛け合わせる

https://atcoder.jp/contests/agc037/submissions/10123166

E - Black or White

黒だけ, 白だけになる確率をそれぞれ求めればよい

https://atcoder.jp/contests/exawizards2019/submissions/10163359

C - Domino Quality

aacd
bbcd
efgg
efhh

aabbc
dee.c
d..fg
h..fg
hiijj

aabc..
ddbc..
..aabc
..ddbc
bc..aa
bc..dd

aabbcc.
dd.dd.a
..d..da
..d..db
dd.dd.b
..d..dc
..c..cc

これを対角線で並べると全行・全列のクオリティが3

E - Avoiding Collision

最短経路数を数えるのは最短路DAGを考えればDPすればできる
各頂点，辺について衝突するパターンが何通りあるか数えて引く

https://atcoder.jp/contests/arc090/submissions/10167547

F - Infinite Sequence

1, 2 1 1, 3 1 1 1, 4 1 1 1 1, … のように1が並んだ後に1の個数以下の数がくるような並びで分割できる
$\text{dp} \lbrack i \rbrack = \lbrack i,\infty)$ が何通りか
$\text{dp} \lbrack i \rbrack = (n-1)^2 + \text{dp} \lbrack i+1 \rbrack + \sum_{j=2}^n \text{dp} \lbrack i+j+1 \rbrack$
$(n-1)^2$ → $x y y \ldots (x,y \neq 1)$ となるパターン
$\text{dp} \lbrack i+1 \rbrack$ → $i$ 番目が1ならば $i+1$ 番目まではなんでもok
$\sum_{j=2}^n \text{dp} \lbrack i+j+1 \rbrack$ → $i$ 番目が $x \gt 1$ でそれ以降に1が $x$ 個並ぶパターン

ちゃんともれなくダブりなく数え上げるのが大事
https://atcoder.jp/contests/arc071/submissions/10206796

D - Reversed LCS

dp[l][r][i] = 部分文字列[l,r]をi回まで変化させたときの答え
遷移は4通り

chmax(dp[l-1][r][i], dp[l][r][i])
chmax(dp[l][r+1][i], dp[l][r][i])
chmax(dp[l-1][r+1][i], dp[l][r][i]+2) s[l-1]==s[r+1]
両端が一致するならそこで+2
chmax(dp[l-1][r+1][i+1], dp[l][r][i]+2)
両端が一致しなくても変化させれば+2できる

https://atcoder.jp/contests/agc021/submissions/10211919

E - Product of Arithmetic Progression

P(a/d+n-1, n) * dⁿ が答え
a/d+n-1 がMOD以上になる場合やd=0の場合に注意

https://atcoder.jp/contests/m-solutions2019/submissions/10223087

E - Bichromization

隣接する重みが同じ頂点対については隣接する辺をつかって頂点重みを達成できる
このような頂点からスタートして重みが増加するような頂点へ遷移することはできる
多点BFSみたいなのをするとできる

E - Bichrome Tree

vを根とする部分木についてvと異なる色にする頂点の重みの和はできるだけ小さい方がよい
子孫の重みが小さい分には重みを増やせばいいので調整できるが，大きいとどうしようもないので
したがって各頂点について条件を満たすような重みにしたとき，異なる色の重みを最小化する問題を木DPで再帰的に解いていく

各子について色をあわせるか/合わせないか2通りがある
dp[i番目まで][頂点vと同じ色の重みがj以下] = 異なる色の最小
としたDPを各頂点で解くと，異なる色の重みの最小化ができる

https://atcoder.jp/contests/arc083/submissions/10256207

E - Young Maids

辞書順なので貪欲に考える
先頭になりうるのは偶数番目の要素なのでこの中でもっとも小さい要素が先頭
2番目になりうるのは先頭より後かつ奇数番目
区間[3番目の位置,4番目の位置]が先頭,2番目の要素を含むようなのは無理なので，[0,1番目の位置) [1番目の位置+1, 2番目の位置) [2番目の位置+1, n) と区間を分割して，区間内で考えるようにする

これを普通に書くと $O(n^2)$ なので高速化する
区間を選択するパートと区間の中から偶数/奇数番目の最小の要素を見つけるパートが存在する
最小の要素を見つけるのはセグ木2本持てばok
区間を選択するパートはkeyとしてその区間の偶数番目の最小の要素をもたせたヒープをもつとできる

セグ木で高速化しようとしたけどデータの持ち方が微妙で実装が終了した

https://atcoder.jp/contests/arc080/submissions/10323584

D - Black and White Tree

葉に隣接する頂点に白を置いたら葉に黒を置かないと不可能
相手を強制できる操作はだいたい強い[要出典]のでこれを繰り返す
葉と葉に隣接する頂点を消すのを繰り返したときに孤立点が残ってたらそこを白にできる
トポソみたいな雰囲気で葉から消してく操作を繰り返す

解説を読んで証明をかんがえる
完全マッチングが存在 → 白を置いた頂点に対応する頂点に黒を置けば後攻の勝ち
完全マッチングが存在しない
葉に隣接する頂点を白にしたとき，葉は絶対に黒に塗らないといけない
この2頂点を取り除いたn-2頂点の木の問題に帰着できる
完全マッチングが存在しないので確実に1頂点は残るので先行の勝ち

https://atcoder.jp/contests/agc014/submissions/10325854

E - Non-triangular Triplets

とりあえず $c_i$ にするのは $k+2n \sim k+3n-1$
kからk+2n-1までの和 <= k+2nからk+3n-1までの和じゃないと明らかに不可能

k+n/2番目までを大きい方に対応させるとなんかうまくいく
a: 1 2 3 4 / 5 6 7
b: 11 12 13 14 / 8 9 10
c: 12 14 16 18 / 13 15 17

天才構築があったことだけ覚えててがちゃがちゃやってたら見つかった

https://atcoder.jp/contests/nikkei2019-2-qual/submissions/10327229

E - Papple Sort

回文にできるかの判定はいつもの

文字列の前半・後半で半分ずつに分割されてないと回文になるわけがないのでとりあえずこれを満たすようにする
あと文字列長が奇数なら真ん中の1文字は奇数個のやつ

同じ文字を入れ替える意味はないので，各文字種ごとに前半分と真ん中にくるやつと後ろ半分に分割
最短手数でこれを満たす文字列をつくる
ataatmma → atamatma

後ろ半分をswapしても前半分をswapしても結局関係ない
後ろ半分を前半分に合わせることにする
atamatma → atammata

与えられた文字列のi番目をtrans[i]番目に持っていくべきというのがわかる
あとは普通の転倒数を求めるだけ

https://atcoder.jp/contests/arc088/submissions/10330482

E - Snuke Line

調和級数っぽい

FOR(d, 1, m+1) for(int i=d; i<=m; i+=d) {  
    // (i-d, i] に始点がある && (i-d, i] に終点がない区間を数える  
    // rangefreqができるやつで頑張る  
}

segtreeとかwaveletで数えたら間に合ったけどこれ計算量なんだ
segtreeは $O(M \log M \log^2 N)$ とかに見えるけど1secで通った
実はもうちょっと早いのか…？

https://atcoder.jp/contests/arc068/submissions/10331633

解説を見た
区間長がd以上 → 必ず訪れる
それ以外 → 高々1回しか訪れることはない
1回しか訪れない区間に一様に+1した数列をつくっておく
この数列で添字がdの倍数のところを見て和を求めると答えが求まる

dを増やしたときに区間長がd未満になる → 数列の[l,r]に+1
あとは各dについて倍数のところだけ見ると調和級数

https://atcoder.jp/contests/arc068/submissions/10332345

C - Median Sum

部分和問題なのでDPするしかない
とりあえず思いつくのはdp[i番目まで][和がj以下] = 何通り
これは $O(N^2A)$ あっておしまい

部分集合Pとその補集合Qのペアをつくる
sum(P) <= sum(Q) としても一般性を失わない
sum(P) + sum(Q) = 全体の和なので sum(P) <= 和/2 <= sum(Q)

部分集合の和の前半部分の $2^{N-1}$ 個にP，後半部分にQが対応する
中央値となるのはQのうち一番小さいものになる
dp[i番目まで][和をjにできるか] = true/false としたDPをする
これはbitsetで高速化できて $O(N^2A/64)$ ならok

bitsetで荒れた（？）のおぼえてる

https://atcoder.jp/contests/agc020/submissions/10332780

C - Three Circuits

場合分けして頑張る

次数が奇数の頂点が存在
一筆書きで一周することがそもそも不可能なので無理
次数が6以上の頂点vが存在
頂点vからスタートして一筆書きをする
頂点vに訪れるたびにサーキットとして分割すると少なくとも3個には分割できる
次数が4の頂点が1個以下
一つサーキットをつくるには各頂点から次数2減らす分の辺が少なくとも必要なのでどう頑張っても足りない
次数が4の頂点が3個以上
次数4の頂点をA,B,Cとする
Aを始点として一筆書きをすると，次数が6以上の場合と同様の議論で少なくとも2つのサーキットに分割可能
- サーキットの少なくとも1つに2回以上訪れる頂点が存在
  その頂点のところでサーキットを切断すると，サーキットを増やせる
- それ以外
  A → … → B → … → C → … → A みたいなサーキットが2つ存在する
  A → B, B → C, C → A の部分をそれぞれつなぎ合わせるとサーキットができるので3個つくれる
次数4の頂点が2個
次数4の頂点をA,Bとする
AとBの間の経路が2本 → OK
AとBの間の経路が4本 → NG

証明が大変

https://atcoder.jp/contests/agc032/submissions/10341260

E - Awkward Response

桁数が同じ場合，辞書順と昇順は一致するのでとりあえず桁数を求めたくなる
1, 10, 100, … と答えを比較してみる
答えを123とする
1 → 'Y' 1<=123, str(1)<=str(123)
10 → 'Y' 10<=123, str(10)<=str(123)
100 → 'Y' 100<=123, str(100)<=str(123)
1000 → 'N' 1000>123, str(1000)<=str(123)
10000 → 'N' 10000>123, str(10000)<=str(123)
Yが返される最大の桁数と一致する

答えが 100…00 の場合，任意の $10^a$ についてYが返ってくるので上の方法で桁数を求めようとしてもうまくいかない
このパターンについては9…99を試せばいいのでok

残りのパターンについては

n < N のとき: str(10n) <= str(N), 10n > N なので'N'が返り値
n >= N のとき: str(10n) > str(N), 10n > N なので'Y'が返り値

となる単調性を使って二分探索

https://atcoder.jp/contests/arc078/submissions/10343490

F - Sum Difference

S+T = sum(A_i) で一定
S-T = sum(A_i) - 2T なので T が取りうる値が何通りか求めればよい

数列からi個選んだときに作れる数は $ix + d(0+1+…+i) \sim ix + d{(n-i)+(n-i+1)+…+(n-1)}$ の範囲になる
0~n-1の中から自由にi個選んだとき $0+1+…+i \sim (n-i)+(n-i+1)+…+(n-1)$ の範囲は全部作れる
ix mod d で場合分けするとある連続した区間を全部つくれることになる
あとは区間がたくさん与えられたときの和集合の大きさを求められればよい
区間を始点でソートして手前からマージしていけばok

D - Isomorphism Freak

カラフルさの最小化から考える
木の直径の中心をもとに対称になるような木をつくると ceil(木の直径/2) はできそう
ceil(木の直径/2) より小さくするのは無理そう

ceil(木の直径/2) を達成するように中心を設定したときの葉の枚数を考える
対称となるような木にするため設定した中心を根にしたときの，各深さでの頂点数の積となる

各頂点・辺を中心としたときの葉の枚数をすべて試すことで $O(n^2)$

https://atcoder.jp/contests/agc024/submissions/10358491

C - Squared Graph

連結成分ごとに考えていく
パリティ的に二部グラフ・非二部グラフで連結成分の数が変わるのがわかる
二部と二部をつなぐ → 連結成分2つ
非二部と何かをつなぐ → 連結成分1つ
孤立点と何かをつなぐ → 頂点数分の連結成分

二部グラフ判定をバグらせない

https://atcoder.jp/contests/agc011/submissions/10370738

C - GP 2

操作によってできる数列がどのようなものか考える
明らかな必要条件として

合計が3M
max < 2M
奇数はM個以下

これを満たすような数列ならつくれることが確認できてこれは必要十分条件

とりあえずmax < 2M の条件を忘れて，別の条件を満たすやつを数える
これは N要素の数列 && 合計が3M && 奇数がM個以下を数えれば良い
奇数がi個のとき → (奇数の場所i個の選び方) * (総和が3M-iとなる偶数からなる数列の総数)
(奇数の場所i個の選び方) = combi(n, i)
(総和が3M-iとなる偶数からなる数列の総数)
= (総和が(3M-i)/2となる数列の総数)
= combi( (3M-i)/2+N-1, N-1)
0 <= i <= min(N,M) について求めて足すことで求められる
よってこれは O(N+M) で求められた

max >= 2M となるようなものを引く
N-1要素の数列 && 合計がM以下 && 奇数がM個以下となる数列に 3N-合計の要素を足すとmax >= 2M の数列になる
要素を足す位置はN通り存在するので，ありえる数列の総数にNを掛ければok
(N-1要素の数列 && 合計がM以下 && 奇数がM個以下となる数列の総数)
= (N要素の数列, 合計がM, 奇数がM個以下) - (N-1要素の数列, 合計がM, 奇数がM個以下)

これらの数列は上記の数列と同様に求められる

https://atcoder.jp/contests/agc036/submissions/10374598

F - Colorful Tree

求める距離 = (パスu,vの距離) - (色xの辺の距離) + (色xの辺の本数)y
パスu-vの距離 = (根からuの分) + (根からvの分) - 2(根からlcaの分) と分割する

各頂点にクエリ番号idxのLCAかパスの端点か？の情報をもたせておく
根から今いる頂点までのパスについての距離・色ごとの本数・色ごとの距離を持ちながら木上を移動していき，各頂点に来たときに対応するクエリに寄与する分を計算

https://atcoder.jp/contests/abc133/submissions/10376688

F - Xor Sum 3

X = A_1 xor A_2 xor … xor A_n とする
Xが1となる，つまり1が奇数個の桁についてはどう分割しても赤のXOR + 青のXOR が1にしかならない
Xが0の桁については (赤のXOR, 青のXOR) が (0, 0) か (1, 1) になる
Xが0の桁についてのみ考えると，赤のXORも青のXORも常に同じ
部分集合をうまく選ぶことでXOR和を最大化するような問題になった
これは60×NのF_2の行列とみなして，基底を求めたあと，上の桁から貪欲に大きくしていくことで解ける

https://atcoder.jp/contests/abc141/submissions/10377318

C - Cleaning

こういうのは木DPする
葉について色々する問題で根を葉にすると面倒なのでそうならないようにする
n=2だと全頂点が葉でコーナーになりがちなので注意

頂点vを根とした部分木内で完結するパスと頂点vの親の方へ向かうパスが存在する
各部分木で部分木内のマッチングがうまくできるか？と親の方へ向かうパスが何本か？をボトムアップで解いていく

頂点vの子cについて親へ向かうパスが何本あるか？の情報が伝播されてくる
a[v] と sum(dp[c]) の値から頂点vの親へ向かうパスが何本になるかは一意に定まって，(a[v] - ceil(sum/2))*2 + sum%2 本になる
あとは a[v]-(親へ向かうパスの本数) 個のペアをつくれるか？という問題になる
これは max > sum/2 が必要十分条件で判定可能

https://atcoder.jp/contests/agc010/submissions/10384308

E - XOR Partitioning

累積XORを取るとかなり見通しがよくなる
最初の区間のXORがXとすると，次の区間をXにするには累積XORが0の位置までを次の区間にする必要がある
その次の区間をXにするには累積XORがXの位置までを次の区間にする必要がある
同様に考えると累積XORが X 0 X 0 X 0 … となるような要素を順に選んでいく方法が何通りあるか？という問題に置き換えられた
これはdpを行うことでO(Xと0の個数)で解ける

2²⁰通りのX全てについてdpを行うと0が多い場合にTLEしてしまう
そこで0が連続する場所についてまとめてDPの遷移を行うことで各XについてO(Xの個数)でDPを行うことができる

https://atcoder.jp/contests/diverta2019/submissions/10387058

E - Negative Doubling

負の部分と正の部分に2分割して，それぞれ独立に解く
[0,i] を負で増加列にするのに必要な操作回数・[i,n) を正で増加列にするのに必要な操作回数をそれぞれ求められればあとは全てのiについて試すことで解ける

符号を固定した場合，4倍する操作を繰り返すとみなせる
DPで操作回数を求める
状態： dp1[i][j] = (i番目に4倍する操作をj回行うときに区間[i,n)を昇順にするのに必要な操作回数)
遷移： chmin(dp1[i][j], dp1[i+1][k] + j) ただし $k$ は [tex:a \lbrack i \rbrack 4^j \lt = a \lbrack i+1 \rbrack 4^k] を満たす

負の部分についても同様のDPで解ける

https://atcoder.jp/contests/caddi2018/submissions/10399167

F - Coincidence

y mod x と x xor y が一致するのは最上位bitが同じで(1,0)となる桁が存在しないとき
dp[i桁目][L<=xが確定か？][y<=Rが確定か？][(1,1)がすでに現れたか] で桁DP

D - Teleporter

a[0]=0以外で条件を満たすことはない
a[0]=0とすると，頂点0との距離がK以下となるように辺をつなぎかえる問題になる
木をボトムアップに見ていって，頂点vを根とする部分木に距離Kより遠い頂点が存在するならばつなぎかえるとすればよい

https://atcoder.jp/contests/agc004/submissions/10400747

F - Strange Nim

実験するとgrundy数は
nがk未満なら 0
n%k=0 なら n/k
それ以外なら grundy[n] = grundy[n-n/k-1]
になっている

これを愚直に求めようとするとTLEするのでうまくまとめたい
n/kが小さいときが問題なのでn/kが変わらないうちはまとめて遷移する
n-i(n/k+1) が n/k*k 以下になるようなiの分はまとめて遷移できる
こうすると O(min(N/K, K)) でgrundy数が計算できて間に合う

https://atcoder.jp/contests/arc091/submissions/10401549

E - Ball Coloring

rmin = min, bmax = max もしくは rmin = min, rmax = max の2パターンに分類できる
rmin = min, bmax = max の場合，小さい方を赤，大きい方を青に塗るのが最適
rmin = min, rmax = max の場合，どう塗ってもrmax-rminは変動しないので青は自由に塗ってよい
x[i] < y[i] として x[i] でsortしておく
このとき [0,i] はyを青，[i+1,n) はxを青と塗るのが最善
より小さいxが青くなっているのに，x→yに変えても最大値が大きくなるだけで絶対に得することはない

https://atcoder.jp/contests/arc073/submissions/10403071

F - Strings of Eternity

[i,i+t.size()) が t と一致する場合，グラフの頂点iから頂点(i+t.size()) mod s.size()に有向辺を張る
この有向グラフで最長経路を求めればよい

ループが存在するならば無限に増やせて答えは-1
ループ検出はトポソでできる
ループが存在しないならばDAGなのでDPすれば求まる

https://atcoder.jp/contests/abc135/submissions/10402080