AtCoder

公式解説と全然違うことをしている……。

問題リンク

https://atcoder.jp/contests/agc027/tasks/agc027_d

問題概要

$N$ が与えられます。次のような $N \times N$ 行列 $a$ を構築してください。

• $1\le a_{ij}\le 10^{15}$
• $a_{ij}$ は distinct
• 隣接する要素 $x, y$ について、$\max(x,y) \% \min(x,y)$ の値は正かつ全て同じ

制約

• $2\le N \le 500$

エスパーです。正直こっちのほうが分かりやすいです。

厳密ではありませんが証明はちゃんとつけました。

問題リンク

https://atcoder.jp/contests/arc129/tasks/arc129_d

問題概要

長さ $N$ の整数列 $(A_1, \dots, A_N)$ があります。この整数列の両端は繋がっています。

$A_{i-1}, A_i, A_{i+1}$ にそれぞれ $-1,2,-1$ を何回か足すことによって $A_i$ を全て $0$ にできるか判定し、できるなら最小回数を求めて下さい。

制約

• $3\le N\le 200000$
• $-100\le A_i \le 100$
• 入力は全て整数

なんか全然公式解説と違うことしてました……。

問題リンク

https://atcoder.jp/contests/arc046/tasks/arc046_d

問題概要

$H$ 行 $W$ 列からなるグリッドグラフがあります。

このグラフにおいて、$(i,j)$ から $((i+1) \bmod H, j)$ または $(i,(j+1) \bmod W)$ に移動できます。

マス $(0,0)$ からスタートして全てのマスを通り、$(0,0)$ に戻ってくるような経路の数を $\bmod 10^9+7$ で数え上げてください。

制約

$1\le H,W\le 10^6$

問題リンク

https://atcoder.jp/contests/zone2021/tasks/zone2021_f

問題概要

$N=2^n$ 個の頂点 $0,1,2,\dots,N-1$ について、$N-1$ 個の辺 $(i,j)$ を張って全域木を構成したいです。ただし、$(i,j)$ について、$i\oplus j$ が $A_1,A_2,\dots,A_M$ のいずれかと一致するような辺 $(i,j)$ は張れません。

全域木が構成できるか判定し、出来る場合は構成の仕方を $1$ つ示してください。

制約

• $N=2^n$ として、$1\le n\le 18$
• $0\le M\le N-1$
• $0\lt A_1\lt A_2\lt\dots\lt A_M\lt N$

最近似た問題を見ていたのでその解説を見て難しい解法にハマりました。

Editorial と同じ解法と、自分の解法を両方紹介します。

問題リンク

https://atcoder.jp/contests/abc198/tasks/abc198_e

問題概要

$N$ 頂点の木が与えられます。頂点 $i$ は色 $C_i$ で塗られています。

頂点 $1$ から $x$ への最短パスに色 $C_x$ が頂点 $x$ 以外に現れないような頂点を良い頂点と呼びます。良い頂点を列挙してください。

制約

• $2\le N\le 10^5$
• $1\le C_i\le 10^5$
• 与えられるグラフは木

久々に ABC でやったらいけないミスした……。

問題リンク

https://atcoder.jp/contests/abc198/tasks/abc198_d

問題概要

覆面算 $S_1+S_2=S_3$ を解いてください。

制約

• $1\le |S_i|\le 10$
• $S_i$ は英小文字のみからなる。