Hatena::Grouptopcoder

TopCoder Memo@kagamiz

09.09.2012 (Sun)SRM 399 div2

asi1024さん, aroshさん, Respect2Dさん, Lepton_sさん, capythmさんと一緒に参加しました.

結果 : oo-

250 CircularLine (230.74pts)

問題概要 : 環状線になっている駅のうち, a -> b に行く方と b -> aに行く方のうち, 大きい方をすべての駅対について求め, その最小値を求める問題. 入力では隣合う駅同士の距離が与えられる.

解法 : 素直に距離を求めて実装する. 累積和を前もって求めておくと楽.

感想 : ちょっと読解に時間がかかった. 全体で3人目くらいにsubmitした(はず). 良い方.

コード :

#include <cstdio>
#include <cstring>
#include <cstdlib>
#include <cmath>
#include <climits>
#include <cfloat>
#include <map>
#include <utility>
#include <set>
#include <iostream>
#include <memory>
#include <string>
#include <vector>
#include <algorithm>
#include <functional>
#include <sstream>
#include <complex>
#include <stack>
#include <queue>
using namespace std;
static const double EPS = 1e-5;
typedef long long ll;

class CircularLine {
public:
  int longestTravel(vector <int> t) {
    int ans;
    int sum[64];
    
    sum[0] = 0;
    for (int i = 1; i <= t.size(); i++){
    	sum[i] = sum[i - 1] + t[i - 1];
    }
    
    ans = 0;
    for (int i = 0; i < t.size(); i++){
    	for (int j = i + 1; j < t.size(); j++){
    		ans = max(ans, min(sum[j] - sum[i], sum[t.size()] - sum[j] + sum[i]));
    	}
    }
    
    return ans;
  }
}

500 MaximalProduct (491.15pts)

問題概要 : a1 + a2 + ... + ak = s となるように a1, a2, ..., akを定める時, 積a1 * a2 * ... * akの最大値を答えよ.

解法 : 相加・相乗平均の関係より, a1 + a2 + ... ak ≧ k・(a1 * a2 * ... * ak) ^ (1 / k) が成立して, 等号はa1 = a2 = ... = akのときに成立します. このことから, 積を最大化するにはa1, a2, ..., akたちを近い数にしてやったほうがよさそうです.

そこで, s / kをaiたちに分配してやり, 余りをs % k個の項に1ずつ加えてやることで, 最大値を達成できることがわかります.

感想 : わりと「こうしたらよさそうだなー」というのがパッと出てきて, そのとおりに実装できて, 晴れて490点台を取ることが出来ました. これは嬉しい!

コード :

#include <cstdio>
#include <cstring>
#include <cstdlib>
#include <cmath>
#include <climits>
#include <cfloat>
#include <map>
#include <utility>
#include <set>
#include <iostream>
#include <memory>
#include <string>
#include <vector>
#include <algorithm>
#include <functional>
#include <sstream>
#include <complex>
#include <stack>
#include <queue>
using namespace std;
static const double EPS = 1e-5;
typedef long long ll;

class MaximalProduct {
public:
  long long maximalProduct(int s, int k) {
    long long result;
    ll a[20];
    
    for (int i = 0; i < k; i++){
    	a[i] = (ll)(s / k);
    }
    
    for (int i = 0; i < s % k; i++){
    	a[i] += 1;
    }
    
    result = 1;
    for (int i = 0; i < k; i++){
    	result *= a[i];
    }
    
    return result;
  }
}

1000 AvoidingProduct (--.--pts)

問題概要 : 配列aの中に含まれる数を使わずに, |n - x * y * z|を最小化する x, y, zを求めよ. 複数ある場合はx, y, zがそれぞれ最小となるものをもとめよ.

解法 : 解けてませんが, n ≦ 1000程度で, x, y, zはそれぞれ掛け合わせるので, 全探索で余裕で間に合うそうです.ぐぬぬ.

感想 : 因数分解とかしてTLEしてました...くやしいなあ. 1000^3じゃダメそうだな, ではなく, ちゃんと状態が減ることも意識しないといけないと思いました.

最近は250, 500は安定して解けているので, 1000を出来るだけ解けるようにしていきたいです.