はまやんはまやんはまやん

hamayanhamayan's blog

Codeforces Round #409 Div1 問題と解説

競技プログラミング

競プロのコード例について補足 競技プログラミング練習問題集 Twitter 競技セキュリティまとめのまとめ

http://codeforces.com/contest/800

問題

A. Voltage Keepsake

N個のデバイスがあり、1秒にA[i]エネルギー使い、元々B[i]エネルギー分充電されている。
毎秒Pエネルギー充電できる充電器が1つだけある。
全てのデバイスを同時に使用する時、充電器を適切に使いまわすことで最大何秒全て稼働させられるか。
無限に動かせるなら"-1"

B. Volatile Kite

N頂点の凸包がある。
全ての頂点を最大長さD分だけ任意の場所へ動かせるとする。
どのように動かしても凸包となる長さDの最大値を求めよ。

C. Vulnerable Kerbals

N個の禁止リストと整数Mがある。
以下のルールを満たす数列Aを求めよ。
1. 全ての要素は[0,M-1]
2. 接頭積列の全ての要素は独立
3. 接頭積列に禁止リストの要素は含まれない
4. 上記のルールを満たすなかで要素数最大
※ 接頭積列(prefix product) : 俺の造語なので注意。B[i] = A[0] * A[1] * ... * A[i]が一般項となる列

D. Varying Kibibits

N個の数列Tがある。

関数f(L)がある。
この関数は数列Lに対して、以下のルールである数を返す。
1. 数列L内の全ての数の桁数が最大のものと等しくなるように先頭に0をつける。
2. i番目の文字が数列Lの全てのi番目の文字の最小となるように文字列を作る。
3. 2.で作った文字列を数に変換して出力

例) f(10,9)
1. 10, 09
2. 1番目は1と0なので0、2番目は0と9なので0より00という文字列が作られる
3. よって f(10,9)=0

関数G(x)がある。
G(x)はf(S)=xとなる全ての空集合でないTの部分集合Sについて要素の総和を二乗して足した数mod(10^9+7)にxを掛けた数である。

G(0) xor G(1) xor ... xor G(999999)を答えよ

以下、解説

















A. Voltage Keepsake

http://codeforces.com/contest/800/submission/26442607
二分探索をするのだが、小数二分探索なので誤差がヤバイ。

まず、無限に動かせる場合を分けておく。
「A[i]の総和 ≦ P」ならば無限に動く。

あとはchk(t) := t秒間動かすことができるか。
自分の解法ではt秒間動かす時はt*Pだけ充電可能で、あるデバイスではt*A[i] - B[i]だけ必要だから分配した時に全てちゃんと分配できるかというのをチェックした。

あとは、Twitter上でも議論になってた二分探索の上限をどうするか問題。
1e12でも通るし、1e10でも通るらしい。
natsugiriさんは上限を計算で求めていた。

B. Volatile Kite

http://codeforces.com/contest/800/submission/26423097
思いつかないと厳しい問題。
全ての隣り合う3点について考える。
時計回りに頂点a,b,cがあるとき、直線acと頂点bの距離をdとすると、この部分について動かせる最大距離はd/2となる。
これを全て計算して最大のものが答え。

C. Vulnerable Kerbals

http://codeforces.com/contest/800/submission/26444039

考察が難しいのだが、まずは、接頭積列B[i]の構築から始める。
Bの最後は0で、それ以外の配置をグラフGを以下のように作って考える。

  • M頂点の1～M-1が書かれた有向グラフGを考える
  • B[i + 1] = B[i] * A[i + 1]であるため、グラフGで言うと、ある頂点iから1～M-1のいずれかをかけてmodMとした先への遷移と考えられる
  • つまり、グラフGでの有向辺は (i,j) <=> i * n = j (mod M)を満たすnが存在
  • もうちょっと言うと、(i,j) <=> gcd(i,j,M) != 1 かつ gcd(i,M) <= gcd(j,M)

もう少し工夫すると、ただの有向グラフではなくDAGにできる

  • gcd(i,M) = gcd(j,M)である頂点は1つに纏めることができる
  • gcdが同じ物を全部使ってから、つぎのgcdへ移ればいいため

gcdが同じ頂点を纏めると自然とDAGになる。
あとは接頭積列の要素は独立であるため、求めたい接頭積列はグラフGにおけるある頂点を複数回通らない最長のパスとでき、DAGなのでDPで解ける。

次は、接頭積列B[i]から答えA[i]を復元することである。
まず、A[0] = B[0]。
A[i]はB[i-1]*A[i]=B[i]を満たす[0,M-1]の数であり、これを高速に求める必要がある。
これは「ax=1(mod m)」が拡張ユークリッドで高速に求められることを利用して求める。
蟻本にやり方が書いてあるし、ここも参考になる。
sucrose.hatenablog.com

まずB[i-1]*x=1(mod m)を求める。
x=B[i-1]^(-1)という訳なので、
B[i-1]*A[i]=B[i]
B[i-1]*A[i]*B[i-1]^(-1)=B[i]*B[i-1]^(-1)
A[i]=B[i]*B[i-1]^(-1)
という感じで求められる。
これで復元して答え。

なのだが、今回はaとmが互いに素でない可能性があり、少し工夫する必要がある。
復元の部分は正直、latteさんの丸パクリでよく理解してない

D. Varying Kibibits

プロのツイート