はじめに
バチャの記録です
結果は $4$ ペナ全完
ペナ全部 G ゴミすぎる
本文
A. Do Not Be Distracted!
概要
英大文字からなる文字列が与えられる
同じ文字で連続していないものが存在するか判定せよ
解法
連続している同じ文字を圧縮した文字列を考える
すると, その文字列に同じ文字が二つ以上存在するかどうか判定すればいいことになる
B. Ordinary Numbers
概要
$1$ 以上 $n$ 以下の正整数で, すべての桁が同じ数字であるようなものがいくつあるか求めよ
解法
そのような数はそんなにないことが簡単にわかって, 高々 $9 \times 9$ 個くらい
すべて列挙すればよい
C. Not Adjacent Matrix
概要
$n \times n$ のグリッドの各マスに $1$ から $n^2$ までの整数を一つずつ書き込むことを考える
任意のマスについて隣接するマスに差の絶対値が $1$ になるような数が存在しないような書き込み方が存在するか判定し, 存在するなら一つ構築せよ
解法
$n = 2$ 以外なら可能
ちょっと実装迷った
グリッドを一マス飛ばし（市松模様のような感じ）に $1$ から順に書いていけばよい
D. Same Differences
概要
長さ $n$ の整数列 $a$ が与えられる
$i < j$ かつ $a_j - a_i = j-i$
をみたす $(i, j)$ の組の数を求めよ
解法
式を変形して
$a_i - i = a_j - j$
と書ける
$b_i = a_i - i$
という数列 $b$ を考えると, 問題は
$i < j$ かつ $b_j = b_i$
をみたす $(i, j)$ の組の数を求めよ
と言い換えられる
これは, std::map などを用いて各 $x$ について $b_i = x$ となる $i$ の数を求めればよい
E. Arranging The Sheep
概要
'.' と '*' からなる文字列が与えられる
'*' を隣と swap する という操作を繰り返してすべての '*' を連続させるとき, 操作の最小回数を求めよ
解法
文字列のうち, '*' であるようなインデックスを並べた数列を $a$ とする
例: "*.*...*.**" なら $a = [0, 2, 6, 8, 9]$
すると, 問題は
$a$ の好きな要素を選んで $+1$ または $-1$ する という操作を繰り返して, 任意の $i$ について $a_i+1 = a_{i+1}$ となるようにするとき, 操作の最小回数を求めよ
と言い換えられる
これは, D 問題のように変形して $b_i = a_i-i$ とすると
$b$ の好きな要素を選んで $+1$ または $-1$ する という操作を繰り返してすべての要素を一致させるとき, 操作の最小回数を求めよ
と言い換えられる
これは $b$ の中央値に揃えるのが最適
証明みたいな何か
$f(x) = b$ を $x$ に揃えるときの最小回数
とすると
$f(x) = \sum_i |b_i-x|$
と書けて, この関数の傾きは (広義)単調増加であることがわかる
図を書いたり微分したりすると, 中央値で最小値を取ることがわかる
F1. Guess the K-th Zero (Easy version)
概要
すべての要素が $0$ か $1$ であるような長さ $n$ の数列がある (が, 隠されている)
ある連続した区間の要素の和を聞く
ということが高々 $20$ 回できるとき, 前から $k$ 番目の $0$ がどこにあるかを求めよ
解法
答えがどこにあるのか を二分探索する
$[l, m)$ における区間和が $x$ であったとすると, その区間に含まれる $0$ は $x - (m-l)$ 個 これを $d$ とする
$k \le d$ なら $k$ 番目の $0$ は $[l, m)$ にある
$d < k$ なら $k$ 番目の $0$ は $[m, r)$ にある
F2. Guess the K-th Zero (Hard version)
概要
F1 と同じ問題を, 同じ数列に対し $t ( \le \min(n, 10^4))$ 回解く
また, 答えた位置の $0$ を $1$ に変更してそれ以降の $k$ を処理する
質問できる回数はすべて合計で $6 \cdot 10^4$ 回
解法
二分探索の過程を保存して, 同じものが呼ばれたらそれを参照することを考える
Segment Tree のようなものを作って逐次保存, 参照, 更新すればよい
G. To Go Or Not To Go?
概要
$n \times m$ のグリッド上を左上から右下まで移動するときの最短経路を求めよ
ただし,
- $a_{i,j} = -1$ ならそのマスは通れない
- その他のマスは, $w$ 時間かけて隣接するマスに移動できる
- $a_{i,j} = x ( > 0)$ なら, そのマスはワープできる
ワープにかかる時間は, $(i, j)$ から $(k, l)$ にワープするとき $a_{i,j}+a_{k,l}$
解法
すべてのワープマスを互いに結ぶ (クリークにする) と辺の数が最大で $(nm)^2$ のオーダーになってしまう
超頂点 $p$ を用意して, $(i, j)$ から $p$ にコスト $a_{i,j}$, $p$ から $(k, l)$ にコスト $a_{k,l}$ というような辺をはれば 辺の数は $nm$ のオーダーに収まる
そのようなグラフで Dijkstra 法 をすればよい
と思ったが TLEした (TLEコード)
なんとか $\log$ を落とすことを考える
ワープを無視すれば, 移動コストは一定なので BFS ができる
ここで, ワープを使う回数は高々一回であることがわかる (二回以上つかうなら, 一回目でその二回目の飛ぶ先に飛んでしまえばいい)
よって, 始点から終点, 始点からワープマス, 終点からワープマス までの距離を BFS で求めて $\min$ を取ればよい
これで $\Theta(nm)$ だがまだ TLE した
さすがにこれ以上のオーダー改善は不可能 (入力サイズが既に $\Theta(nm)$ ) なので, 入出力高速化とQCFium法を貼ってみると $1.2$ sec まで落ちた
おわりに
全完できたのはよかった
D,E みたいな問題は好きです
Gはさすがにひどくないですか？ TL $5$ sec じゃダメだったんですか...