AtCoder Beginner Contest 204のきろく

AtCoder Beginner Contest 204で久しぶりにレート上昇しました!

A - Rock-paper-scissors (100点)

3 人のじゃんけんであいこになるのは、全員同じ手を出すか、全員違う手を出した時なので、 x = y のときはその手、そうでないときは 3-x-y の手を出せばいいです。また、サーバルの出した手に対応する文字を z としたとき、x + y  + z \equiv 0 \pmod 3 となることを利用すると z = (6 - x - y) \bmod 3 となります。

B - Nuts (200点)

forifを組み合わせて答えを出すことができますが、各 i について足す数は \max\{A_i - 10,\,0\} であるのでこれを足していく方が多分少し短いです。

C - Tour (300点)

全頂点対について移動が可能かどうかなので、Warshall-Floyd法で...とすると O(N^3) なので間に合いません。
始点を固定した時同じ頂点を2度以上訪れないようにしたDFSやBFSを行うと、どの頂点も辺も高々1回しか通らないので O(N+M) でその始点から訪れることができるかどうか判別できるので、その始点を全て試して足して合わせてやることで O(N(N+M)) で判定することができます。

D - Cooking (400点)

コストをlong longにし忘れと辺を双方向につなぎ忘れによって3WA出してしまいました... これがなければ、青色復帰できたのに...

U = \{1,\,2,\,\dots,\,N\} を二つの集合 A_1,\,A_2空集合を許した分割を行ったときの \displaystyle\min \max\left\{\sum_{i \in A_1} T_i,\,\sum_{i\in A_2}T_i\right\} が答えです。分割の方法は 2^N 通り存在するため、全探索では間に合いません。
この問題は部分和問題であるためDPの利用を考えます。

{\mathrm{dp}}_{i,j} = (T_1,\,T_2,\,\dots,\,T_i \text{の部分和を\(j\)にすることができるかのbool値})
とすると {\mathrm{dp}}_{0,0} =\mathrm{true} であり、1 \leq ileq N について
{\mathrm{dp}}_{i,j}=\left\{
    \begin{array}{ll}
      {\mathrm{dp}}_{i-1,j} & (j < T_i)\\
      {\mathrm{dp}}_{i-1,j}\ \mathrm{OR}\ {\mathrm{dp}}_{i-1,j-T_i} & ({j \geq T_i})
    \end{array}
  \right.
が成り立ち、\displaystyle S = \sum_{i=1}^{N}T_i とすると \displaystyle \sum_{i\in A_2}T_i = S - \sum_{i\in A_1}T_i であるため、答えは \displaystyle\min_{{\mathrm{dp}}_{N,j} = \mathrm{true}}\max\{j, \,S-j\} が答えとなります。j の値は S 以下で S \leq N \displaystyle \max_i T_i \leq 10^5 であり、計算量 O(NS) で十分間に合いました。

E - Rush Hour 2 (500点)

任意の整数時間待機することができるので、各都市への最速到達時間を考えればいいです。道路 i を通って都市 A_i から時刻 t に出発して都市 B_i に到達する時刻は t + C_i + \displaystyle \left\lfloor \frac{D_i}{t+1} \right\rfloor となります。f(t) = t + C + \displaystyle \left\lfloor \frac{D}{t+1} \right\rfloor, g(t) = t + C + \displaystyle\frac{D}{t+1} とした時 g'(t) = 1 - \displaystyle\frac{D}{(t+1)^2} であり、gt \leq \sqrt{D} -1 で単調減少、t \geq \sqrt{D} -1 で単調増加することから、t = \sqrt{D}-1 のときに最小値をとり、f(t) = \lfloor g(t) \rfloor であることから f\sqrt{D}-1 附近で最小値をとることが分かります。ちゃんとした解説は公式解説を参照して下さい。
上記から各道を通った時の反対側に着く時刻が最小値となるような出発時刻 t_i が求まります。よって、頂点 A_i に到達可能な最速時刻が T であるとき、 T \lt t_i の時は t_i まで待ってから、T \geq t_i の時は即座に道 i を用いることでその道を用いて B_i へ行く経路のうち最速で B_i に行くことができるため、このように改造したDijkstra法で答えを求めることができます。

F - Hanjo 2 (600点): 未提出

制約からbitDP+行列累乗かなと思いましたが、漸化式が書けませんでした...

結果、感想

f:id:Flkanjin:20210607132329p:plain
久しぶりにレートが上昇しました。速く青色復帰したいです。

ZONeエナジー プログラミングコンテスト “HELLO SPACE”のきろく

ZONeエナジー プログラミングコンテスト “HELLO SPACE”に参加、レートを大幅に冷やしてしまいました...

A - UFO襲来 / UFO Invasion (100点)

長さは 12 文字なので愚直に書くこともできますがfor文を用いてi文字目から4文字の部分文字列がZONeであるかどうかを判別すればいいです。

B - 友好の印 / Sign of Friendship (200点)

距離 d, 高さ h の遮蔽物が邪魔にならないのはUFOと遮蔽物の上端を結ぶ直線とタワーの交点以上上った時であり、その高さを x とすると三角形の相似より h-x:d = H-x:D 依り \displaystyle x = \frac{Dh-Hd}{D-d} であるため答えは \displaystyle \max\left\{0,\,\max_{i} \frac{Dh_i-Hd_i}{D-d_i}\right\} となります。

D - 宇宙人からのメッセージ / Message from Aliens (300点)

実際に文字列を反転させるのは文字列長ほどの計算量を要するので時間がかかります。反転しているかどうかbool型の変数を用意しておき、その状態に合わせて前後から文字を追加できるようにdequeを利用します。
後半の同じ文字を取り除くのは文字を1文字ずつ取り出していくとき、答えの文字列の末尾と追加する文字が同じときに取り除き、そうでないときそのまま追加するとすることによって実現することができます。

C - MAD TEAM (400点)

最小値の最大化なので二分探索であることは思いつきましたがそれに必要な判定方法をコンテスト中に思いつくことができませんでした。
答えが x 以上かどうかを考える時各人の各能力が x 以上かどうかしか考える必要がなく、5 bitの数と考え、状態を圧縮し、3人を選んだ時に全てがtrueになるかどうかを判定すればいいことが分かります。3人を選ぶときは各人の5 bitの数を集合などに入れてやることで高々 32 種類しか考える必要がなくなり、そこから重複を許して3つ選んでやることでOKかどうか分かります。

E - 潜入 / Sneaking (500点)

愚直に辺を張ると辺の本数が O(R^2C) となり、Dijkstra法でも間に合わないなと考えていました。 何かこれでも通る人は通るみたいですね...通しとけばよかった

x 軸の負方向への移動は +1 がなければ隣の頂点へのコスト 1 の辺で表すことができます。そこで頂点を2階層とし、x 軸の負方向への移動だけは2階層目で、その他は1階層で行うことにします。1階層から2階層の対応する頂点へはコスト 1, その逆はコスト 0 とすることで、問題文の移動を O(RC) 本の辺で表現することができ、Dijkstra法で十分間に合う本数になります。

F - 出会いと別れ / Encounter and Farewell (600点): 未提出

線形の基底らしいですね、履修しておきます...

結果、感想

f:id:Flkanjin:20210503231016p:plain
CやEが解けず、レートを冷やしてしまいました... 2週間連続で冷やしているので、何とか挽回していきたきですね。

Educational Codeforces Round 108のきろく

問題文和訳はこちら

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 問題文和訳

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

出力例1
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

出力例1
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

出力例1
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

出力例1
29
2
13 37
2 4

出力例
174
6
1 8 7 6 3 6
5 9 6 8 8 6

出力例3
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

出力例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

出力例2
1
1 2
4
182 168 60 96
78 72 45 72
69 21 144 63
148 12 105 6

出力例3
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_ii 番目の宝箱に入っているコインの枚数である。

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

出力例1
205205
2 3
3 3
2 1 4
10 20 100
20 15 80

出力例2
110
2 3
3 4
1 1 4
10 20 100
20 15 80

出力例3
-1

注記

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

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

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

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

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

AtCoder Beginner Contest 199のきろく

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

A - Square Inequality (100点)

いつぞやの誤差を気にする問題のような問題文ですがこちらは元から整数なので素直に A^2 + B^2C^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などを考えます。S1 から 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} については頂点 uv を結ぶ辺が選ばれたとき 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 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のきろく

問題文和訳はこちら

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

タイプ i のレビュアーの人数を a_i とします。
タイプ 13 のレビュアーを第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} とすると xa 桁、yb 桁であり、\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 の時はak = 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しているのですが)のでちゃんと通ってよかったです。