ARMERIA

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

Codeforces Avito Cool Challenge 2018 参加記録＆解説（A～E）

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

プレテスト5完だったのですが、Dがしょうもない実装ミスで落ちました…

f:id:betrue12:20181217033706p:plain

A～Eまで5問振り返ります。

A. Definite Game

Problem - A - Codeforces

問題概要

正整数 n の初期値 v が与えられる。これに以下の操作を0回以上繰り返して、 n をできるだけ小さな数にしたい。その数を求めよ。

  • x \lt n かつ x が n の約数でないような正整数 x を選び、 n から x を引く。

制約

  • 1 \le v \le 10^{9}

解法

v = 1, 2 のときは条件を満たす x が存在しないので一度も操作を行えません。

v \ge 3 のとき、 x = v-1 は条件を満たすのでこれを選ぶと n = 1 にすることができて、これが最小です。

つまり v = 2 のとき答えは2、そうでないとき答えは1になります。

ACコード

B. Farewell Party

Problem - B - Codeforces

問題概要

n 人の人が、 1, ..., n で番号付けされた n 種類の帽子のうちどれかを被っている。ここで各人 i について、その人と違う種類の帽子を被っている人は a_{i} 人である。

このような条件を満たす帽子の割り当て方を1つ求めるか、割り当て方が存在しないことを判定せよ。

制約

  • 1 \le n \le 10^{5}
  • 0 \le a_{i} \le n-1

解法

同じ帽子を被っている人は a_{i} の値が同じになっていて、かつその帽子を被っている人はちょうど N - a_{i} 人います。そのため各人を a_{i} の値ごとに分類しておき、人 i を順番に見ていって

  • 人 i の帽子が未割り当てのとき、 a_{i} の値が同じ人を人 i 含めて N-a_{i} 人適当に選び、その人達に同じ帽子を割り当てる

という操作を繰り返すことで帽子を割り当てていくことができます。割り当てるための人数が足りなくなってしまった場合は、割り当てが不可能と判定して終了します。

ACコード

C. Colorful Bricks

Problem - C - Codeforces

問題概要

一列に並んだ n 個のレンガを m 色のペンキで塗り分ける。このとき、隣り合うレンガ間で色が異なるような場所がちょうど k 個あるような塗り方の総数を求め、 998244353 で割った余りを出力せよ。

制約

  • 1 \le n, m \le 2000
  • 0 \le k \le n-1

解法

「 i 番目のレンガまでの塗り方で、それまででレンガ間の色が異なる箇所が j 個であるような塗り方の総数」を dp\lbrack i \rbrack\lbrack j \rbrack とします。 dp\lbrack n \rbrack\lbrack k \rbrack が答えです。

最初のレンガの塗り方は m 通りなので dp\lbrack 1 \rbrack\lbrack 0 \rbrack = m、そこからの遷移は「前と色が同じ」塗り方が1通りで「前と色が異なる」塗り方が m-1 通りなので

  • dp\lbrack i+1 \rbrack\lbrack j \rbrack += dp\lbrack i \rbrack\lbrack j \rbrack
  • dp\lbrack i+1 \rbrack\lbrack j+1 \rbrack += (m-1) \times dp\lbrack i \rbrack\lbrack j \rbrack

となります。 O(NK) が間に合うのでこれで解けます。

ACコード

D. Maximum Distance

Problem - D - Codeforces

問題概要

n 頂点 m 辺の重み付き無向グラフが与えられる。辺 i の重みは w_{i} である。

このグラフにおける経路の「コスト」を、その経路の最も重い辺の重みと定義する。そして頂点同士の「距離」を、頂点間を結ぶ経路のコストの最小値とする。

頂点のうち k 個の頂点が「特別な頂点」として指定される。それぞれの特別な頂点について、最も「遠い」特別な頂点との距離を求めよ。

制約

  • 2 \le k \le n \le 10^{5}
  • n-1 \le m \le 10^{5}
  • 1 \le w _{i} \le 10^{9}
  • グラフは連結であるが、単純とは限らない

解法

頂点同士の距離が d 以下であることは、重み d 以下の辺だけを使って頂点間が連結となることと同値です。

まずグラフから全ての辺を取り去り、重みの小さい辺から順にグラフに足していくことを考えます。この操作において頂点同士が連結になったとき、最後に追加した辺の重みがその頂点間の距離となります。

つまり各特別な頂点について最も遠い特別な頂点は、一番最後に連結になったものです。結局は、全ての特別な頂点が連結になったときに全頂点にとってそれぞれ最も遠い頂点と連結になり、そのとき最後に追加した辺の重みが全ての頂点についての答えになります。

あとは、辺を追加して端点同士を連結にしていく操作をUnion-findで実装します。「全ての特別な頂点が連結になった」という判定が少し難しいですが、Union-Findの連結成分に「その連結成分に含まれる特別な頂点の個数」を管理する機能を持たせ、その値が k になればOKという判定をするのが楽だと思います。

ACコード

E. Missing Numbers

Problem - E - Codeforces

問題概要

正の偶数 n が与えられる。数列 x_{1}, ..., x_{n} のうち偶数番目の要素が与えられる。

このとき奇数番目の要素の選び方で、以下を満たすものを1つ求めよ。またはそのような要素の選び方が存在しないことを判定せよ。

  • 1 \le x_{i} \le 10^{13}
  • 各 t について、 x_{1} + \cdots + x_{t} は平方数となる。

制約

  • 2 \le n \le 10^{5} であり n は偶数
  • 与えられる偶数番目の要素は、 1 \le x_{i} \le 2\times 10^{5}

解法

平方数 x_{1} + \cdots + x_{t} の正の平方根を a_{t} と表すことにします。この値は整数です。また x_{i} が全て正であることから、 a_{1}, ..., a_{n} は狭義単調増加になっています。

この最大値 a_{n} がどこまで大きくなり得るか考えてみます。 x_{n} = a_{n}^{2} - a_{n-1}^{2} であり、 a_{n-1} \le a_{n} - 1 を用いて式変形すると

  • a_{n} \le \frac{x_{n}+1}{2}

という不等式を得ることができます。制約から x_{n} \le 2\times 10^{5} なので、 a_{n} が整数であることも考慮すると a_{n} \le 10^{5} となり、そんなに大きな値にならないことが分かります。

次に、奇数番目の要素 x_{2k+1} をどのように決めればよいか考えます。1つ前までの要素和が a_{2k}^{2} であるとき、 x_{2k+1} を適切に選ぶことによって、 a_{2k} \lt a_{2k+1} である任意の a_{2k+1} を実現することが出来ます。具体的には x_{2k+1} = a_{2k+1}^{2} - a_{2k}^{2} とすればよいです。

もちろんその次の要素 x_{2k+2} は与えられているので、 a_{2k+1}^{2} + x_{2k+2} が平方数となるようなものを選ばなければいけません。その条件内でなるべく小さいものを選んだほうがその後の選択肢が多くなります。

そのため、各奇数番目の要素 x_{2k+1} を決めるにあたって、

  1. a_{2k+1} の候補として、1つ前の値 a_{2k} より大きい値を小さい方から順に a_{2k}+1, a_{2k}+2, ... と試す。
  2. もし a_{2k+1}^{2} + x_{2k+2} が平方数となるような a_{2k+1} が見つかれば、その値を採用して x_{2k+1} = a_{2k+1}^{2} - a_{2k}^{2} とする。
  3. その値を採用したときの a_{2k+1}^{2} + x_{2k+2} の平方根が a_{2k+2} となるので、これを用いて次の a_{2k+3} を同じ手順で求める。

というように、前から順番に値を決めていくことが出来ます。

この過程において調べる a_{2k+1} の値は、試行を1回行うごとに少なくとも1増えます。先ほど見たように a_{n} \le 10^{5} なので、多くとも合計で 10^{5} 回の試行を行えば、最後まで値を求め終わるか、または解が存在しないことが分かります。計算量の面でも十分間に合います。

ACコード

ある整数が平方数かどうかを誤差を気にせずに求めるのは少し面倒ですが、今回の問題では取り得る値が限られていて計算量にも余裕があるので、この実装では「平方数→その平方根」の対応を集めたmapを作ってしまっています。