# 競プロ講習会第5回 Web資料

#### ◎問題セット
https://codeforces.com/contestInvitation/d4b2461e98073f639a5d30ae0f8d81598891fa4b

#### ◎公式解説
##### A～C問題
https://codeforces.com/blog/entry/79517
##### D～O問題
https://codeforces.com/gym/103119/attachments/download/13796/2020icpc-macau-analyze.pdf

## ◎解説(Fまで)

### A. Required Remainder

:::spoiler **◎解説**

$A = \lfloor n / x \rfloor \times x$ とします。
この時、$A$ は $n$ 以下の最大の $x$ の倍数になっています。

この時、答えの候補は $A+y , A-x+y$ のどちらかです。
前者が $n$ 以下であれば前者を、そうでなければ後者を出力すればよいです。

:::

:::spoiler **◎実装例(python3)**

tt = int(input())

for loop in range(tt):

    x,y,n = map(int,input().split())

    A = n // x * x
    if A+y <= n:
        print (A+y)
    else:
        print (A-x+y)

:::

---

### B. Multiply by 2, divide by 6

:::spoiler **◎解説**

値を、以下のような形式で表します。
$2^a \times 3^b \times c$ ($c$は2,3の倍数でない)
さらに、値 $k$ を上の形式で表したときの$a,b,c$を $a_k,b_k,c_k$ とします。

さて、問題中の二種類の操作は以下のように言い換えられます。

* 2を掛ける操作
$2^a \times 3^b \times c$ → $2^{a+1} \times 3^b \times c$ に変更する。

* 6で割る操作
$2^a \times 3^b \times c$ → $2^{a-1} \times 3^{b-1} \times c$ に変更する。ただし、$a,b > 0$ の時しかこの操作を行えない。

まず、$c$を変更する手段はありません。そのため、$c_n$ が1ではない場合、最終的な値を1にはできないので `-1` を出力します。

最終的な値を1にするためには、以下のような方法を取るのが最適です。
1. 2を掛ける操作を繰り返し、$a = b$ にする。
2. 6を割る操作を繰り返して、$a = b = 0$ にする。

最初から $a > b$ の場合、どのように操作しても $a=b$ にできないので、`-1`を出力します。
そうでない場合、操作1を $b_n - a_n$ 回行い、操作2を $b_n$ 回行うので、答えは $2b_n - a_n$ です。

:::

:::spoiler **◎実装例(python3)**

tt = int(input())

for loop in range(tt):

    n = int(input())

    an = 0
    bn = 0
    cn = n
    
    while cn % 2 == 0:
        an += 1
        cn //= 2
    
    while cn % 3 == 0:
        bn += 1
        cn //= 3
    
    if cn != 1 or an > bn:
        print (-1)
    else:
        print (2*bn-an)

:::

---

### C. Move Brackets

:::spoiler **◎解説**

"(" を 1 、 ")" を -1 と変換し, 数列 $a$ とします。

$b_i = a_1 + a_2 + ... + a_i$ と定義された数列$b$を考え、 $b$ の最小値を $\mathrm{min}(b)$ とします。

1. $0 \le \mathrm{min}(b)$ の時、最初からregular bracket sequenceなので、答えは0です。
2. そうでない場合、答えは $-\mathrm{min}(b)$ です。

具体的には、以下のように操作することで以上の最小値を達成できます。
1. 前から$b$を見ていき、$b_i < 0$ の場合、 $i$ 番目にある閉じかっこにチェックを付け、$i$ 以降の全ての $j(j > i)$ について、 $b_j$ に1を加える。
2. チェックを付けた全ての閉じかっこを一番後ろに移動する。

:::

---

### D. Random Permutation

:::spoiler **◎解説**

全ての $p$ についての条件を満たす確率を求め、その総和を計算すると求める答えになります。(この考え方を主客転倒と呼びます)

ある $p$ について、条件を満たす$a$の個数は、$\prod_{ i = 0 }^n (n-p_i+1)$ であり、$p$ は順列であるためこの値は $n!$ と等しいです。$a$ は $n^n$ 通りありうるため、ある $p$ が条件を満たす確率は $n! / n^n$ であることが分かります。

$p$ は $n!$ 個あるため、求める答えは $n!n! / n^n$ です。

整数型だとオーバーフローするため、浮動小数点型を利用しましょう。

:::

---

### E. Artifacts

:::spoiler **◎解説(解説してません)**

頑張って読解をして、書くだけです。
記述が曖昧なところがあります(特に%関連のところ)。
とても酷い問題なので、この問題を解き直す時間は他の問題に充てましょう。

:::

---

### F. Fixing Networks

:::spoiler **◎解説**

まず、$d = 0, d = 1$ の場合を処理しておきます。
$d = 0$ の時、$n = c$ ならば`Yes`であり、そうでない場合`No`です。
$d = 1$ の時、$n = 2c$ ならば`Yes`であり、そうでない場合`No`です。
構成は、適当に2頂点ずつペアにして、連結成分にしていけばよいです。

さて、以下のような部分問題を考えてみます。

* 頂点数が$m$、全ての頂点の次数が$d$である連結な単純無向グラフを構成せよ。

これは、$m,d$ がともに奇数の場合は構成できません。 全ての頂点の次数が$d$である頂点数$m$のグラフでは、辺の数を$e$とすると、$2e = md$ が成り立ちます。しかし、$m,d$が共に奇数の場合、左辺は偶数・右辺は奇数となり等式が成立しないからです。

また、$m \le d$ の場合も、構成できません。ある頂点からは$d$本の辺がそれぞれ別の頂点につながっている必要がありますが、そのためには最低でも$d+1$個の頂点がグラフに必要だからです。

条件を満たしている場合、以下のようにグラフを構築できます。
1. 頂点を円周上に等間隔に並べる。
2. $d$ が奇数の場合、ちょうど反対側にある頂点と辺を結ぶ。
3. 以下の操作を全ての頂点 $v$ について行う。
* 頂点 $v$ に関して、その頂点から時計回りに $\lfloor d/2 \rfloor$ 個先までの頂点全てに対して、$v$ との間の辺を引く。

このようにすることで、部分問題を解くことができました。

さて、元の問題を考えてみます。部分問題が解ける条件を守りつつ、$n$ 個の頂点を $c$ グループに分けます。まず、頂点数が少なすぎると構成できないので、なるべく均等に頂点を分けるのが最適であることが分かります。さらに、$m,d$ が共に奇数になってはいけない条件を考慮すると、以下のように分けるのが最適となります。

* $d$ が偶数の場合: なるべく頂点を均等に分配する。
* $d$ が奇数の場合: $n$ 個の頂点を2個ずつペアにし、ペアを単位にして頂点を均等に分配する。($n$ が奇数の場合、構成不可)

あとは、各グループの部分問題を解けばよいです。

:::