Educational Codeforces Round 107のきろく

問題文和訳はこちら

A. Review Site / Сайт отзывов
B. GCD Length / Длина НОД
C. Yet Another Card Deck / Очередная задача про колоду карт
D. Min Cost String / Строка минимальной стоимости
E. Colorings and Dominoes / Раскраски и домино (実行時間制限: 3 sec): 未提出
F. Chainword / Чайнворд (実行時間制限: 3 sec): 未提出
結果、感想

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

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

$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$ 文字を出力すればよいです。