SRM536

結果報告

試しに作った。多分長続きはしないけど前回SRMの報告でも書いとく。

Level	ProblemName	Status	Point
Easy	MergersDivOne	PassedSystemTest	195.38
Medium	RollingDiceDivOne	ChallengeSucceeded	0.00
Hard	BinaryPolynomialDivOne	Opened	0.00

Challenge Phaseで撃墜2成功2失敗で+50点だった。

Easy MergersDivOne

問題

初期状態では複数お店があり、それらの収入が数列として与えられる。
このお店のうちm店を合併させると、新たに出来るお店の収入は元のお店の収入の平均値であることが知られている。
店舗の合併を繰り返し、最終的には１店舗にしたい。最後に残った店舗の収入の最大値を答えよ。

考えたこと

最初の10分強くらい、数列の順番入れ替え不可＆一度に合併出来る店舗が2店であると勘違いしてdpを書いてた。
書いてから最後のテストケースが通らないことに気づいたので、取り敢えず最後のテストケースについて考察する。。
入力{10, -10, 100, -100, 1000, -1000}に対して491.25を返したいのだから、
1000の与える影響が大きくなれば良い。逆に、-1000の与える影響は極力小さくしたい。
何となく、小さい順に二個ずつ合併させて言ったら良いんじゃね？と思う。
仮に三店舗あった場合も、その収入を小さい順にとした時、
三店舗一気にまとめたよりは、二店舗ずつ小さい方からまとめたの方が、の寄与が大きくてお得そう。
ガリガリと数式を弄ったら一般的にと言うことはすぐ示せた。
というわけでこの方針で書いた。コードがさくっと書ける分最初の１０分ロスが痛かった。

コード

  double findMaximum(vector <int> revenues) {
    sort( revenues.begin(), revenues.end() );
    int size = revenues.size();
    double ans = revenues[0];
    for( int i = 1 ; i < size; i++ ){
      ans+=revenues[i];
      ans/=2;
    }
    return ans;
  }

計算量は。nが最大50なので余裕。

後付け考察

なんか書くかも。

Medium RollingDiceDiveOne

問題

色々な数の面をもつダイスがある。ダイスの面の数が数列として与えられi番目のダイスは1以上以下の数字を等確率で出す。
ダイスをすべて振った時に出た目の総和で、もっとも高確率で出現するものを答えよ。複数ある場合はその中でも最小の値を返せ。

考えたこと(嘘解法)

ダイス目の期待値を全部足してみたらどうかと考えてみる。何となく期待値が一番表現パターン多そうだし。
最小値を返すためには、例えば入力が{10}の場合だったら１を返したいし、{1,1,10}とかが入力の場合は3を返したい。
これは1の個数を調べておいて、1以外の値が1つ以下の時に1面ダイスの個数+1でも返しとけば良いんではないか。
（蛇足だがこれも微妙に嘘。1以外の値が0の時は1面ダイスの個数を返すべきだった。それを修正してもなお嘘解法だけど)
少なくてもテストケースの小さいものについてはすべてこの方針で行けそうだ。
書いてみたら最後のケースまで通ってやがる…よろしいならば記念submitだ。

Challenge Phase前にガシガシ紙に書いていたら、この場合、入力{2,5}の場合に出力4を返すが、正しい答えは3であるという事に気付く。
撃墜争いになると思ったので、ぱっとみて似た方針っぽいコード４つに対してこの入力でチャレンジ。
結果、２撃墜２失敗だった。もうちょっとコードをしっかり見たほうが良かったんだろうな。

Hard BinaryPolynomialDivOne

問題

係数が0か1の1変数n次多項式Pの係数が配列によって渡される。(がの係数)
この時、入力kと入力mに対して、与えられた多項式のm乗を2の剰余系で計算した時のの係数に該当する値を返せ。

考えたこと(途中)

例えば多項式Pがの時、
その2乗の係数はで、
4乗の係数はで…なんか規則性がありそう。
もうちょっと踏み込むと、のの係数は、のの係数で決まり、kが奇数なら0しかありえない。
つまり、とかだったらで計算出来る。
…
……
………
でっていう？
例えばだったらなわけだが。
これが例えば足し算だったら解けるけど、掛け算だしねえ。