s/even/odd/

the winning player at i coincides with the winning player of misere Nim on a[i,j).
Note that when a[i,j) contains a value >=2, the winning side of Nim and that of misere Nim are the same, and that otherwise they are different. The rest part is a simple DP optimization.

let's consider the transition from j to i by examining the case where a[i,j) fits into a single box.
・If the winning player at j is the first player, the winning player at i coincides with the winning player of Nim on a[i,j).
・If the winning player at j is the second player,

eaxmple, by extended Euclidean algorithm on polynomials.)
F: Let dp[i] be the pair of the number of ways that the first player has a winning strategy and the number of ways that the second player has a winning strategy for array a[i,n).
We can compute dp[i] in descending order of i. Assuming i<j,

⇔ a+f(x^-1+2+x)≡cn (mod 1-x) and a+f(x^-1+2+x)≡0 (mod 1+x+...+x^(n-1)) for some c in R
⇔ f(1+x)^2≡-ax (mod 1+x+...+x^(n-1))
⇔ f≡-ax/(1+x)^2 (mod 1+x+...+x^(n-1))
Since n is odd, 1+x has the inverse -x-x^3-x^5-...-x^(n-2)(≡1+x^2+x^4+...+x^(n-1)) in mod 1+x+...+x^(n-1). (You can find the inverse, for

R[x]/(1-x^n), then the operation can be regarded as a mapping a↦a+x^i(x^-1+2+x).
Therefore the problem reduces to finding an f that satisfies the following:
a+f(x^-1+2+x)≡c(1+x+...+x^(n-1)) (mod 1-x^n) for some c in R

reduce 1 query somehow. For example, we can:
・omit the first query after the first step; we already know its parent is node 1.
・determine the parent without making a query once the number of the candidates becomes 1.
E:Consider the indexing to be 0-based. Let's view cyclic array a as an element of

n-(k+1), and the parent check fails at most k-1 times.
In all n+k-2 queries are performed. If the count of the nodes left (n-(k+1)) is 1, the parent check never fails and the count of queries does not exceed the limit.
So let's assume n-(k+1)>=2 ⇔ k<=n-3. Then we have n+k-2 <= 2n-5. We need to

queue.
Once it turn out that a candidate is not the parent to be searched for, it cannot be the parent of any nodes either, so ignore it afterward.
The count of queries are evaluated as follows:
Let the degree of node 0 be k. The first step makes (k-1)+1 queries.
The count of the nodes left is

Two-pointer technique.
D: The sequence 0,1,...,n-1 forms a BFS-ordering. Consider finding p_v for v=2,3,... in order. First find all the children of node 0 by querying for (1,v) iteratively.
Then make queries for v with a candidate of its parent iteratively while maintaining the candidates in a

・the unchanged elements form a (consecutive) subarray. (By shifting the choice with the maximum fixed, you can always convert the choice to a consecutive one.)
Now the condition imposed is that, when only considering the unchanged elements, the sum of the two smallests is larger than the largest.

C: Let array a sorted. First consider narrowing the search space. It is sufficient to consider only the cases where:
・there exists an element whose value doesn't change throughout the operations.
・only the maximum value among the unchanged elements is used for the assignments.

と

す

。長さP未満、P以上の2通りを考慮して計算。
TREESFUN343:操作可能な頂点同士を結ぶと二部グラフだから、二部グラフの片方を*-1すると操作前後で総和は不変。二部グラフの連結性が調べられればよく、重心分解してUFを頑張る。

2位でした。
以下自分の解法です。

COUNTSUB343:Lを固定した時、sum(A[L,R))<=NであるようなRはO(√N)個
COUNTARR343:操作によって総XORは不変だから総XORが0であることが必要であり、これで十分。N-1個自由に選んだ上で最後の要素で調整する。
FINDPERM343:AをN個の区間と見なす。後ろほど「内側」の区間であればよく、左端昇順とかにすればうまくいく。
CONSTPERM343:最小値と最大値の間を全部達成可能。最小値の場合の順列をもとにうまく作る
MINOP343:scoreは、長さP未満なら総和で、長さP以上なら長さPの部分配列の和の最大値

✅CodeChefの文字列を含む世界初のTweet

なんとなくTOKIMEKIの方が軽く感じる