--- tags: GCJ --- # Google Code Jam 2021 Qualification Round 問題文和訳 簡単に ## A 順列 $L$ を以下の疑似コード (Python) でソートする ```python= def Reversort(L : List[int]): for i in range(len(L) - 1): j = argmin(L[i :]) reverse(L[i : j + 1]) ``` 4 行目で $j - i + 1$ のコストがかかる 合計コストは？ ## B `C`, `J`, `?` からなる文字列があり、`?` に `C` または `J` を代入 `CJ` と連続していると $X$ 点、`JC` と連続していると $Y$ 点のコストがかかる 最小コストは？ 注 : $X,Y$ が負になる場合を解くと +1 点 (30 点を取るならいらない) ## C A 問題において、$1, \dots, N$ の順列であって、コスト $C$ のものを構築 ## D $1, \dots, N$ をランダムに並び替えた数列 $x$ が隠されている インタラクティブ : $i, j, k$ を渡すと $x_i, x_j, x_k$ のうち中央値をとる index を教えてくれる $1, \dots, N$ を並べ替えた indices $i_1, \dots, i_N$ であって、$x_{i_1},\dots,x_{i_N}$ が昇順ソート または 降順ソート になっているものを求めよ 注 : interactive runner と testing tool を使うと手元で Hidden も動かせるよ 入出力の形式に十分注意してね ## E 100 人の参加者と 10000 問の問題がある。 $i$ 人目の rating は $S_i$ 、 $i$ 問目の difficulty は $Q_i$ 、これらは $[-3,3]$ の実数からランダムに選ばれる $i$ 人目が $j$ 問目を解く確率は [シグモイド関数](https://ja.wikipedia.org/wiki/%E3%82%B7%E3%82%B0%E3%83%A2%E3%82%A4%E3%83%89%E9%96%A2%E6%95%B0) を $f$ として $f(S_i - Q_j)$ それぞれの参加者がそれぞれの問題を解いたかどうかが与えられる。 100 人のうち 1 人はチーターで、解く確率が $\dfrac{1 + f(S_i - Q_j)}2$ になっている チーターの index を出力 $P$ ％ 以上のケースに正解せよ