最近のSRM無駄にconstructive多いっすね。
SRM 742 easy
1,0.5,0.25,0.125....と1,2,4,8,16....を作って適当に繋げれば良いけどバグった。
SRM 742 med
kmpチックにbitdpすればいい
SRM 740 easy
どういうことやねんと思ったら罠が有りました…
SRM 740 medium
dp復元久しぶりに書いてめちゃくちゃバグった。
SRM 739 easy
虚無実装だけど、こういうのはだいたい全探索できるからありがたい。
SRM 739 med
にぶたんしたあと適当に貪欲でいいなぁと思って実装したけど、条件を間違えまくって辛かった。
正しいのは、前の餌場から見ていって、空腹度が大きい牛を使っていくんですが、今の餌場では空腹を満たせない時、次の餌場でもそうであればfalseです。
(SRM 738は神回です)
SRM 738 easy
長さが整数である格子点上の2点がかなり少ないことを利用する。
SRM 738 med
実は独立に考えて良い。良問。
SRM 737 easy
面白い。全要素のxorをXとする。ある要素aをとって、X^aが0になる方法はたかだか1通り。
またX^a<=aという条件がつくが、これはXの最上位bitがaに含まれていることと同値。
よって奇数なら64, 65, 66...とかすればN<=37なので良くて、偶数なら全要素が上の条件を満たすのは不可能で、
1つ犠牲にすれば奇数と同じ状態になる。
SRM 737 med
は？0,1,-1に気をつけて掛け算するんですが、多倍長整数がいる。やめて。
SRM 735 easy
aaaaaa...とbbbbbb...を取ればたかだか2です。
SRM 735 med
条件はX(X-1)=0(mod m)です。XとX-1は互いに素なので、mの互いに素な積を全部試して、extgcdする。
SRM 734 easy
まず軸上は最初に除いておきます。そうすると、x>0,y>0,x^2+y^2<=r^2,gcd(x,y)=1なるx,yの個数を求めればよいです。
あとはx全部試してyは包除原理します。
SRM 734 med
ブラックジャックなんてしないで…
SRM 733 easy
ほんとうにやるだけ
SRM 732 easy
これ難しすぎるだろ…1点をひっくり返すのを繰り返すのが良いとわかりますが、領域が分かれている時もあるので注意。
SRM 731 easy
こういうの速くならないんだよね…dfsしていけばいいですが、文字列の扱いが若干複雑。
