A. Sports Betting
難しい．読解：長さ $10^9$ の 01 文字列 $S$ に対して $(S_a, S_{a+1})=(x,y)$ という予想をいくつかする．全部外れることがありえないようにできるか．
頻度列になおしたときに，$4$ があれば勝ちです（サンプル）．
頻度列になおしたときに，$(2,1,1,1,2)$ のような列があれば勝ちです．最初の $2$ で $(0,0),(1,0)$ と予想すれば，次が $1$ であると分かっているつもりで残りを考えればよくなります．先頭が $1$ であると分かっていて頻度 $1$ があるとき，やはり $(1,0)$ と聞けば，次が $1$ であるとしてよくなります．これで勝てることが分かります．
こういうのを含まない中で最も非自明なのが $(3,1,1,1,1,\ldots,1)$ のタイプだと思いますが，常に次の文字の可能性として片方しか消せないので勝てないです．
B. Baggage Claim
それぞれ挿入できるマスの選択肢の個数が 0, 1, 2 のどれかです．0 個の選択肢だと答は 0 です．そうでないとき，2 択の関係をグラフ上の辺で表します．次の問題に帰着されます：
- 頂点に非負整数が書かれているグラフがある．各辺に対して一方に +1 する．すべての頂点が 1 以下になる方法は何通りありますか？
連結成分ごとに解きます．頂点数を $V$, 辺数を $E$ として最初に書かれている数の和を $x$ とすると，$E+x\leq V$ が必要です．次のパターンがあります．
- $x=0, E=V-1$：木です．$0$ にする頂点を決めるとそこから順に一意に決まるので，$V$ 通り．
- $x=1,E=V-1$ 上の議論と同様にちょうど $1$ 通りであることが分かります．
- $x=0,E=V$：unicyclic graph です．葉から確定していき，サイクル上の辺について $2$ 通りの選択肢ができます．
C. Bermuda Triangle
直角三角形を辺で折り返して無限に並べていきます．次の問題になります：
- 最初に $x,y$ 座標がともに $N$ の倍数になるところを考える（なければ -1 を返す）．そこまでの線分が $x=kN$, $y=kN$, $x+y=(2k+1)N$, $x-y=(2k+1)N$ などの直線と交わる回数を求めよ．
$v_x,v_y$ は最大公約数で割っておきます．$x+t\cdot v_x\equiv 0\pmod{N}$, $y+t\cdot v_x\equiv 0\pmod{N}$ を解いて最小の $t$ を求めます．あとは，適当な区間内にある $N$ の倍数や $2N$ の倍数を数える問題に帰着されます．実装によってはここの帰着で $x+y=(2k+1)N$ に乗っているかなどの場合分けが発生すると思います．
D. Homework
$n=2^km$ として，$m$ bit の行ベクトルが $2^k$ 個並んでいると思います．これに対する行基本変形が実は何でもできます．swap も行加算 $3$ 回でできることに注意．
$(a,b,c,d)\to (a,b,ac,bc)\to (a,ab,ac,bd)\to (a,ab,c,ad)\to (a,ab,c,ad)$ のような要領で，隣の subtree 内のひとつのノードに何かを足せるので，subtree size で帰納法をすることにして，足す前後に subtree 内での swap をしてやれば好きなものを好きなところに足せることが示せます．
よって，$(2^k,m)$ 行列ふたつが行基本変形でうつりあうかどうかを確認すればよいです．標準形になおして一致判定すればよいです．$O(\min(2^k,m)n)$ 時間ですが bitset で高速化可能です．
E. Clearing the Snowdrift
最大値から順に操作していくとしてよいです．
$01$ 列（最初すべて 0）に対する次のクエリ処理に帰着されます．
- ひとつの値を $1$ に変更する
- 長さ $d$ の区間をいくつか置いて $1$ を全部被覆するときの最小コストを求める．
後者の問題は貪欲法で解けます．次の有向木での $0, N$ の距離を求めればよいです．
- $i$ 番目の要素が $0$ ならば $i$ から $i+1$ に重み $0$ の辺
- $i$ 番目の要素が $1$ ならば $i$ から $\min(i+d,N)$ に重み $1$ の辺
これは link cut tree でできます．
F. Lost Luggage
結局次のネットワークでの最大流を求めることになります．
- source から $(0,j)$ に容量 $S_j$ の辺
- $(i,j)$ から $(i+1,j-1)$ に容量 $a_{i,j}$ の辺
- $(i,j)$ から $(i+1,j)$ に容量 $b_{i,j}$ の辺
- $(i,j)$ から $(i+1,j+1)$ に容量 $c_{i,j}$ の辺
最小カットを求めることにします．$M\times N$ グリッドの各セルについて $0$ または $1$ のどちらであるかを決めることになります．最後の行の 01 列を状態とすれば，$O(M\cdots 2^{2N}\cdot poly(N))$ 程度の計算量の dp で解けます．
これは最後の $2N$ マスの状態を考えていますが，最後の $N+1$ マス程度の状態だけ持てばよいです．グリッドの dp を行ごとではなく 1 マスずつ進めていく手法で，$O(MN\cdot 2^N)$ 時間になります．
