ARMERIA

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

Codeforces Round #525 参加記録＆解説（A～E）

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

Dashboard - Codeforces Round #525 (Div. 2) - Codeforces

今回は3完…うーん。Div2でこれは良くないですね。

f:id:betrue12:20181205205506p:plain

本番後にEまで通したので5問書いていきます。

A. Ehab and another construction problem

Problem - A - Codeforces

問題概要

正整数 x が与えられる。以下の条件をすべて満たす整数 a, b を1組求めよ。（存在しない場合は -1 を出力せよ。）

  • 1 \le a, b \le x
  • b は a の約数である
  • ab \gt x
  • \frac{a}{b} \lt x

制約

  • 1 \le x \le 100

解法

a, b の組が最大で10000個しかないので、全探索が確実です。

O(1) 解法もありますが、本番ではノータイムで全探索を書き始めました…Codeforcesではコーナーケース考慮漏れによるシステス落ちが常に頭をよぎるので、個人的には余裕で間に合う計算量であれば全探索したくなります。

ACコード

Submission #46589226 - Codeforces

B. Ehab and subtraction

Problem - B - Codeforces

問題概要

長さ n の配列 a_{1}, ..., a_{n} が与えられる。これに以下の操作を k 回行い、それぞれ値を出力せよ。

  • 非零の要素が存在する場合、最も小さい非零の値を出力する。その後、その値を配列内のすべての非零要素から引く。
  • 全ての要素が0である場合、0を出力する。

制約

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

解法

0になってしまった要素はその後の操作に全く関係しないので、配列から除外してしまって構いません。また与えられる要素が全て正で、常に最小の値を引き算するので、操作中に配列の要素に負数が現れることはありません。

以下リンク先のコードではシミュレーションをしています。配列を降順にソートし、末尾の値が0なら削除し、そうでなければその値を出力して全体から引きます。ただし毎回全ての要素に引き算をしていては間に合わないので、「今まで累積いくつ引き算したか」を持っておいて処理しています。

よりスマートな解法として、最初に重複要素を全て除いてしまうという方法もあります。

ACコード

Submission #46592094 - Codeforces

C. Ehab and a 2-operation task

Problem - C - Codeforces

問題概要

長さ n の配列 a_{1}, ..., a_{n} が与えられる。この配列に以下の操作を好きな順序で n+1 回以下行い、配列を狭義単調増加にしたい。そのような操作列を1つ求めよ。

  • 整数 i, x を選ぶ（ 1 \le i \le n, 0 \le x \le 10^{6}）。配列の要素 a_{1}, a_{2}, ..., a_{i} それぞれに x を加算する。
  • 整数 i, x を選ぶ（ 1 \le i \le n, 1 \le x \le 10^{6}）。配列の要素 a_{1}, a_{2}, ..., a_{i} それぞれを、 x で割った余りに置き換える。

制約

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

解法

「余りを取る」という操作を上手く使うことを考えます。

  1. a_{1}, a_{2}, ..., a_{N} に上手く値を足し、それぞれを n で割った余りが 0, 1, ..., (n-1) になるようにする。
  2. 最後に全要素を n で割った余りに置き換える。

ことで条件を満たすことができます。 n 回の足し算操作を行えるので、末尾から順番に余りの値を合わせていけばよさそうです。

足し算操作は n が小さいので愚直にやっても十分間に合います。B問題で書いたのと同じようにまとめて加算することもできます。

各操作では（1-indexedで書くと） (a_{i} + x) \% N = i-1 となるような x を求めることになりますが、これはそのまま移項して x = (i-1 - a_{i}) \% N とすればよいです。ただし言語によってはこの値が負になってしまったりするので、さらに x = (x + N) \% N とするなどしてください （つらい）。

ACコード

Submission #46597669 - Codeforces

D. Ehab and another another xor problem

Problem - D - Codeforces

問題概要

インタラクティブ問題である。以下のクエリを62回以下行うことで、隠された整数 a, b を求めよ。

  • 0 \le c, d \lt 2^{30} である整数 c, d をクエリとして出力する。その答えとして以下の値を得ることができる。ここで \oplus はXOR演算を表す。
    • a \oplus c \gt b \oplus d のとき、 1
    • a \oplus c = b \oplus d のとき、 0
    • a \oplus c \lt b \oplus d のとき、 -1

制約

0 \le a, b \lt 2^{30}

解法

最下位ビットを0ビット目として、下から数えて k ビット目のビットを単に「 k ビット目」と呼ぶことにします。

値の大小には、上位ビットほど優先的に影響を与えます。そのため上位ビットから順に決めていくことを考えます。まず最上位のビット（29ビット目）を決めるため、クエリとして29ビット目だけを立てたものを考えてみましょう。

考えられるクエリは (0, 2^{29}), (2^{29}, 0), (0, 0), (2^{29}, 2^{29}) あたりです。各ビットごとに使えるクエリはほぼ2回なので、良い情報が得られそうなものを2つ選びたいですが…ここでは (0, 2^{29}), (2^{29}, 0) を考えてみましょう。

a, b の29ビット目のパターンそれぞれについて、クエリの結果がどうなるかを書き下します。

↓ a, b の29ビット目 (0, 2^{29}) (2^{29}, 0)
0, 0 -1 が返る 1が返る
0, 1 28ビット目以下の大小に従う 同左
1, 0 28ビット目以下の大小に従う 同左
1, 1 1が返る -1が返る

このように、両クエリで値が異なる場合は a, b の29ビット目が確定します。ただし値が同じ場合、29ビット目が a, b で異なるという情報は得られますが、どちらが 1 なのかは分かりません。これを判定するには、別途 (0, 0) のクエリを発行し、 a, b の大小関係を調べればよいです。

上位のビットが判定できれば、以降のクエリにはそのビットを常に付与しておくことで、 a \oplus c, b \oplus d ともに上位ビットは打ち消し合って0になります。そのため最上位ビットと同様の判定方法でビットを判定していくことができます。

まとめると、「 k ビット目を判定するためには、 k ビット目以下の大小関係を知った上で、クエリ (0, 2^{k}), (2^{k}, 0) を発行すればよい」ことになります。これだけ見ると、ビット1つにつきクエリが3つ必要そうに思えますが…

最初の情報を得るために (0, 0) は発行する必要があります。それ以降は追加のクエリを発行しなくても、上位ビットから判定していって以下のように考えることで大小の情報を得ることができます。

  • a, b の k ビット目が等しい場合、 k ビット目以下の大小と k-1 ビット目以下の大小は一致するので、そのまま情報を使うことができる。
  • a, b の k ビット目が異なる場合、上記の表に記載した通りクエリの結果は「 k-1 ビット目以下の大小に従う」ため、この結果を情報として使うことができる。

このように考えることでクエリ回数は最初の1回＋30ビット×2回の計61回となり、問題の条件に収まります。

ACコード

Submission #46645417 - Codeforces

E. Ehab and a component choosing problem

Problem - E - Codeforces

問題概要

n 頂点の木があり、各頂点に重み a_{i} が設定されている。この木から連結成分を互いに交わらないように1個以上選ぶ。

選び方のスコアは、連結成分の数を k 、選んだ連結成分に含まれる頂点全ての重み和を A として \frac{A}{k} と定義される。

スコアを最大にし、かつその中で k を最大にしたい。そのような選び方をしたときの A, k を求めよ。

制約

  • 1 \le n \le 3\times 10^{5}
  • |a_{i}| \le 10^{9}

解法

スコアは「各連結成分の重み和の平均」と解釈することができます。その最大値は、1つだけの連結成分で作れる重み和の最大値（これを A_{1} とします）と一致します。 A_{1} より大きな重み和を持つ連結成分が作れない以上、その平均も A_{1} を超えることができないからです。

そのためまずは A_{1} を求めます。重み和最大の連結成分を求めるのは、適当に根を決めた根付き木において以下のような木DPをすることで可能です。

dp\lbrack i \rbrack を「頂点 i を含み、根付き木において i 以下の要素で作られる連結成分の最大重み和」とします。 dp\lbrack i \rbrack を求める時に i の子 j それぞれと接続をするかどうかは、 dp\lbrack j \rbrack \gt 0 であれば接続し、そうでなければ接続しない、とすることで最適となります。

f:id:betrue12:20181205231143p:plain

※この説明には例外がありますが、それは後で補足します。

これで A_{1} を求めることができました。今度は k を最大にするため、「重み和 A_{1} の連結成分を最大でいくつ作れるか？」を求めることが必要になります。これも同様に木DPで求めることができます。先程のDPとの違いは、「重み和 A_{1} の連結成分ができたら、そこで連結成分を閉じて上と繋がない」ようにするだけです。

これで多くの場合は解を求めることができますが…DPにおいて「重み和が正でない子は切り捨てる」としているため、全頂点の重みが0以下であるときには1つも頂点を選べません。この場合は「いかにマイナスを小さくするか」という視点で考えると、「値が最大の頂点を探し、それと同じ値の頂点を全て独立な連結成分として選ぶ」ことが最適だと分かるので、木DPをせずにこれを出力してしまえばよいです。

ACコード

Submission #46645581 - Codeforces

この実装のようにDPテーブルを保持せず、再帰関数の戻り値だけで処理することも可能です。