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
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が遅かったのか……