A. Скрытый друг
問題概要．有向グラフが隣接リスト形式の入力で与えられる．$(i,j)$ 辺は存在しないが $(j,i)$ 辺はあるような $(i,j)$ を列挙せよ．
B. Code Review
よくわからないが $(a_i,b_i)$ が与えられて，$a_i\neq a_{i+1}$ であるような $b_i$ 以外の $b$ を出力？
C. #define Задача B …
define の列によって長さ $4^{25}$ の配列を作った．pos 番目の値を答えよという $Q$ クエリ．
D. Storage2
予想問題文
$(4,7)$ grid がある．ちょうど $K$ 個が $0$ で $N-K$ 個が $1$ である．列の和が $3$ 以上であるとき列を $1$ 埋めしてよい．行の和が $5$ 以上であるとき行を $1$ 埋めしてよい．
$K$ が与えられたとき, $(3,5)$ 部分について，$0$ がのこる確率およびその個数の期待値を求めよ．
$2^{28}$ 通り全探索して埋め込めばよいです．
E3. Контрольная сумма
問題概要．整数列の crc32 を保つように列を変更する．a[i], a[i+1], a[i+2], a[i+3] が変更されるので，a[j], a[j+1], a[j+2], a[j+3] をどう変更すればよいかを答えよ．
crc というのは 01 列があるときに，$\mathbb{F}_2$ 上の適当な多項式での剰余をとるハッシュのことのようです．crc32 といえば標準的な実装ではこれだという多項式も知られているようです．整数列を 01 列にするのは，b[i] = a[i/8]>>(i%8)&1 という要領でよいようです．私は crc32 を chatgpt に実装してもらってそれをもとに解きました．
結局 $x$ 倍して多項式剰余という反復をするだけです．$i$ 番目のビットを変えたときに $i+n$ 回目の反復で剰余がどうなっているか（$x^{n}\bmod f(x)$）を前計算しておきます．
F. Шардирование постов
問題：ソート列が $S$ 個与えられる．要素数が $a_i$ で合計 $10^5$ 個以下である．すべての列をあわせてみたときの $k$ th element を求めよ．
列の番号が $2$ の倍数のところで $k/2$ 番目を解いたあと $O(S)$ 回クエリするという雰囲気で計算すると $O(S\log K)$ 回になります．AC にはなりましたが定数倍の見積もりは $100$ 回で抑えられていなかったので少しあやしいかもしれません．
