Educational Codeforces Round 108のきろく

Codeforces 競技プログラミング Educational Codeforces Round 参戦記

問題文和訳はこちら

A. Red and Blue Beans / Красные и синие мармеладки

赤い豆の方が数が少ないとします(多い場合は赤と青を入れ替える)。このとき r 個の小包に分けることができ、各ポケットに青豆を 1 個以上 d+1 個以下入れることができるので b \leq r(d+1) のとき条件を満たします。

B. The Cake Is a Lie / Торт - это ложь

どの経路を辿ったとしてもセル (n,\,m) へ到達するのにかかる費用は nm-1 burle となります。以下はその証明です。

n = m = 1 のとき 1 \cdot 1 - 1 = 0 より成立。
n = 1 または m = 1 のとき経路は1通り(それぞれずっと右、下)であり、それぞれ費用は m-1 = 1 \cdot m -1, n-1= n \cdot 1 -1 より成立します。
これら以外のセル (n,\,m) については n + m = l についての数学的帰納法で示せます。l-1 について成立を仮定します。このマスに辿り着くには

  • セル (n,\,m-1) から右に1マス
  • セル (n-1,\,m) から下に1マス

のいずれかであり、このとき費用は帰納法の仮定を利用してそれぞれ n(m-1) - 1 + n = nm -1, (n-1)m - 1 + m = nm -1 より成立するため、これで証明ができました。

C. Berland Regional / Берляндский отбор

大学 i の学生数を c_i とすると、チームメンバー数が k のとき \displaystyle \left\lfloor \frac{c_i}{k} \right\rfloor チームができ、\displaystyle \left\lfloor \frac{c_i}{k} \right\rfloor k 人が参加します。各大学について強い順に学生をソートし、累積和をとっておくことで高速に計算することができます。

D. Maximum Sum of Products / Максимальная сумма произведений

全ての部分列について計算すると組み合わせが O(n^2) で、和の計算が O(n) より O(n^3) なので間に合いません。
反転する部分列の中心を固定し、幅を 2 (両方向に 1)ずつ大きくすることで和の計算(更新)を O(1) に落とすことができ、間に合うようになります。

E. Off by One / Сдвиг на один: 未提出

2重の意味でグラフなのかこれ。さっぱりです。

F. Chests and Keys / Сундуки и ключи (実行時間制限: 3 sec): 未提出

ゲームはやっぱり苦手...

結果、感想

f:id:Flkanjin:20210503220636p:plain
Highest更新!! Dまで速く通せたのが幸いでした

Educational Codeforces Round 108 問題文和訳

Codeforces 競技プログラミング Codeforces 和訳 Educational Codeforces Round 和訳

A. Red and Blue Beans / Красные и синие мармеладки

テストごとの時間制限: 1秒
テストごとのメモリ制限: 256 MB
入力: 標準入力
出力: 標準出力
r 個の赤い豆と b 個の青い豆があります。次のような方法でそれらをいくつか(場合によっては1つでも可)の小包に分けたいと思っています。各小包について

  • 少なくとも1つの赤い豆をふくむ (つまり、赤い豆の個数 r_i \gt 1)
  • 少なくとも1つの青い豆をふくむ (つまり、青い豆の個数 b_i \gt 1)
  • 赤と青の豆の個数の差は d 以下 (つまり、|r_i - b_i| \leq d)

全ての豆を分配することができるでしょうか?

入力

1行目には単一の整数 t (1 \leq t \leq 1000) が与えられる、これはテストケースの個数である。

各テストケースの1行目にして唯一の行には3つの整数 r,\,b,\,d (1 \leq r,\,b \leq 10^9, 0 \leq d \leq 10^9) が与えられる、これらは赤と青の豆の個数と各小包内の個数の最大絶対差である。

出力

各テストケースについて、全ての豆を分配できる場合、YESと出力せよ。そうでなければNOと出力せよ。

各文字はどの活字ケースで出力してもよい(したがって、例えばyEs, yes, Yes, YESは全て肯定の答えとして見做される)。

入出力例

4
1 1 0
2 7 3
6 1 4
5 4 0
YES
YES
NO
NO

注記

1つ目のテストケースでは、赤い豆1個と青い豆1個で小包を1つ作ることができます。絶対差は |1-1| = 0 \leq d となります。

2つ目のテストケースでは、2つの小包を作ることができます。1つ目の小包には赤い豆1個と青い豆4個、2つ目の小包には赤い豆1個と青い豆3個が入ります。

3つ目のテストケースでは、b=1 なので、赤豆6個と青豆1個の小包を1つしか作ることができません。絶対差は |6-1| = 5 \gt d となってしまいます。

4つ目のテストケースでは、d=0 なので、それぞれの小包には同じ数の赤い豆と青い豆が入っているはずですが、r \neq b です。

B. The Cake Is a Lie / Торт - это ложь

テストごとの時間制限: 2秒
テストごとのメモリ制限: 256 MB
入力: 標準入力
出力: 標準出力
n \times m の格子があります。貴方はセル (1,\,1) に立っていて、セル (n,\,m) がゴールです。

貴方は右や下の隣接するセルに移動することができます。言い合えれば、セル (x,\,y) に立っているとすると、次のことを行うことができます。

  • セル (x,\,y+1) へ右に移動する。費用としてx burle*1かかる
  • セル (x+1,\,y) へ下に移動する。費用としてy burleかかる

ちょうど k burleでセル (n,\,m) に到達することができるでしょうか?

入力

1行目には単一の整数 t (1 \leq t \leq 100) が与えられる、これはテストケースの個数である。

各テストケースの1行目にして唯一の行には3つの整数 n,\,m,\,k (1 \leq n,\,m \leq 100; 0 \leq k \leq 10^4) が与えられる、これらは格子の大きさと支払わなければならないちょうどの金額である。

出力

各テストケースについて、ちょうど k burleでセル (n,\,m) に到達することができる場合、YESと出力せよ。そうでなければNOと出力せよ。

各文字はどの活字ケースで出力してもよい(したがって、例えばyEs, yes, Yes, YESは全て肯定の答えとして見做される)。

入出力例

6
1 1 0
2 2 2
2 2 3
2 2 4
1 4 3
100 100 10000
YES
NO
YES
NO
YES
NO

注記

1つ目のテストケースでは、すでに目的セルにいるので、0 burleかかります。

2つ目、3つ目、4つ目のテストケースでは、(1,\,1) から (2,\,2) への経路は2つあります: (1,\,1) \rightarrow (1,\,2) \rightarrow (2,\,2) と (1,\,1) \rightarrow (2,\,1) \rightarrow (2,\,2) です。どちらもコストは 1+2=3 burleなので、これが唯一の金額です。

5つ目のテストケースでは、(1,\,1) から(1,\,4) への道は1つしかなく、コストは 1+1+1=3 burleです。

C. Berland Regional / Берляндский отбор

テストごとの時間制限: 2秒
テストごとのメモリ制限: 256 MB
入力: 標準入力
出力: 標準出力
Поликарп*2はBerland*3ICPC地域大会の主催地です。Berlandには 1 から n までの番号が附いた n 個の大学があります。Поликарпはこの地域の全ての競技プログラマを知っています。学生は n 人いて、i 番目の学生は大学 u_i に在籍していて、そのプログラミングスキルは s_i です。

Поликарп、これからルールを決めなければなりません。特に、1チームのメンバー数です。

1チームの大きさを整数 k とした時、各大学は最も強い(プログラミングスキル s が最も高い) k 人を第一チームに、次に強い k 人を第二チームに、と言う風にチームに送り込むことをПоликарпは知っています。残った学生が k 人に満たない場合は、チームを組むことができません。1チームも送り出さない大学があるかもしれないことに注意してください。

地域の強さとは、その場にいるすべてのチームのメンバーのスキルの合計です。チームが1つもない場合は、強さは 0 です。

1 から n まで k をそれぞれ選んだ時の地域の強さを求めるПоликарпの手助けをしてください。

入力

1行目には単一の整数 t (1 \leq t \leq 1000) が与えられる、これはテストケースの個数である。

各テストケースの1行目には単一の整数 n (1 \leq n \leq 2 \cdot 10^5) が与えられる、これは大学や学生の数である。

各テストケースの2行目には n 個の整数 u_1,\,u_2,\,\dots,\,u_n (1 \leq u_i \leq n) が与えられる、これらは i 番目の学生が在籍している大学である。

各テストケースの3行目には n 個の整数 s_1,\,s_2,\,\dots,\,s_n (1 \leq s_i \leq 10^9) が与えられる、これらは i 番目の学生のプログラミングスキルである。

全てのテストケースでの n の和が 2 \cdot 10^5 を超えないことは保証されている。

出力

各テストケースについて、n 個の整数を出力せよ: これらはチームの大きさをそれぞれ選んだ時の地域の強さ、すなわち、現在の全てのチームのメンバーのスキルの合計である。

入出力例

4
7
1 2 1 2 1 2 1
6 8 3 1 5 1 5
10
1 1 1 2 2 2 2 3 3 3
3435 3014 2241 2233 2893 2102 2286 2175 1961 2567
6
3 3 3 3 3 3
5 9 6 7 9 7
1
1
3083
29 28 26 19 0 0 0 
24907 20705 22805 9514 0 0 0 0 0 0 
43 43 43 32 38 43 
3083

注記

1つ目のテストケースでは、各 k について各大学のチームは次のようになります。

  • k = 1
    • 大学 1: [6],\,[5],\,[5],\,[3]
    • 大学 2: [8],\,[1],\,[1]
  • k = 2
    • 大学 1: [6,\,5],\,[5,\,3]
    • 大学 2: [8,\,1]
  • k = 3
    • 大学 1: [6,\,5,\,5]
    • 大学 2: [8,\,1]
  • k = 4
    • 大学 1: [6,\,5,\,5,\,3]

D. Maximum Sum of Products / Максимальная сумма произведений

テストごとの時間制限: 2秒
テストごとのメモリ制限: 256 MB
入力: 標準入力
出力: 標準出力
長さ n の2つの整数の配列 a,\,b が与えられます。

配列 a の部分列(連続した部分セグメント)を高々1つ反転させることができます。

和 \displaystyle \sum_{i=1}^{n} a_i \cdot b_i を最大化するような部分列を反転させることが課題です。

入力

1行目には1つの整数 n (1 \leq n \leq 5000) が与えられる。

2行目には n 個の整数 a_1,\,a_2,\,\dots,\,a_n (1 \leq a_i \leq 10^7) が与えられる。

3行目には n 個の整数 b_1,\,b_2,\,\dots,\,b_n (1 \leq b_i \leq 10^7) が与えられる。

出力

単一の整数を出力せよ、その整数は a の高々1つの部分列(連続した部分セグメント)を反転させたのちの和の可能な最大値である。

入出力例

5
2 3 2 1 3
1 3 2 4 2
29
2
13 37
2 4
174
6
1 8 7 6 3 6
5 9 6 8 8 6
235

注記

1つ目の入出力例では部分列 [4,\,5] を反転させることができます。すると、a = [2,\,3,\,2,\,3,\,1] で、2 \cdot 1 + 3 \cdot 3 + 2 \cdot 2 + 3 \cdot 4 + 1 \cdot 2 = 29 となります。

2つ目の入出力例では反転操作を行う必要がありません。13 \cdot 2 + 37 \cdot 4 = 174 となります。

3つ目の入出力例では部分列 [3,\,5] を反転させることができます。すると、a = [1,\,8,\,3,\,6,\,7,\,6] で、1 \cdot 5 + 8 \cdot 9 + 3 \cdot 6 + 6 \cdot 8 + 7 \cdot 8 + 6 \cdot 6 = 235 となります。

E. Off by One / Сдвиг на один

テストごとの時間制限: 2秒
テストごとのメモリ制限: 256 MB
入力: 標準入力
出力: 標準出力
無限の平面に n 点が存在します。i 番目の点は x_i \lt 0, y_i \lt 0 であるような 座標 (x_i,\,y_i) に位置します。座標は必ずしも整数とは限りません。

1回の操作で次のような操作を行うことができます。

  • 2点 a,\,b (a \neq b) を選ぶ
  • 点 a を (x_a,\,y_a) から (x_a +1,\,y_a) と (x_a,\,y_a +1) のいずれか一方に移動させる
  • 点 b を (x_b,\,y_b) から (x_b +1,\,y_b) と (x_b,\,y_b +1) のいずれか一方に移動させる
  • 2点 a,\,b を削除する

但し、この操作は a の新座標、b の新座標、(0,\,0) を通る直線が存在する場合のみ行うことができます。

そうでなければ、この操作は行われず点はそれぞれ元の座標 (x_a,\,y_a), (x_b,\,y_b) のままとなります。

幾つかの点が削除された後も点の番号は変わりません。一度削除された点はその後の操作では選択することができません。sl差の際には両方の点を移動させなければならず、元の座標のままにしておくことはできないことに注意して下さい。

最大何回操作を行うことができるでしょうか? どのような操作でしょうか?

答えが複数存在する場合は、そのいずれを出力してもいいです。

入力

1行目には1つの整数 n (1 \leq n \leq 2 \cdot 10^5) が与えられる、これは点の個数である。

続く n 行の i 番目には4つの整数 a_i,\,b_i,\,c_i,\,d_i (1 \leq a_i,\,b_i,\,c_i,\,d_i \leq 10^9) が与えられる。i 番目の点の座標は \displaystyle x_i = \frac{a_i}{b_i}, \displaystyle y_i = \frac{c_i}{d_i} である。

出力

1行目には単一の正位数 c を出力せよ、その数とは操作回数の最大値である。

続く n 行のそれぞれには1手の動きを記述する2つの整数 a,\,b (1 \leq a,\,b \leq n, a \neq b) を出力せよ、これらはその操作で差k序された点である。 a の新座標、b の新座標、(0,\,0) を通る直線が存在するような問題文の条件に従った塡 a,\,b の移動方法が存在しなければならない。削除された点が後の操作で選ばれることはない。

答えが複数存在する場合は、そのいずれを出力してもよい。操作や操作内の点は任意の順序で出力することができる。

入出力例

7
4 1 5 1
1 1 1 1
3 3 3 3
1 1 4 1
6 1 1 1
5 1 4 1
6 1 1 1
3
1 6
2 4
5 7
4
2 1 1 1
1 1 2 1
2 1 1 2
1 2 1 2
1
1 2
4
182 168 60 96
78 72 45 72
69 21 144 63
148 12 105 6
1
2 4

注記

1つ目の入出力例の点とその移動は次のようになります。
f:id:Flkanjin:20210502003137p:plain

F. Chests and Keys / Сундуки и ключи

テストごとの時間制限: 3秒
テストごとのメモリ制限: 512 MB
入力: 標準入力
出力: 標準出力
AliceとBobはゲームをしています。Aliceは n 個の宝箱(i 番目の宝箱には a_i 枚のコインが入っている)と m 個の鍵(j 番目の鍵は b_j 枚のコインでBobに売ることができる)を持っています。

まず、Aliceは宝箱にいくつかの錠前を附けます。m 種類の錠前が存在し、j 種類目の錠前は j 番目の鍵でしか開けることができません。i 個目の宝箱に j 種類目の錠前を附けるには c_{i\,j} ドル支払わなければなりません。Aliveは各宝箱に任意の数の様々な種類の錠前をつけることができます(0であってもよい)。

そして、BobはAliceからいくつかの鍵(0でも全てでもよい)をカイ、開ける音ができる各空箱を開けます(その宝箱についている全ての錠前に対応する鍵を持っている場合開けることができる)。Bobに利益は開けた宝箱の中にあるコインの合計枚数とAliceから鍵を買うのに用いたコインの合計枚数の差です。Bobの利益が厳密に正である(0よりも大きい)場合、彼がこのゲームで勝利します。そうでなければ、Aliceが勝利します。

Aliceは、Bobがどのカギを買っても常にAliceが勝てる(Bobが正の利益を得ることができない)ようにいくつかの宝箱にいくつかの錠前を附けたいです。もりとん、彼女は錠前の購入にかける金額はできるだけ少なうしたいです。彼女がゲームに勝てるかどうか、勝てるなら何ドル用いなければならないかを判別する彼女の手助けをしてください。

入力

1行目には2つの整数 n,\,m (1 \leq n,\,m \leq 6) が与えられる、これらはそれぞれ宝箱と錠前の個数である。

2行目には n 個の整数 a_1,\,a_2,\,\dots,\,a_n (1 \leq a_i \leq 4) が与えられる、ここで、 a_i は i 番目の宝箱に入っているコインの枚数である。

3行目には n 個の整数 b_1,\,b_2,\,\dots,\,b_n (1 \leq b_j \leq 4) が与えられる、ここで、 b_j はBobが j 番目の鍵をAliceから買うのに必要なコインの枚数である。

そして n 行が続く。その i 行目には m 個の整数 c_{i,\,1},\,c_{i,\,2},\,\dots,\,c_{i,\,m} (1 \leq c_{i,\,j} \leq 10^7) が与えられる、ここで、 c_{i,\,j} はAliceが i 番目の宝箱に j 種類目の錠前をつつけるのに支払わなければならないドル金額である。

出力

Aliceが勝つことが保証されない(どのように錠前を宝箱に付けても、Bobは必ず正の利益を得ることができる方法が存在する)場合、-1 を出力せよ。

そうでなければ、1つの整数を出力せよ、その数とはBobの行動に関わらずゲームに勝つためにAliceが支払わなければならない最小のドル金額である。

入出力例

2 3
3 3
1 1 4
10 20 100
20 15 80
205205
2 3
3 3
2 1 4
10 20 100
20 15 80
110
2 3
3 4
1 1 4
10 20 100
20 15 80
-1

注記

1つ目の入出力例では、Aliceは1番目の宝箱に種類 1 と 3 の錠前を、2番目の宝箱に種類 2 と 3 の錠前を附けます。

2つ目の入出力例では、Aliceは1番目の宝箱に種類 1 と 2 の錠前を、2番目の宝箱に種類 2 の錠前を附けます。

*1:бурль 架空の国Berlandの通貨

*2:露[pəlʲɪˈkarp]、ポリカルプ、ポリカープ、Polycarp: 古希Πολύκαρπος/po.lý.kar.pos/、ポリュカルポスに由来する人名

*3:Берлянд: 木やグラフに関する問題でしばしば登場する架空の国家

AtCoder Beginner Contest 199のきろく

AtCoder 競技プログラミング AtCoder Beginner Contest 参戦記

AtCoder Beginner Contest 199（Sponsored by Panasonic）で3問しか解けませんでした...

A - Square Inequality (100点)

いつぞやの誤差を気にする問題のような問題文ですがこちらは元から整数なので素直に A^2 + B^2 と C^2 を計算して大小比較すればいいです。

B - Intersection (200点)

整数 x が満たす条件は \max A \leq x \leq \min B であるので答えは \max\{\min B - \max A + 1,\,0\} となります。

C - IPFL (300点)

問題文の通りに実装すると T_i = 2 のクエリで毎回 O(N) となるので O(NQ) となり、間に合いません。前半後半を入れ替えたかどうかというフラグを管理し、T_i = 2 のクエリが来るたびにこのフラグを反転させます。T_i = 1 のクエリで入れ替える文字に注意。

D - RGB Coloring 2 (400点)

各頂点が赤、黄、青の 3 色なので全て試せば 3^N 通り、正しいかどうかを確かめるの込みで O(3^N M) で間に合わない...ってやっているうちに時間が来てしまいました...

まず、連結成分ごとに独立で、それぞれの値の積が答えとなります。DFSやBFSを用いて連結成分に属す頂点をvectorに入れていったとき、最初の頂点以外は辺で結ばれた頂点がそれより前に少なくとも1つ存在し、そのためその頂点と同じ色は考えなくともいいため、連結成分の頂点数を v とすると高々 2^v 通りしか考えなくてもいいことが分かります(最初の頂点は任意の色がいけるが、どれをとっても対称なので1色に固定し3倍すればいい)。そのため全体の計算量が O((N+M)2^N) となり、間に合うようになります。

E - Permutation (500点)

2 \leq N \leq 18 という制約から O(N \cdot N!) は通らないな、という感じでした。

O((N+M) 2^N) は通るのでbitDPなどを考えます。S を 1 から N までの整数の集合の部分集合とし、

{\mathrm{dp}}_{S} = (最初の\, |S|\, 個のみを考えたときに\, X_i \leq |S|\, である条件を全て満たす場合の数)
としたとき、{\mathrm{dp}}_{\emptyset} = 1 であり、x \notin S について S \cup \{x\} が X_i \leq |S|+1 であるような条件を全て満たすときに S から S \cup \{x\} に遷移できるため、それに従って遷移させる ({\mathrm{dp}}_{S \cup \{x\}} \texttt{+=}\, {\mathrm{dp}}_{S}) ことで答え {\mathrm{dp}}_{\{1,\,2,\,\dots,\,N\}} が求まります。

F - Graph Smoothing (600点)

期待値問題なので、コンテスト中はあまり考えていませんでした。後で考えてみれば後半3問の中で一番可能性があった...

行列累乗です。\boldsymbol{A} = (A_1,\,A_2,\,\dots,\,A_N)^{\top} とし、N \times N 行列 \boldsymbol{M} = (M_{i,\,j}) を考えます。各頂点 v の次数を d_v とします。
M_{v,\,v} について頂点 v に隣接する頂点が選ばれたとき A_v への自分自身の寄与が半分に減るため M_{v,\,v} =\displaystyle 1 - \frac{d_v}{2M} となります。
M_{v,\,u} については頂点 u と v を結ぶ辺が選ばれたとき A_v への A_u の寄与が \dfrac{1}{2} 増えるため M_{v,\,u} =\displaystyle \frac{1}{2M} となります。
その他の要素は全て 0 です。

このとき \boldsymbol{M}^i\boldsymbol{A} が i 回の操作後の頂点の数となるため、\boldsymbol{M}^K\boldsymbol{A} の各要素が答えとなります。

結果、感想

f:id:Flkanjin:20210429221053p:plain
後半が解けず、1時間以上何も提出しない時間を過ごしてしまいました...

AtCoder Regular Contest 117のきろく

AtCoder AtCoder Regular Contest 競技プログラミング 参戦記

AtCoder Regular Contest 117で黄パフォ!!

A - God Sequence (200点)

A = B のとき E_i = i\hspace{0.5cm} (1 \leq i \leq A), E_{A+i} = -i\hspace{0.5cm} (1 \leq i \leq B) とすれば条件を満たします。
A \gt B のとき E_i = i\hspace{0.5cm} (1 \leq i \leq A), E_{A+i} = -i\hspace{0.5cm} (1 \leq i \leq B-1), \displaystyle E_{A+B} = -\sum_{i = B}^{A}i = -\frac{A(A+1) - B(B-1)}{2} とすれば条件を満たします。
A \lt B のとき正負の役割を入れ換え、 E_i = i\hspace{0.5cm} (1 \leq i \leq B), E_{B+i} = -i\hspace{0.5cm} (1 \leq i \leq A-1), \displaystyle E_{A+B} = \sum_{i = A}^{B}i = \frac{B(B+1) - A(A-1)}{2} とすれば条件を満たします。

B - ARC Wrecker (400点)

建物を並び替えても状況を変わらず、両者での景観は一対一対応するため、A をソートし、A_0 = 0 を追加したものを考えます。
隣り合う建物の高さについて、その差が大きくなることはなく、他の建物とは独立にその間の値を全てとることができます。そのため答えは \displaystyle \prod_{i=1}^{N} (A_i - A_{i-1} + 1) となります。

C - Tricolor Pyramid (600点)

青、白、赤の色を数 0,\,1,\,2 と対応させ、a_{i,j} を 下から i 段目の左から j 番目のブロックの色に対応する数とします。
このとき 9 通りのパターンを全て試すことで a_{i+1,j} = -(a_{i,j} + a_{i,j+1}) \bmod{3} が成り立つことが分かります。これは二項係数の漸化式によく似た式で、実際の所 a_{i,j} = \displaystyle \left( (-1)^{i-1}\sum_{k = j}^{j + i -1} {}_{i-1}\mathrm{C}_{k-1}\, a_{1,k}\right) \bmod{3} となるため、a_{N,1} = \displaystyle \left( (-1)^{N-1}\sum_{k = 1}^{N} {}_{N-1}\mathrm{C}_{k-1}\, a_{1,k}\right) \bmod{3} となり、これを対応する色にすれば答えですが、各 {}_{n}\mathrm{C}_{r} を \bmod{3} で求める場合、いつものように逆元を用いる方法では r \geq 3 のとき常に 0 となってしまい、WAとなってしまいます。そこで蟻本の262, 263ページに記載されている方法で求めることになります。

D - Miracle Tree (600点): 未提出

直径とか求めるのかな、ACしたら追記します。

E - Zero-Sum Ranges 2 (900点、実行時間制限: 5 sec): 未提出

N がかなり小さい...

F - Gateau (900点、実行時間制限: 3 sec): 未提出

苺がいっぱい...

結果、感想

f:id:Flkanjin:20210419110509p:plain
黄パフォで久しぶりのHighest更新!! はやく1800越えしたいなぁ

Educational Codeforces Round 107のきろく

Codeforces 競技プログラミング Educational Codeforces Round 参戦記

問題文和訳はこちら

A. Review Site / Сайт отзывов

タイプ i のレビュアーの人数を a_i とします。
タイプ 1 と 3 のレビュアーを第1サーバに、タイプ 2 のレビュアーを第2サーバに送ることで a_1 + a_2 個の「いいね」を得ることができます。タイプ2のレビュアーが「いいね」を押すことはないのでこれが最大です。

B. GCD Length / Длина НОД

x = 10^{a-1}, y = \displaystyle 10^{c-1} \sum_{i = 0}^{b-c} 10^i =\underbrace{1\cdots1}_{b-c+1}\underbrace{0\cdots0}_{c-1} とすると x は a 桁、y は b 桁であり、\displaystyle\gcd\left(10^{a-c},\,\sum_{i = 0}^{b-c} 10^i\right) = 1 であるから、\gcd(x,\,y) = 10^{c-1} であり、10^{c-1} は c 桁であることから条件を満たします。

C. Yet Another Card Deck / Очередная задача про колоду карт

各色について一番上にあるカードしか考えなくてよく、それを配列などに覚えておく。各クエリ毎に覚えていた値を出力し、また、その値よりも小さなお値のものを全て+1 し、その値を 1 にすることで実装することができます。

D. Min Cost String / Строка минимальной стоимости

連続2文字は k^2 通りあるので 2^k 文字目と 1 文字目のものも含めて 2^k 文字で全ての組み合わせを網羅するものを考えます。k = 1 の時はaで k = 2 の時はabbaです。もっと大きい k については漸化式的に文字列を作っていきます。実例として k = 4 から k = 5 への遷移で説明します。k = 4 のときの文字列のひとつはabcacdadbddccbbaとなります。このとき同じ文字が連続しているところのうち一つを選び(ここではdd)、次のような文字列を挿入します: eaebeceed。これは(新しく追加される文字+連続の文字以外の文字)の全パターン+新しく追加される文字×2+連続の文字という文字列です。このようにしてベースとなる文字列ができました。この文字列を何度も連結させたものについて先頭の n 文字を出力すればよいです。

E. Colorings and Dominoes / Раскраски и домино (実行時間制限: 3 sec): 未提出

さっぱりです。

F. Chainword / Чайнворд (実行時間制限: 3 sec): 未提出

ゲーム系の問題苦手です...

結果、感想

f:id:Flkanjin:20210413222137p:plain
Highest近くにまで恢復できました。D問題が思いついたときは本当にこれで良いんやろうかってなっいた(まぁ、実装バグらせて2WAしているのですが)のでちゃんと通ってよかったです。

Educational Codeforces Round 107 問題文和訳

Codeforces 競技プログラミング Codeforces 和訳 Educational Codeforces Round 和訳

A. Review Site / Сайт отзывов

テストごとの時間制限: 2秒
テストごとのメモリ制限: 256 MB
入力: 標準入力
出力: 標準出力
貴方は将来の映画監督で、最初の映画を公開したところです。また、「いいね」と「ひどいね」の2つのボタンのついたシンプルなサイトを立ち上げました。

しかし、このサイトは内部的にはそれほど単純ではありません。サーバが2台あり、「いいね」と「ひどいね」をそれぞれのサーバが別々にカウントしています。

n 人のレビュアーが1人ずつサイトを訪れます。各レビュアーは以下のタイプのいずれかです。

  • タイプ 1: レビュアーは映画を見て気に入り、「いいね」ボタンを押す
  • タイプ 2: レビュアーは映画を見て気に入らず、「ひどいね」ボタンを押す
  • タイプ 3: レビュアーは映画を見ないで、自分のいるサーバの「いいね」と「ひどいね」の現在の数を見て、どちらのボタンを押すかを決める。「ひどいね」が「いいね」より多い場合、この映画に対して「ひどいね」を押す。そうでない場合、この映画に対して「いいね」を押す。

各レビュアーは1回のみ映画に対して評価を行います。

サーバが2つあるので、映画にできるだけ多くの「いいね」が付くように投票を操作することができます。レビュアーがサイトを訪れたときその人のタイプが分かるので、第1サーバに送るか第2サーバに送るかを選ぶことができます。

各レビュアーをどちらのサーバに送るかを決めたとき、両方のサーバで集められる「いいね」の合計値の最大値はいくらでしょう?

入力

1行目には単一の整数 t (1 \leq t \leq 10^4) が与えられる、これはテストケースの個数である。

その後、t 個のテストケースについての記述が続く。

各テストケースの1行目には単一の整数 n (1 \leq n \leq 50) が与えられる、これはレビュアーの人数である。

各テストケースの2行目には n 個の整数 r_1,\,r_2,\,\dots,\,r_n (1 \leq r_i \leq 13) が与えられる、これらはサイトを訪れる順に並べたレビュアーの種類である。

出力

各テストケースについて、単一の整数を出力せよ、その整数とは各レビュアをどちらのサーバーに送るかを決めたとき、両方のサーバで集められる「いいね」の合計値の最大値である。

入出力例

4
1
2
3
1 2 3
5
1 1 1 1 1
3
3 3 2
0
2
5
2

注記

入出力例の1つ目のテストケースでは、唯一のレビュアをどちらのサーバにも送ることができますが、どちらにしても「ひどいね」を押します。この映画は「いいね」の評価を受けません。

入出力例の2つ目のテストケースでは、レビュアーを全員第1サーバに送ることができます。

  • 1人目のレビュアーが「いいね」を押す
  • 2人目のレビュアーが「ひどいね」を押す
  • 最後のレビュアーが「ひどいね」が「いいね」を上回っていなことを確認し、「いいね」を押す

「いいね」は合計で2つです。別の方法として、1人目のレビュアーと2人目のレビュアーを第1サーバに、最後のレビュアーを第2サーバに送ることもできます。

  • 1人目のレビュアーが第1サーバで「いいね」を押す
  • 2人目のレビュアーが第1サーバで「ひどいね」を押す
  • 最後のレビュアーが第2サーバで「いいね」も「ひどいね」もないことを確認し、「いいね」を押す

B. GCD Length / Длина НОД

テストごとの時間制限: 2秒
テストごとのメモリ制限: 256 MB
入力: 標準入力
出力: 標準出力
3つの整数 a,\,b,\,c が与えられます。

次の条件を満たす2つの正整数 x,\,y (x \gt 0, y \gt 0) を求めて下さい。

  • 先行ゼロを除いた x の十進数表現は a 桁である
  • 先行ゼロを除いた y の十進数表現は b 桁である
  • 先行ゼロを除いた gcd(x,\,y) の十進数表現は c 桁である

gcd(x,\,y) は整数 xと y の 最大公約数(greatest common divisor, GCD)*1を表します。

xと y を出力してください。答えが複数存在する場合、そのいずれかを出力してください。

入力

1行目には単一の整数 t (1 \leq t \leq 285) が与えられる、これはテストケースの個数である。

続く t 行のそれぞれには3つの整数 a,\,b,\,c (1 \leq a,\,b \leq 9, 1 \leq c \leq \min(a,\,b)) が与えられる、これらは数字の長さの条件である。

与えられた制約のもとで、全てのテストケースに対して答えが存在することは証明できる。

入力についての追加制約: 全てのテストケースは異なるものである。

出力

各テストケースについて2つの整数を出力せよ、その2つの整数は以下の条件を満たす x,\,y (x \gt 0, y \gt 0) である。

  • 先行ゼロを除いた x の十進数表現は a 桁である
  • 先行ゼロを除いた y の十進数表現は b 桁である
  • 先行ゼロを除いた gcd(x,\,y) の十進数表現は c 桁である

入出力例

4
2 3 1
2 2 2
6 6 2
1 1 1
11 492
13 26
140133 160776
1 1

注記

入出力例では次の通りになります。

  1. gcd(11,\,492) = 1
  2. gcd(13,\,26) = 13
  3. gcd(140133,\,160776) = 21
  4. gcd(1,\,1) = 1

C. Yet Another Card Deck / Очередная задача про колоду карт

テストごとの時間制限: 2秒
テストごとのメモリ制限: 256 MB
入力: 標準入力
出力: 標準出力
上から下に番号が振られた n 枚のカードデッキがあります。つまり，一番上のカードのインデックスは 1で、一番下のカードのインデックスは n となります。各カードにはそれぞれの色があり、i 枚目の色は a_i です。

q 個のクエリを処理しなければなりません。j 番目のクエリは整数 t_j で表されます。各クエリについて次のようなことを行わなければなりません。

  • デッキ内で色 t_j である最も上のカード、即ち、最小のインデックスを持つカードを見つける
  • 見つけたカードの位置を出力する
  • そのカードを取り出し、デッキの一番上に置く

入力

1行目には2つの整数 n,\,q (2 \leq n \leq 3 \cdot 10^5; 1 \leq q \leq 3 \cdot 10^5) が与えられる、これらはデッキ内のカードの枚数とクエリの個数である。

2行目には n 個の整数 a_1,\,a_2,\,\dots,\,a_n (1 \leq a_i \leq 50) が与えられる、これらはカードの色である。

3行目には q 個の整数 t_1,\,t_2,\,\dots,\,t_q (1 \leq t_j \leq 50) が与えられる、これらはクエリの色である。クエリではデッキ内に存在する色のみを尋ねられることは保証される。

出力

q 個の整数を出力せよ、それらは各クエリに対する答えである。

入出力例

7 5
2 1 1 4 3 3 1
3 2 1 1 4
5 2 3 1 5

注記

入出力例の説明:

  1. デッキは [2,\,1,\,1,\,4,\,\underline{3},\,3,\,1] で、色 t_1 = 3 である最初のカードの位置は 5 である。
  2. デッキは [3,\,\underline{2},\,1,\,1,\,4,\,3,\,1] で、色 t_2 = 2 である最初のカードの位置は 2 である。
  3. デッキは [2,\,3,\,\underline{1},\,1,\,4,\,3,\,1] で、色 t_3 = 1 である最初のカードの位置は 3 である。
  4. デッキは [\underline{1},\,2,\,3,\,1,\,4,\,3,\,1] で、色 t_4 = 1 である最初のカードの位置は 1 である。
  5. デッキは [1,\,2,\,3,\,1,\,\underline{4},\,3,\,1] で、色 t_5 = 4 である最初のカードの位置は 5 である。

D. Min Cost String / Строка минимальной стоимости

テストごとの時間制限: 2秒
テストごとのメモリ制限: 256 MB
入力: 標準入力
出力: 標準出力
文字列 s のコストを s_i = s_j かつ s_{i+1} = s_{j+1} を満たすインデックスの組 i,\,j (1 \leq i \lt j \leq |s|) の個数と定義しましょう。

2つの正整数 n,\,k が与えられます。ラテン文字の最初の k 文字のみを含む長さ n の全ての文字列の中で、可能な限り最小コストの文字列を求めて下さい。そのような最小コストの文字列が複数存在する場合は、そのいずれかを出力してください。

入力

唯一の行には2つの整数 n,\,k (1 \leq n \leq 2 \cdot 10^5; 1 \leq k \leq 26) が与えられる。

出力

n 文字で構成され、その各文字がラテン文字の最初の k 文字のうちの1つであり、これらの文字列の中でコストが最小となるような文字列 s を出力せよ。このような文字列が複数ある場合は、そのうちのいずれかを出力せよ。

入出力例

9 4
aabacadbb
5 1
aaaaa
10 26
codeforces

E. Colorings and Dominoes / Раскраски и домино

テストごとの時間制限: 3秒
テストごとのメモリ制限: 512 MB
入力: 標準入力
出力: 標準出力
n \times m 個のセルに分割されている大きな長方形のボードがあります(n 行 m 列)。各セルは白か黒です。

各白セルを赤か青で塗ります。自明ですが、白セルの数を w とすると塗り方は 2^w 通りあります。

ボード上の白セルを塗ったのち、次のようなルールに従って最大数のドミノを置いていきます。

  • 各ドミノは隣接する2つのセルを覆う
  • 各セルは高々1枚のドミノで覆われる
  • ドミノを横向きに置いた(1行の2つセルを覆う)場合、赤セルのみを覆う
  • ドミノを縦向きに置いた(1列の2つセルを覆う)場合、青セルのみを覆う

ボードの値を置くことができるドミノの最大枚数とします。可能な 2^w 通りの塗り方全てについての値の合計を計算してください。個の和が巨大になる可能性があるので、modulo 998\,244\,353 で出力してください。

入力

1行目には2つの整数 n,\,m (1 \leq n,\,m \leq 3 \cdot 10^5; nm \leq 3 \cdot 10^5) が与えられる、これらはそれぞれ行と列の数である。

そののち、n 行が続き、各行には m 文字の文字列が与えられる。i 個目の文字列の j 文字目は i 行目の j 番目のセルが黒のとき *、そうでないときoである。

出力

1つの整数を出力せよ、その数とは可能な 2^w 通りの塗り方についてボードの値の和を 998\,244\,353 で割った余りである。

入出力例

3 4
**oo
oo*o
**oo
144
3 4
**oo
oo**
**oo
48
2 2
oo
o*
4
1 4
oooo
9

F. Chainword / Чайнворд

テストごとの時間制限: 3秒
テストごとのメモリ制限: 256 MB
入力: 標準入力
出力: 標準出力
チェーンワードはクロスワードの特殊な種類です。大体のクロスワードと同様に、文字を入れるセルと、その文字が何であるかを示すヒントがあります。

チェーンワードの文字セルは1列に並べられています。この課題では長さ m のチェーンワードを考えます。

チェーンワードのヒントとは、互いに交差せず、m 個の文字セルを全てカバーするような、一連のセグメントのことです。各セグメントには、対応するセルにある単語の説明が含まれています。

奇妙なことに実際にはヒントは2つあります: 1つは文字セルの上の行のセグメント列で、もう1つは文字セルの下の行のセグメント列です。列が異なる場合は、答えの曖昧さを解消するのに役立っています。

n 単語の辞書が当たられます、各語は小文字のラテン文字から成ります。全ての語は互いに相異なります。

チェーンワードのインスタンスは次のような3つ組です。

  • m 文字の小文字のラテン文字の文字列
  • 第1ヒント: 各セグメントに対応する文字が辞書内の単語となるようなセグメント列
  • 第2ヒント: 各セグメントに対応する文字が辞書内の単語となるような別のセグメント列

セグメント列は必ずしも異なるものである必要はないことに注意してください。

チェーンワードの2つのインスタンスは、異なる文字列または異なる第1ヒントまたは異なる第2ヒントを持つ場合、異なるものと見做されます。

チェーンワードの異なるインスタンスの数を数えます。この数はかなり大きくなるかもしれないので、modulo 998\,244\,353 で出力してください。

入力

1行目には2つの整数 n,\,m (1 \leq n \leq 8, 1 \leq m \leq 10^9) が与えられる、これらは辞書の単語数と文字セルの数である。

続くn 行のそれぞれには単語が与えられる、これらは小文字のラテン文字 5 文字以内の空でない文字列である。全ての単語は互いに異なる。

出力

1つの整数を出力せよ、与えられた辞書に対する長さ m の異なるチェーンワードのインスタンスの数を 998\,244\,353 で割った余りである。

入出力例

3 5
ababa
ab
a
11
2 4
ab
cd
4
5 100
a
aa
aaa
aaaa
aaaaa
142528942

注記

ここにあるのは、1つ目の入出力例についての有効なチェーンワードの全てのインスタンスです。
f:id:Flkanjin:20210413181239p:plain
文字の上の赤い線は第1ヒントのセグメントを、文字の下の青い線は第2ヒントのセグメントを示しています。

2つ目の入出力例では、以下の文字列が考えられます: "abab", "abcd", "cdab", "cdcd"。ヒントは全て、最初の2文字と最後の2文字をカバーするセグメントです。

G. Chips on a Board / Фишки на доске

テストごとの時間制限: 5秒
テストごとのメモリ制限: 512 MB
入力: 標準入力
出力: 標準出力
AliceとBobは n 行 m 列から成る長方形のボードを持っています。各行にはチップがちょうど1枚置かれています。

AliceとBobは次のようなゲームをします。2人は 1 \leq l \leq r \leq m である2整数 l,\,r を選び、列 lから列 r まで(区間の両端を含む)の部分のみが残るようにボードを切ります。つまり、列 l より左にある全ての列と列 r より右にある全ての列はもはやボードの一部ではなくなります。

ボードを切った後、ボードの残った部分(列 lから列 r までの部分)のチップを移動させます。交互に手を打ち、手を打てなかったプレイヤーがゲームに負けます。1手目はAlice、2手目はBob、3手目はAliceというように進行します。手を打つ際、プレイヤーはボード上のチップを1つ選び、任意の正の数のセル分左に移動させなければなりません(つまり、列 i にあったチップは列 j \lt i に移動させることができ、一番左の列にあるチップは選べない)。

AliceとBobは数の組 L_i,\,R_i を q 組持っています。そのような各ペアについて、l = L_i, r = R_i としたときに、どちらがゲームの勝者になるかを判別したいと思っています。これらのゲームは独立である(次のゲームのボードの状態には影響を与えない)と考えられ、AliceもBobも最適なプレーを行います。

入力

1行目には2つの整数 n,\,m (1 \leq n,\,m \leq 2 \cdot 10^5) が与えられる、これらはそれぞれ行と列の数である。

2行目には n 個の整数 c_1,\,c_2,\,\dots,\,c_n (1 \leq c_i \leq m) が与えられる、ここで c_i は i 行目のチップのある列のインデックスである(つまり、i 行目のチップは c_i 列目にある)。

3行目には1つの整数 q (1 \leq q \leq 2 \cdot 10^5) が与えられる。

そののち、q 行が続き、その i 行目には2つの整数 L_i,\,R_i (1 \leq L_i \leq R_i \leq 2 \cdot m) が与えられる。

出力

q 文字の文字列を出力せよ。 i 文字目は、l = L_i, r = R_i のゲームでAliceが勝った場合はA、Bobが勝った場合はBとする。

入出力例

8 10
1 3 3 7 4 2 6 9
7
2 3
1 3
1 4
1 10
5 10
8 10
9 10
BAAAAAB

*1:原文では英語、ロシア語のWikipediaへのリンク

Codeforces Round #714 (Div. 2) 問題文和訳

Codeforces 競技プログラミング Codeforces 和訳 Codeforces Div. 2 和訳

A. Array and Peaks / Массив и пики (500点)

テストごとの時間制限: 1秒
テストごとのメモリ制限: 256 MB
入力: 標準入力
出力: 標準出力
n 整数の列は 1 から n までの全ての整数をちょうど1個ずつ含むとき順列と呼ばれます。

2つの整数 n,\,k が与えられるので、ちょうど k 個のピークをもつ 1 から n までの数の順列 a を構築してください。大きさ n の配列 a のインデックス i は 1 \lt i \lt n かつ a_i \gt a_{i-1} かつ a_i \gt a_{i+1} であるとき、ピークといいます。そのような順列が存在しない場合は、-1 と出力してください。

入力

入力の1行目には単一の整数 t (1 \leq t \leq 100) が与えられる、これはテストケース数である。

それから t 行が続き、そのそれぞれには空白で区切られた2つの整数 n (1 \leq n \leq 100), k (0 \leq k \leq n) が与えられる、これらは配列の長さとピークの数である。

出力

t 行出力せよ。各テストケースについて、与えられた長さとピークの数を持つ順列がない場合は、-1 と出力せよ。そうでない場合は、1 から n までの数の順列を形成し、ちょうど k 個のピークを持つような空白で区切られた n 個の整数を1行に出力せよ。

答えが複数存在する場合、そのいずれかを出力せよ。

入出力例

5
1 0
5 2
6 6
2 1
6 1
1 
2 4 1 5 3 
-1
-1
1 3 6 5 4 2

注記

入出力例の2つ目のテストケースでは、配列 a = [2,\,4,\,1,\,5,\,3] となります。ここでインデックス i = 2 と i = 4 がピークとなります。これは (a_2 \gt a_1, a_2 \gt a_3) で、 (a_4 \gt a_3, a_4 \gt a_5) であるからです。

B. AND Sequences / Последовательности И (1250点)

テストごとの時間制限: 2秒
テストごとのメモリ制限: 256 MB
入力: 標準入力
出力: 標準出力
n (n \geq 2) 個の非負整数の列 a_1,\,a_2,\,\dots,\,a_n は 1 から n-1 までの全ての i について次の条件が成立するとき、よい配列という。
a_1 \: \& \: a_2 \: \& \: \dots \: \& \: a_i = a_{i+1} \: \& \: a_{i+2} \: \& \: \dots \: \& \: a_n
ここで、\& はビットAND*1を表します。

大きさ n (n \geq 2) の配列 a が与えられます。列 a_{p_1},\,a_{p_2},\,\dots,\,a_{p_n} がよい配列となるような 1 から n までの数の順列 p の個数を求めて下さい。この数は大きくなる可能性があるので、modulo 10^9 + 7 で出力してください。

入力

入力の1行目には単一の整数 t (1 \leq t \leq 10^4) が与えられる、これはテストケース数である。

各テストケースの1行目には単一の整数 n (2 \leq n \leq 2 \cdot 10^5) が与えられる、これは配列の大きさである。

各テストケースの2行目には n 個の整数 a_1,\,a_2,\,\dots,\,a_n (0 \leq a_i \leq 10^9) が与えられる、これらは配列の要素である。

全てのテストケースでの nの和が 2 \cdot 10^5 を超えないことは保証されている。

出力

t 行出力せよ、ここで、i 行目には i 番目のテストケースでの良い順列の個数を 10^9 + 7 で割った余りを出力せよ。

入出力例

4
3
1 1 1
5
1 2 3 4 5
5
0 2 0 3 0
4
1 3 5 1
6
0
36
4

注記

1つ目のテストケースでは、全ての数が同じなので、どのような順列をとっても良い配列になります。1 から 3 までの数の順列は次のように合計で 6 通り存在します: [1,\,2,\,3], [1,\,3,\,2], [2,\,1,\,3], [2,\,3,\,1], [3,\,1,\,2], [3,\,2,\,1]。

2つ目のテストケースでは、よい配列となるような順列が存在しないことを証明することができます。

3つ目のテストケースでは、よい配列となるような順列が合計で 36 通り存在しますそのうち1つが順列 [1,\,5,\,4,\,2,\,3] であり、このとき列は s = [0,\,0,\,3,\,2,\,0]となります。これがよい配列となるのは以下の通りです。

  • s_1 = s_2 \: \& \: s_3 \: \& \: s_4 \: \& \: s_5 = 0
  • s_1 \: \& \: s_2 = s_3 \: \& \: s_4 \: \& \: s_5 = 0
  • s_1 \: \& \: s_2 \: \& \: s_3 = s_4 \: \& \: s_5 = 0
  • s_1 \: \& \: s_2 \: \& \: s_3 \: \& \: s_4 = s_5 = 0

Add One / Добавь единицу (1500点)

テストごとの時間制限: 1秒
テストごとのメモリ制限: 256 MB
入力: 標準入力
出力: 標準出力
整数 n が与えられます。それに m 回操作を適用させなければなりません。

1回の操作では、数の各桁 d を d+1 の十進数表現に置き換えなければなりません。例えば、1912 は1回の操作を適用させると 21023 となります。

m 回の操作を適応させた後の n の長さを求めなければなりません。この数は大きくなる可能性があるので、modulo 10^9 + 7 で出力してください。

入力

入力の1行目には単一の整数 t (1 \leq t \leq 2 \cdot 10^5) が与えられる、これはテストケース数である。

各テストケースの唯一の行には2つの整数 n (1 \leq n \leq10^9, [tex:m (1 \leq m \leq 2 \times 10^5) が与えられる、これらは初期状態の数と操作回数である。

出力

各テストケースについて結果として得られる数の長さを 10^9 + 7 で割った余りを出力せよ。

入出力例

5
1912 1
5 6
999 1
88 2
12 100
5
2
6
4
2115

注記

1つ目のテストケースについて、1912 は 1 回の操作の後 21023 となり、その長さは 5 となります。

2つ目のテストケースについて、5 は 6 回の操作の後 21 となり、その長さは 2 となります。

3つ目のテストケースについて、999 は 1 回の操作の後 101010 となり、その長さは 6 となります。

4つ目のテストケースについて、88 は 2 回の操作の後 1010 となり、その長さは 4 となります。

D. GCD and MST / НОД и МОД (2000点)

テストごとの時間制限: 2秒
テストごとのメモリ制限: 256 MB
入力: 標準入力
出力: 標準出力
n (n \geq 2) 個の正整数から成る配列 a と整数 p が与えられます。頂点 i と j (i \lt j) の間の辺が次のようにして追加される 1 から n までの番号がついた n 個の頂点からなる重み付き無向グラフを考えます。

  • gcd(a_i,\,a_{i+1},\,a_{i+2},\,\dots,\,a_j) = min(a_i,\,a_{i+1},\,a_{i+2},\,\dots,\,a_j) である場合、i から j の間に重さ min(a_i,\,a_{i+1},\,a_{i+2},\,\dots,\,a_j) の辺が存在する
  • i + 1 = j である場合、i と j の間に重さ p の辺が存在する

ここで gcd(x,\,y,\,\dots) は整数 x,\,y,\,\dots の最大公約数(greatest common divisor, GCD)*2を表します。

上記の条件の両方を満たす場合、i と j の間には多重辺が存在し、何方の条件も満たさない場合、i と j の間には辺が存在しないことに注意してください。

目標は、このグラフの最小全域木(minimum spanning tree, MST)*3の重みを求めることです。

入力

入力の1行目には単一の整数 t (1 \leq t \leq 10^4) が与えられる、これはテストケース数である。

各テストケースの1行目には2つの整数 n (2 \leq n \leq 2 \cdot 10^5), p (1 \leq p \leq 10^9) が与えられる、これらは頂点数とパラメータ p である。

各テストケースの2行目には n 個の整数 a_1,\,a_2,\,a_3,\,\dots,\,a_n (1 \leq a_i \leq 10^9) が与えられる、これらは配列の要素である。

全てのテストケースでの nの和が 2 \cdot 10^5 を超えないことは保証されている。

出力

t 行出力せよ。各テストケースでについて対応するグラフの重さを出力せよ。

入出力例

4
2 5
10 10
2 5
3 3
4 5
5 2 4 9
8 8
5 3 3 6 10 100 9 15
5
3
12
46

注記

ここでは、例題の4つのテストケースのグラフを示しています(グラフの可能なMSTの辺はピンク色で示されています)。
テストケース1について
f:id:Flkanjin:20210412183948p:plain
テストケース2について
f:id:Flkanjin:20210412184017p:plain
テストケース3について
f:id:Flkanjin:20210412184118p:plain
テストケース4について
f:id:Flkanjin:20210412184143p:plain

E. Cost Equilibrium / Ценовой баланс (2750点)

テストごとの時間制限: 1秒
テストごとのメモリ制限: 256 MB
入力: 標準入力
出力: 標準出力
配列の全ての要素が等しい場合、その配列は美しいといいます。

以下の手順で、配列を任意の回数変換することができます。

  1. 2つのインデックス i,\,j (1 \leq i,\,j \leq n) と整数 x (1 \leq x \leq a_i) を選ぶ。i をソースインデックス、j をシンクインデックスとする
  2. i 番目の要素を x だけ減らし、j 番目の要素を x だけ増やす。i 番目と j 番目で得られる値はそれぞれ a_i - x, a_j + x となる
  3. この操作のコストは x \cdot |j - i| である
  4. ここで、i がシンクインデックス、j がソースインデックスになることはなくなる

変換の総コストはステップ 3 の全てのコストの合計です。
例えば、配列 [0,\,2,\,3,\,3] は総コスト 1 \cdot |1-3| + 1 \cdot |1-4| = 5 で美しい配列 [2,\,2,\,2,\,2] に変換できます。

美しい配列に変換することができ、その変換のコストが一意に定まる配列をバランス型といいます。言い換えれば、美しい配列に変換するための最小のコストは、最大のコストに等しいものです。

非負整数から成る長さ n の配列 a_1,\,a_2,\,\dots,\,a_n が与えられます。貴方の仕事は、与えられた配列の並べ替えであるバランス型の配列の数を求めることです。要素が異なる位置が存在する場合2つの配列は異なる配列とみなされます。答えが大きくなる可能性があるため、modulo 10^9+7 で出力して下さい。

入力

1行目には単一の整数 n (1 \leq n \leq 10^5) が与えられる、これは配列の大きさである。

2行目には n 個の整数 a_1,\,a_2,\,\dots,\,a_n (0 \leq a_i \leq 10^9) が与えられる。

出力

単一の整数を出力せよ、これはバランス型である並び替えの数を 10^9 + 7 で割った余りである。

入出力例

3
1 2 3
6
4
0 4 0 4
2
5
0 11 12 13 14
120

注記

1つ目の入出力例では、値 3 のインデックスをソース、値 1 のインデックスをシンクと考えることができるので、[1,\,2,\,3] は有効な並び替えです。したがって、変換後は美しい配列 [2,\,2,\,2] となり，総コストは 2 となります。これが美しい配列になる唯一の変換であることを示すことができます。同様に他の並び替えについても調べることができます。

2つ目の入出力例では、[0,\,0,\,4,\,4] と [4,\,4,\,0,\,0] がバランス型である並び替えです。

3つ目の入出力例では、すべての並び替えがバランス型です。

F. Swapping Problem / Задача об обмене (3500点)

テストごとの時間制限: 2秒
テストごとのメモリ制限: 512 MB
入力: 標準入力
出力: 標準出力
大きさ n の2つの配列 a,\,b が与えられます。b の2つの要素を最大1回だけ入れ替える(またはそのままにする)ことができ、次の値を最小化しなければなりません。
\displaystyle \sum_{i} |a_i - b_i|
この和の可能な最小値を求めて下さい。

入力

1行目には単一の整数 n (1 \leq n \leq 2 \cdot 10^5) が与えられる。

2行目には n 個の整数 a_1,\,a_2,\,\dots,\,a_n (1 \leq a_i \leq 10^9) が与えられる。

3行目には n 個の整数 b_1,\,b_2,\,\dots,\,b_n (1 \leq b_i \leq 10^9) が与えられる。

出力

\displaystyle \sum_{i} |a_i - b_i| の最小値を出力せよ。

入出力例

5
5 4 3 2 1
1 2 3 4 5
4
2
1 3
4 2
2

注記

1つ目の入出力例では、配列 b の1番目と5番目の要素を入れ替えて [5,\,2,\,3,\,4,\,1] にすることができます。

従ってその和の可能な最小値は |5-5| + |4-2| + |3-3| + |2-4| + |1-1| = 4 となります。

2つ目の入出力例では、1番目と2番目の要素を入れ替えることができます。つまり、答えは 2 となります。

*1:原文では英語、ロシア語のWikipediaへのリンク

*2:これも原文では英語、ロシア語のWikipediaへのリンク

*3:英語、ロシア語のWikipediaの最小全域木のページへのリンク