Codeforces Round #85 (Div 1 only)

B落とした上にA,Cリサブミットしててまた残念な感じorz

result

206位 304 / (-1) / 740 / - / -
1833 -> 1834

A. Petya and Inequiations

問題

次の条件を満たす正の整数からなる数列a1,a2,...,anを出力せよ。
a1+a2+...+an≦y
a1^2+a2^2+...+an^2≧x


答えが複数ある場合はどれを出力してもよい。存在しない場合は-1を出力せよ。

試行錯誤

aiの和が一定のとき、明らかにa1=a2=...=an-1=1, an=(残り)としたときに二乗和が最大。
だからそういう数列を作って、二乗和がx以上になってるか確認して出力すればいい。


書いた。queueが非常に混んでいる。
採点結果を見ないままBを解き始める。

B. Petya and Divisors

問題

n個の整数の二つ組xi,yiが与えられる。それぞれについて以下のようなクエリを処理せよ。

xiの約数のうち、xi, xi-1, xi-2, ..., xi-yiのどれも割り切らないような数の個数を出力する。

xi,yi≦10^5

試行錯誤

10^5!?
約数を全生成しておくとかできない。。。


うーん。区間を平方分割して、区間ごとに約数をまとめてオーダー落とすくらいしか思い浮かばない。

やってる。ぱっと書けた。送ってみる。pretest passed.

A.(再)

そうこうしているうちにAがHackされたとのお知らせが。
あれー方針おかしかったかなあ。


いや、1,1,1,1,kのとき最大に決まってる。証明する。正しいよな。

じゃあ何だろう。10分くらい悩む。
あ、1,1,1,1,1がそもそもyに届かない場合あるじゃん。これだ。
その処理を追加して再送信。

C. Petya and Spiders

問題

nxmのマスがある。初期状態ではそれぞれのマスに蜘蛛が1匹ずるいる。
それぞれの蜘蛛に同時に指令を与える。指令は

  • 動かない
  • 上のマスに行く
  • 下のマスに行く
  • 左のマスに行く
  • 右のマスに行く

の5種類。移動後に、一つのマスに蜘蛛が二匹以上入っていてもいい。
ただしマスからはみでてはダメ。

このとき、蜘蛛が入っていないマスの数を最大化したい。その値を求めよ。

m,n≦40かつm*n≦40

試行錯誤

蜘蛛がいるマスをしましま模様みたいにするのが最善だろうか。
すると元のマスの1/3くらいが蜘蛛の入ったマスになる。

いや、十字の中心に移動するようにすると大体1/5が蜘蛛のマスになるから最善でもなさそう。まあ1/5になることはなさそうで……


あー制約小さいしDPすればいいか。
DPかきかき。

あ、これ1列の蜘蛛の状態覚えながらじゃダメで、二列の蜘蛛の状態覚えながらにしないとダメっぽい。
んー時間すごいギリギリな気が。


書いた。最大ケース6*6のときやっぱ10秒くらいかかっちゃうなー。
他のケースは一瞬で終わる。どうしよ。


残り時間15分なので一旦提出。


最大ケース最適化とかかかったとしてもやっぱ無理だなあ。
いいや6*6だけうめこんじゃえ。再送信。pretest passed.

D.

時間なし。

System Test

BがTLEで落ちたorz
平方分割じゃダメなのか、あるいはsetが遅かったのか……