SRM463 の成績・ソース (要ログイン) : AC/WA/- : rng回は今後敵前逃亡を検討する（嘘です
500開く
- 『1.5～10.0の実数値が書かれたカードがN枚あります。2枚(a,b)選んでa+bかa*bを書いた1枚のカードにして戻す、を繰り返して1枚になったときに値が最大になるようにした時のその最大値を求めてね』
- 足し算も掛け算もオペランドが大きい方が大きくなるので、書き込むときはmax(a+b,a*b)を書けばいい
- 問題は、どういうときにどっちが大きくなるか…
- a+b≦ab
- iff 1≦ab-a-b+1
- iff 1≦(a-1)(b-1)
- のとき。
- 必ず1.5以上だから、a-1は0.5以上だから、b≧3なら掛け算有利
- それより下だと足し算かもしれない
- 両方2以上なら掛け算有利
- テストケース作成
- 最小例兼境界例狙いで、(a-1)(b-1)=1 になる{a,b}を何個かいれておく
- 最大ケースは…サンプルに入ってるからいいや。
- で
- あと、
- 掛け算を途中で混ぜる理由はない
- の方がいいに決まっているので。
- なので、3以上の数は無条件で掛け算する。
- 他の数達も、１度足し算したら絶対3以上になるので、
- まとめると
- 3未満の数達をうまいこと足しあわせて全部3以上にしてやる
- 残りを全部掛け算
- と。
- 「うまいこと足し合わせて」が問題だな
- なにか綺麗な規則があるか…
- 3個の場合で考えるとa<=b<=c<3として
- はどっちがいいか。
- そもそもこれ?は+と*どっちになるパターンがある？
- ええと…
- (※ ここで何か勘違いして常に上がベターなような気がしてしまった！)
- ふむ、単純に小さいのどうしを足してやればいいのか
- 実装
- サンプル通らない
- あれ？
- 1.5 1.5 1.6 1.7 で…(1.5+1.7)*(1.5+1.6)に負けている
- ううむ。
- ううむ。
- どうすればいいのだ。全然わからない
- スコアボード見たら数百人submitしてる！！！！
- は？え？
- うそー
- じゃあ何かすごく簡単な規則があるのかなあ。
- さっきのサンプルだけ見ると、小さい方と大きい方を足し合わせていく感じ
- 手元でいくつか別の例をやってみてもそんな感じ
- うーむ、全然それでいい根拠が思いつかないけど、まあいいか。
- 今日はwriter的に250一完できれば満足する予定だったし。
- これで実装してしまえ。えい。
- 3未満の値達をこの方式で足し合わせるコードを実装。
- サンプル通った。submit！
250開く
- スコア見る限りみんな瞬殺している。その心構えで。
- 『i番目のうさぎには1～maxNumber[i]番のどれかの番号を振ります。N匹のうさぎ全部に違う番号を振る振り方は何通り？mod 10000000007で。』
- 全探索…はmod 10000000007を見る限り無理。N=50も無理な感じ。
- ええと
- maxNumberが小さい方から決めていけば後ろの方は自由度が1個ずつ減るから Π_{i=0～N-1} maxNumber[i]-i だ
- maxNumber[i]-i≦0 なら不可能。
- できた。サンプル通った。追加テストケース要らんでしょ。submit！
- 「maxNumber[i]-i≦0 なら不可能」を考慮せずにそのまま積を返すとどうなる？
- 負の数が返ったりは
- しないか、sortしてあるから、不可能になるところではその値は必ず0。負にはならない。
- maxNumber[i]が1000あるので計算途中でintあふれるけど。
- そういうケースはサンプルにあるな。じゃこれも撃墜には使えない。
1000開く
- 『long long座標の数直線上に3匹のうさぎと3つの巣がありますK≦100ステップちょうどうさぎ達を動かして巣におさめるおさめかたは何通り？mod 10000000007で』
- うさぎの動かしかたは、「座標a,bにいるウサギを選んでaを2b-a (= b+(b-a))に動かす」
- 左に飛んでも右に飛んでもいいけどウサギとウサギが重なったり2匹一気に飛び越してはいけない
- ちょっとだけ考えてみよう
- ウサギ飛び操作は可逆なので
- と考えても同じ事になる。
- てことは両側探索ができるなあ。
- ウサギ軍団を K/2 ステップ動かして可能な状態を列挙
- 巣軍団を (K+1)/2 ステップ動かして可能な状態を列挙
- 重なってるところを掛け算
- これだとK/2=50ステップの全探索が必要…
- これは無理だなー
- しかしとりあえず一瞬で組めそうだから組んでみるか。
- ケース #0, #1, #2 はあったけど #3 で返ってこない
- 諦める
500開く
- こっちの数学的根拠を考えよう
- あと撃墜例作成
- そもそもさっきの方針本当にあってるのか？
- 3未満で切ったから2.5+2.5とかやりかねない…
- というかやってる…
- 2未満で切ろう
- これで大丈夫かなあ…
撃墜タイム
感想
- 500の解法が思いつかないのはまあいいとして、反省したい点はいくつか。
- サンプル通す規則は思いついたが正しいことを全く確信していない時にどうするか
- 「反例を考えるも思いつかず」じゃねーよ
- 小さいケースなら全探索が可能だし、そんなものはすぐ書けるのだから、全探索とランダム生成で反例を探してみるべきだった
- 「3未満で切ろう→2未満で切ろう」って
- どうせ3である根拠も2である根拠もないんだから、
- どうせエセ回答で特攻をかけるなら「任意の切り方を全て考えて最適を選ぶ」という一般化はしておくべきだった。実際これで何故か通るらしい。
- もちろんそれで意味も分からず通して自分の力になるかっていうとならないと思うんですけど、まあ勝負事だからそれでもスコアを狙うところに全力をかけたくもあるわけで。計算量の許す限り一般化できるところはしておいて損はない。
class Nisoku { public:
double theMax(vector <double> cards)
{
sort(cards.begin(), cards.end());
double ans = 0.0;
for(int i=0; 2*i<=cards.size(); ++i)
ans = max(ans,
accumulate(cards.begin()+2*i, cards.end(),
inner_product( cards.begin(), cards.begin()+i,
cards.rend()-2*i,
1.0, multiplies<double>(), plus<double>() ),
multiplies<double>()
)
);
return ans;
}
};
- 全部の値が正なので
- (△*x)+□ ＜ (△+□)*x
- よって、まず足し算し終わった後で掛け算、という流れが最適。
- 全部の値が1.5以上なので
- x≧3 なら x*□＞x+□ (ab≧a+b iff (a-1)(b-1)≧1 より)
- よって、2個足し算したら3以上になることと合わせると、3個以上を足し合わせることはない。
- ここまでの理由から、最適解は
- (a+b)*(c+d)*...*(e+f)*g*h*...*y*z
- という形をしている
- 全部の値が正なので
- x≦y なら (□+x)*y ≧ (□+y)*x
- よって、足し算部の数達a,b,..,e,f ≦ 掛け算部の数達g,h,..,y,z
- 足し算部の２ペア (a+b)*(c+d) だけ取り出して考えると
- この式の値を最大にするには
- 一般性を失わず a≦b,c,d と仮定すると、c,d≦b である
- 要は最大値と最小値が必ず足されてる
- 「周の長さが同じ長方形の面積は正方形に近いほど大きい」のと同じ
- この関係が全ての足し算部のペアに対して成り立つためには、
- 足し算部の数をsortしたらa[0],a[1],...,a[n]だったとすると
- (a[0]+a[n])*(a[1]+a[n-1])*... みたいに最大と最小をgreedyにペアにしていかないといけない
- （そうなってなければ最小と最大が入ってる２ペアを選んだらswapしないといけないのに反する）
- どこからが足し算部に入ってどこからが掛け算部かは、全探索すればよい
