ARMERIA

Rubyと競技プログラミングの話　AtCoderやCodeforcesの問題解説記事が多め。

Educational Codeforces Round 59 参加記録＆解説（A～D）

Codeforces プログラミング 競技プログラミング

しばらくこどふぉの記事をサポってますね…

A. Digits Sequence Dividing

Problem - A - Codeforces

問題概要

以下の問題 q 個に答えよ。

  • 1, ..., 9 からなる n 文字の文字列が与えられる。この文字列を2つ以上の連続部分文字列に分解し、「それぞれの文字列を10進数の数値として見たときに、狭義単調増加列になっている」ようなものを1つ出力せよ。存在しない場合はそれを判定せよ。

制約

  • 1 \le q \le 300
  • 2 \le n \le 300

解法

n \ge 3 のとき、1文字目とそれ以外に分けることで後の文字列が2桁以上になり、必ず条件を満たします。

n = 2 のときは1文字目と2文字目に分けるしか無いので、1文字目より2文字目が大きければそれが解になり、そうでなければ解は存在しません。

ACコード

Submission #48994495 - Codeforces

B. Digital root

Problem - B - Codeforces

問題概要

以下の問題 n 個に答えよ。

  • 非負整数に対し、「その10進数における桁和を取る」という操作を1桁になるまで繰り返したときの値をdigital rootと呼ぶことにする。digital rootが x となる非負整数の中で小さい方から k 番目のものを求めよ。

制約

  • 1 \le n \le 10^{3}
  • 1 \le k \le 10^{12}
  • 1 \le x \le 9

解法

digital rootが0になる整数は0だけで、入力として0は与えられないので、正整数だけを考えます。

正整数 a に対してこのような操作を繰り返して得られる数は、 a を9で割った余りに一致します。ただし余りが0の場合は9です。これは「10進数の桁和を取っても、9で割った余りは変化しない」という性質によるものです。

そのためdigital rootが x である k 番目の数は、1番目の数（すなわち x ）に 9(k-1) を足したものとして求められます。

ACコード

Submission #48996531 - Codeforces

C. Brutality

Problem - C - Codeforces

問題概要

n 文字の文字列が与えられる。この文字列の i 文字目には得点 a_{i} が割り当てられている。

この文字列の部分列を取り、「どの同じ文字も k 回を超えて連続しない」という条件のもとで、選んだ文字の得点合計を最大にしたい。その得点を求めよ。

制約

  • 1 \le k \le n \le 2\times 10^{5}
  • 1 \le a_{i} \le 10^{9}

解法

与えられた文字列を、同じ文字が連続する区間で分割します。そうすると、

  • 同じ文字が連続する長さが k 以下である場合、その文字を全て選んで良い。
  • 同じ文字が連続する長さが k を超えている場合、この中から k 文字までしか選ぶことができないので、大きい方から k 個選ぶのが最適である。

というような選び方をすることができます。

あとはこれを実装しましょう。私は文字列を前から見ていって、文字が変わるタイミングで今まで連続していた文字の得点をソートし加算しています。priority_queueなどを使うのも良いですね。

ACコード

Submission #48999277 - Codeforces

D. Compression

Problem - D - Codeforces

問題概要

0または1を要素とする n \times n 行列が与えられる。以下の条件を満たす時、この行列は x 圧縮可能であると呼ぶことにする。

  • x は n の約数である。
  • 行列を要素数 x \times x のブロック \frac{n}{x} \times \frac{n}{x} 個に分割したとき、各ブロックに含まれる要素は全て等しい。

x 圧縮可能である x のうち最大のものを求めよ。

制約

  • 4 \le n \le 5200 であり、 n は4の倍数
  • 各行の値は \frac{n}{4} 文字の16進数として与えられる

解法

x 圧縮可能な行列は、どの行・列を見ても「最初の x 個の要素は全て等しい」「次の x 個の要素は全て等しい」…という状態になっています。これを言い換えると、それぞれの行・列で「同じ要素が続く個数」を全て列挙したときに、それらが全て x の倍数になっている必要があります。

逆も言えるので、求めたいものは結局全ての行・列の「同じ要素が続く個数」全ての最大公約数になります。ちょっと計算量が多めですが、素直に全ての行・列を見ていって最大公約数を取っていく実装で間に合います。

ACコード

Submission #49005241 - Codeforces