---
# System prepended metadata

title: UCUP 0-0

---

###### tags: ucup

# WF 46,47th


## B
社員が2N人いて、(1,1),..,(N,1), (1,2),..,(N,2) と名前がついている
W日労働する。それぞれの日に対し、各iに対し、(i,1)と(i,2)のうちちょうど一人が出社する

人(i,a)と(j,b) の不仲度は、その二人が同時に出社した日が最大でどのくらい空いてるか
会社全体の不仲度は、i != j なる各 (i,a,j,b) に対する不仲度の最大

会社全体の不仲度を最小化してください　復元あり


## C = V
各面に整数が書かれたダイスD,Eがあったときに、
score(D,E)を、(一回振ってDのほうが大きい確率) + (同じ確率)*0.5 と定義する

ダイスD1,D2が与えられる。score(D1,D2) > 0.5 が保証されている

問題1: score(D3,D1) >= 0.5 という条件下で score(D3,D2) を最小化
問題2: score(D2,D3) >= 0.5 という条件下で score(D3,D1) を最大化

https://atcoder.jp/contests/xmascon18/tasks/xmascon18_d

yo:

## D = T

二次元平面に二個ピラミッド(高さhの正方形すい)が置いてあるので、ピラミッドの頂点の間をトコトコ歩くときの最短距離　そう…

## E

## F


## H


## J = S
人がN人いて、橋の左側から右側に渡ろうとしている
人iが渡るのに t_i 分かかる
橋は同時にK人まで通れる
橋をグループで渡るときは最も遅い人に合わせた時間がかかる
懐中電灯がひとつあって、これを持った状態でしか橋は渡れない
全員右に行くまでの時間の最小

ほぼ既出: https://onlinejudge.u-aizu.ac.jp/beta/room.html#ACPC2021Day3/problems/H
解説: https://hcpc-hokudai.github.io/archive/acpc/2021/acpc2021_H.pdf

## K
各面に文字(26+10)が書かれた6面サイコロがd個ある
一回の操作で次のことができる: サイコロをいくつか選んで同時に振り直す(初回は全部振る)

ワードがW個与えられる。サイコロの目でワードをどれでもいいから一個作れるまでの操作の期待値は?
d <= 6

## Q
1, 2, ..., nの順列が与えられる。あなたは2個のスタックを持っていて、最初はどちらも空

- 順列に従って荷物が届く、あなたは各荷物について独立にランダムにスタックを選んで荷物をpushする

この後、i=1,2,...,nについて次を行う

- 片方のスタックから荷物をpopして逆のスタックにpushすることを繰り返し、荷物iがスタックの一番上に出てくるようにする
- 荷物iを取り除く

操作回数の総和の期待値を求めよ　double



## X

1-8の書かれたトランプ、計32枚のカードを使って4人ゲームをする

最初に各プレイヤーはカードを8枚ずつ配られて、次の操作を人1, 2, 3, 4, 1, 2, ...とする

- もし同じ数字のカードを4枚持っていたら、それを公開してゲームから取り除いてもよい(好きな回数)
- カードが0枚になったら消える
- そのカード自体は持っていないが、同じ数字のほかのカードを持っている、というカードを1枚選び、ほかの人にそのカードを持っているか聞く
- 聞かれた人がそのカードを持っていたらカードを渡す
- 持っていたらこの操作を繰り返す。持っていなかったら手番が終了する。

このゲームの操作列が与えられる。この操作列は、後述の嘘つきが混じっている可能性があるが、嘘つきに目をつぶればvalid。嘘つきなしと仮定したときにvalidかを判定、invalidの場合どの操作で初めて矛盾が起きるか？

嘘つき
- 自分が持っているカードを聞く
- 持ってるカードを聞かれたのに持ってないと嘘をつく


↑読解がニ箇所以上違うよ


## Z

nとkが与えられる。長さkの012文字列は3^k 通りあるが、この3^k 通りの文字列についての"頻度表"が与えられる。頻度の総和は2^n。次の条件を満たすn個の長さkの012文字列は存在するか？

n個の文字列それぞれについて選ぶか選ばないか決めて選んだ文字列の総和を(mod 3で)取る。選び方は2^n通りあるが、これについて結果の文字列の頻度表を作ると与えられたものに一致する

n <= 40
k <= 5

## R

n頂点m辺の単純無向グラフが与えられる。各頂点には整数が書かれたコマが一つずつ置いてあり、最初はb_iと書かれたコマが置いてある。

次の操作を好きな回数できる

- グラフの単純サイクルを一つ選ぶ。このサイクルに沿って頂点のコマをrotateする。

最終的に頂点iにコマe_iが置いてあるようにできるか？

https://atcoder.jp/contests/arc062/tasks/arc062_d
辺だけどほぼ一緒だろ多分


---
## --------------脳内Solved------------------


## I
図のように球面を分割する
各領域内の海の割合が与えられるので表面全体の海の割合を求めよ

そう...




## --------------Solved------------------

## G = P
ライト mod 3 のやつ
連結成分ごとに数通りしかない

## A = W
インタラクティブ
ジャッジが非負整数x,y,zを隠し持ってるので5回の質問で特定してください
投げれる質問: (a,b,c) -> ax+by+cz が返ってくる
ただしたかだか一回嘘を答えてくる可能性がある

どの３つをとっても独立なベクトルを5個聞いて、5C4のうちOKなやつを答える


## Y

バイナリ文字列に対して次の操作を好きな回数できる

- substringとしてSSを含むとき、片方を削除してSにする

最終的な文字列としてありえるもののうち、最も長さが短いもの(のうちいずれか一つ)を出力

どうせRLEして長さ3以下

## U

画像みたいに<->とLの二種類が書かれた線路が与えらえる　最大長のデカループを作りたい

S, Cともに偶数としていい

C = 4 (mod 8) -> S = 0,2,...
C = 2, 6 (mod 8) -> S = 2,4, ...?
