2012-01-31
SRM531 Div1 Medium: MonsterFarm
過去問 | | 
なんかEasyより簡単そうに思えたんだけど、やってみて5回目でSystem Test通った程度の体たらくなのでまあEasy頑張っておいてよかった的な。
〈1投目〉ナイーブにシミュレーション。step by stepで100万回ぐらいしか見てない。収束するまでやれてなくてアウト。
〈2投目〉ちまちまstep by stepしてくんじゃなくて自乗を繰り返してみる。まあそれは良いとして。1000000007 周期のやつなんて無いとか高をくくってたのかアウト。
〈3投目〉mod 1000000007系とmod 1000000009系を回して両方で収束を確認できなければ-1、としてみる。2501回回して51回不変、という条件では（手元のcore i7では余裕なのだが）TLEでアウト。
〈4投目〉1001回回して51回不変、にしてみるがまだTLEでアウト
〈5投目〉101回回して51回不変、にしてやっと通った。
最終的なコード：
#include <iostream>
#include <sstream>
#include <cstdio>
#include <cmath>
#include <cctype>
#include <algorithm>
#include <string>
#include <vector>
#include <deque>
#include <stack>
#include <queue>
#include <list>
#include <map>
#include <set>
using namespace std;
typedef long long ll;
#define sz(a) int((a).size())
#define pb push_back
#define rep(var,n) for(int var=0;var<(n);var++)
#define all(c) (c).begin(),(c).end()
#define tr(c,i) for(typeof((c).begin()) i=(c).begin(); i!=(c).end(); i++)
#define found(s,e) ((s).find(e)!=(s).end())
vector<string> split(string str, int delim=' ')
{
vector<string> result;
const char *s = str.c_str();
if (delim == ' ') {
for (const char *p=s; *p; p++) {
if (*p == delim) s++;
else break;
}
if (!*s) return result;
for (const char *p=s; *p; p++) {
if (*p == delim) {
if (s < p) {
string a(s,p-s);
result.push_back(a);
}
s = p + 1;
}
}
if (*s) result.push_back(s);
} else {
for (const char *p=s; *p; p++) {
if (*p == delim) {
string a(s,p-s);
result.push_back(a);
s = p + 1;
if (*s == '\0') result.push_back("");
}
}
if (*s) result.push_back(s);
}
return result;
}
vector<int> map_atoi(vector<string> nums)
{
vector<int> vals(nums.size());
for (int i=nums.size()-1; i>=0; i--) vals[i] = atoi(nums[i].c_str());
return vals;
}
const ll MOD7 = 1000000007LL;
const ll MOD9 = 1000000009LL;
class MonsterFarm {
public:
int numMonsters(vector<string> transforms) {
int N = sz(transforms); // 1-50
vector<vector<ll> > ta(N,vector<ll>(N,0)); // 1-50
vector<vector<ll> > tb(N,vector<ll>(N,0)); // 1-50
rep(a,N) {
vector<int> ns = map_atoi(split(transforms[a],' '));
tr(ns,it){
int b=*it - 1;
// ta[a][b]++;
ta[b][a]++; // TR
tb[b][a]++; // TR
}
}
ll sum7_ = 1, sum9_ = 1, staying=0;
rep(j,101) {
vector<vector<ll> > taa(N,vector<ll>(N,0)), tbb(N,vector<ll>(N,0));
rep(x,N) rep(y,N) {
rep(i,N) taa[x][y] = (taa[x][y] + ta[x][i]*ta[i][y]) % MOD7;
rep(i,N) tbb[x][y] = (tbb[x][y] + tb[x][i]*tb[i][y]) % MOD9;
}
ll sum7 = 0; rep(i,N) sum7 = (sum7 + taa[i][0]) % MOD7;
ll sum9 = 0; rep(i,N) sum9 = (sum9 + tbb[i][0]) % MOD9;
ta = taa;
tb = tbb;
if (sum7 == sum7_ && sum9 == sum9_) {
staying++;
if (staying==51) return (int)(sum7 % MOD7);
} else {
staying=0;
}
sum7_ = sum7;
sum9_ = sum9;
}
return -1;
}
};
コメント
トラックバック - http://topcoder.g.hatena.ne.jp/n4_t/20120131
2010-07-30
SRM477 Easy: Islands
過去問 | | 
寝倒し回。
- 隣接する六角形のマス目同士が異なる属性なら海岸。それだけ
- 最近HHKB触ってなくて打鍵がもたつく...
- 229.37 (8'40'')
- passed
- とりあえずこれが取れてればレーティングは微増だったっぽい
using namespace std;
#define sz(a) int((a).size())
#define pb push_back
#define FOR(var,from,to) for(int var=(from);var<=(to);var++)
#define rep(var,n) for(int var=0;var<(n);var++)
#define all(c) (c).begin(),(c).end()
class Islands {
public:
int beachLength(vector <string> kingdom) {
int R=sz(kingdom),C=sz(kingdom[0]);
int b=0;
rep(r,R){
rep(c,C-1){
if(kingdom[r][c]!=kingdom[r][c+1])b++;
}
}
for(int r=0;r<R-1;r+=2){
rep(c,C){
if(kingdom[r][c]!=kingdom[r+1][c])b++;
}
rep(c,C-1){
if(kingdom[r][c+1]!=kingdom[r+1][c])b++;
}
}
for(int r=1;r<R-1;r+=2){
rep(c,C){
if(kingdom[r][c]!=kingdom[r+1][c])b++;
}
rep(c,C-1){
if(kingdom[r][c]!=kingdom[r+1][c+1])b++;
}
}
return b;
}
};
SRM477 Medium: PythTriplets
過去問 | | 
寝倒し回
- なんだ最大フローで解ける問題じゃん
- GCJの問題でこういう系のなかった？
- 最大マッチングを求める問題は、全てのメンバーを二部グラフの両側に置いて、可能な結合パターンのところに容量１のパイプを敷いて、ソースとシンクを別途設け、ソースから二部グラフの一方の全メンバーにそれぞれ容量１のパイプを、二部グラフのもう一方の全メンバーからシンクへそれぞれ容量１のパイプを敷き、ソースからシンクへの最大フローを求めればよい。
- ２階調画像のノイズ消去に同様の手法が使えるのが面白いです
- あ。答えが２倍になってる。最後に２で割ればおｋ
- submitted
- 396.39 (15'22'')
- failed system test...
- GCDチェック忘れてるし
- もう馬鹿馬鹿馬鹿
- gcd()いれたらpassed system test
- こういう抜けた所はどうにかしたい...これも取れてればrating1700行けるところなのに
- 以下、通るコード。コメントアウトしてるgcd()の部分が抜け。
- うわ。皆さんの日記みたらGCD忘れが意外に多い。ナカーマ＞＜
using namespace std;
typedef long long ll;
typedef vector<int> vi;
typedef vector<vector<int> > vvi;
typedef vector<string> vs;
typedef vector<long long> vll;
#define sz(a) int((a).size())
#define pb push_back
#define FOR(var,from,to) for(int var=(from);var<=(to);var++)
#define rep(var,n) for(int var=0;var<(n);var++)
#define all(c) (c).begin(),(c).end()
#define tr(c,i) for(typeof((c).begin()) i=(c).begin(); i!=(c).end(); i++)
#define found(s,e) ((s).find(e)!=(s).end())
vector<string> split(string str, int delim=' ')
{
vector<string> result;
const char *s = str.c_str();
if (delim == ' ') {
for (const char *p=s; *p; p++) {
if (*p == delim) s++;
else break;
}
if (!*s) return result;
for (const char *p=s; *p; p++) {
if (*p == delim) {
if (s < p) {
string a(s,p-s);
result.push_back(a);
}
s = p + 1;
}
}
if (*s) result.push_back(s);
} else {
for (const char *p=s; *p; p++) {
if (*p == delim) {
string a(s,p-s);
result.push_back(a);
s = p + 1;
if (*s == '\0') result.push_back("");
}
}
if (*s) result.push_back(s);
}
return result;
}
vector<int> map_atoi(vector<string> nums)
{
vector<int> vals(nums.size());
for (int i=nums.size()-1; i>=0; i--) vals[i] = atoi(nums[i].c_str());
return vals;
}
string join(vector<string> strs, const string &delim="")
{
int n=strs.size(); if (n==0) return "";
stringstream ss;
ss << strs[0];
for(int i=1;i<n;i++) { ss << delim << strs[i]; }
return ss.str();
}
#define infty 987654321
int maximumFlow(const vector<vector<int> >& capacity, int s, int t) {
int w = capacity.size();
// residual networks
vector<vector<int> > resid(w, vector<int>(w,0));
for(int j=0; j<w-1; ++j){
for(int k=j+1; k<w; ++k){
resid[j][k] = capacity[j][k];
resid[k][j] = 0;
}
}
// find another way
for (int total=0; ;++total) {
bool another_way = false;
vector<int> prev(w, infty);
queue<pair<int,int> > q; q.push(pair<int,int>(s,-1));
while (!q.empty()) {
pair<int,int> p = q.front();
int node = p.first, prev_node = p.second;
q.pop();
prev[node] = prev_node;
if (node==t) { another_way = true; break; }
rep(i,w) {
if (resid[node][i] == 0) continue;
if (prev[i] < infty) continue;
q.push(pair<int,int>(i,node));
}
}
// no more ways
if (!another_way) return total;
for (int node=t; node!=s; node=prev[node]) {
int prev_node = prev[node];
resid[prev_node][node]--;
resid[node][prev_node]++;
}
}
return 0;
}
//ll gcd(ll m, ll n)
//{
// if (m == 0 || n == 0) return 0;
// if (m == 1 || n == 1) return 1;
// if (m == n) return m;
// while (1) {
// if (m == 0) return n;
// if (n == 0) return m;
// if (m > n) m %= n; else n %= m;
// }
//}
class PythTriplets {
private:
ll sq(ll zz){
ll zd = (ll)sqrt((double)zz);
return (zd*zd == zz);
}
bool pyth(ll x, ll y){
// if(gcd(x,y)>1) return false;
return sq(x*x + y*y);
}
public:
int findMax(vector <string> stick) {
vector<int> st=map_atoi(split(join(stick)));//1-999999 x 1-200
int n=sz(st);
int w = 1+n+n+1;
vector<vector<int> > capacity(w, vector<int>(w,0));
rep(i,n) capacity[0][1+i] = capacity[1+n+i][1+n+n] = 1;
rep(i,n)rep(j,n){
if(i==j)continue;
if(pyth(st[i],st[j])) capacity[1+i][1+n+j]=1;
}
int maxflow = maximumFlow(capacity, 0, 1+n+n);
return maxflow/2;
}
};
トラックバック - http://topcoder.g.hatena.ne.jp/n4_t/20100730
2010-06-06
SRM472 Div1 Easy(250): PotatoGame
Nimとかこういう石取り・芋喰い系ゲームが苦手…
- 普通だったらDPで解くような問題なのだが
- 今回は1e9までなので、DPしてたら間に合わない(ローカルマシンで60秒超)。パターンを見つけて数式を書くだけ
- 大抵、両者が最適手を打つ、というのをすごく難しく考えてしまって破滅する
- 落ち着いて順序を追って考えたらある重要かつ初歩的な事実に気がついた
芋数がNのとき、それは先手必勝か後手必勝かのどちらかしかない
次回、眠くても目を瞑ってても解けるようにメモしておく。恥ずかしい記事なのでDiv1の人は見ないようにｗ
N=0: もう取るものがない。先手必敗・後手必勝。// dp[0] = G;
N=1: 先手は1をとるしかない。残りが0(後手必勝)なので先手必勝。// dp[1] = S;
N=2: 先手は1をとるしかない。残りが1(先手必勝)なので後手必勝。// dp[2] = G;
N=3: 先手は1をとるしかない。残りが2(後手必勝)なので先手必勝。// dp[3] = S;
N=4: 先手は1をとるか4をとるか選べる。
- 4をとれば残りが0(後手必勝)なので勝てる
- 1をとれば残りが3(先手必勝)なので負ける
- 先手必勝手（＝取った先が後手必勝）がある場合はそれを取る（のが最適手というものだ）。どれを取っても先手必勝なら仕方がない（後手必勝）
- というわけでこの場合、4を取って先手必勝。// dp[4] = S;
N=5: 先手は1をとるか4をとるか選べる。
- 4をとれば残りが1(先手必勝)なので負ける
- 1をとれば残りが4(先手必勝)なので負ける
- というわけで、勝てる手がないので先手必敗。// dp[5] = G;
N=6: 先手は１をとるか４をとるか選べる。
- 4をとれば残りが2(後手必勝)なので勝てる。
- 1をとれば残りが5(後手必勝)なので勝てる。
- というわけで、どちらを取っても勝てる。先手必勝。// dp[6] = S;
こんな感じのことをDPで調べていけばよい。
if(i>=1 && dp[i-1]==G) dp[i]=S; else if(i>=4 && dp[i-4]==G) dp[i]=S; else if(i>=16 && dp[i-16]==G) dp[i]=S; ... else dp[i]=G; // 1手先は後手必勝でないなら先手必勝。
適当なNまで見てみると
{ G, S, G, S, S, G, S, G, S, S, G, S, G, S, S, G, S, G, S, S, G, S, G, S, S, ... }
といった感じで、周期５でパターンが繰り返されている。N mod 5が0か2ならG, 1,3,4ならTが来る。（この問題ではGが後手の"Hanako"、Sが先手の"Taro"に対応）
答えが
return (N%5==0||N%5==2)?"Hanako":"Taro";
でいいのかどうか、プログラムを書いてDP結果と照合してみたら、1<=N<=1e9の範囲で完全に一致した。（が、このチェックには1分46秒かかった。DPで解いていたら到底間に合わない）
トラックバック - http://topcoder.g.hatena.ne.jp/n4_t/20100606
2010-06-03
Google Code Jam 2009: Round 2
過去問 | | 
- 去年のRound 2の問題を見てみた
- 去年は1758/3000位だったらしい。(500位で通過)
- しかし同じ問題だったらアウトな感じ
A. Crazy Rows
- [2,1,1,0] みたいな配列を [0,1,2,3] かそれ以下にするswapの回数。
- v[i]>iの場合、最初に手に入るi以下の数字を持ってくる。
- その繰り返し(0..N-1)でswap回数の和を取れば終わる
#include <iostream>
#include <sstream>
#include <algorithm>
#include <string>
#include <vector>
#include <deque>
#include <stack>
#include <queue>
#include <list>
#include <map>
#include <set>
#include <cstdio>
#include <cmath>
#include <cctype>
using namespace std;
#define rep(var,n) for(int var=0,lim=(n);var<lim;var++)
int main(){
int T; cin >> T;//1..60
rep(t,T){
int N; cin >> N;//1..40
vector<int> m(N,-1);
rep(n,N){
string s; cin >> s;
rep(i,N) if(s[i]=='1')m[n]=i;
}
int k=0;
rep(n,N){
if (m[n]<=n) continue;
for(int i=n+1;i<N;++i){
int t=m[i];
if(t<=n) { //n..)i
k += i-n;
for(int j=i;j>n;--j) m[j]=m[j-1];
m[n] = t;
break;
}
}
}
printf("Case #%d: %d\n", t+1, k);
}
return 0;
}
B. A Digging Problem
- あー。
- あとで見る
C. Stock Charts
- クロスないしタッチしてるかどうか見て、組分けの考えられる組み合わせを全て試す方法ではsmallならなんとか時間に間に合う。でもIncorrectだった。グラフ問題。最大フローとかで何とかなるような気がするんだけどどう解いたらよいか
- Contest Analysis読んだ。二部グラフの最大マッチングに落とせるので確かに最大フロー。
- すぱげってぃこーどからコピペしたmaximumFlowだと思った結果が出ない。確認のために自分で書いてみる（というか1年半前の自分からコピペ）
#include <iostream>
#include <sstream>
#include <algorithm>
#include <string>
#include <vector>
#include <deque>
#include <stack>
#include <queue>
#include <list>
#include <map>
#include <set>
#include <cstdio>
#include <cmath>
#include <cctype>
using namespace std;
#define rep(var,n) for(int var=0,lim=(n);var<lim;var++)
#define infty 987654321
int maximumFlow(const vector<vector<int> >& capacity, int s, int t) {
int w = capacity.size();
// residual networks
vector<vector<int> > resid(w, vector<int>(w,0));
for(int j=0; j<w-1; ++j){
for(int k=j+1; k<w; ++k){
resid[j][k] = capacity[j][k]; // = capacity[j][k] - flow[j][k]
resid[k][j] = 0; // = flow[k][j]
}
}
// find another way
for (int total=0; ;++total) {
bool another_way = false;
vector<int> prev(w, infty);
queue<pair<int,int> > q; q.push(pair<int,int>(s,-1));
while (!q.empty()) {
pair<int,int> p = q.front();
int node = p.first, prev_node = p.second;
q.pop();
prev[node] = prev_node;
if (node==t) { another_way = true; break; }
rep(i,w) {
if (resid[node][i] == 0) continue;
if (prev[i] < infty) continue;
q.push(pair<int,int>(i,node));
}
}
// no more ways
if (!another_way) return total;
for (int node=t; node!=s; node=prev[node]) {
int prev_node = prev[node];
resid[prev_node][node]--;
resid[node][prev_node]++;
}
}
return 0;
}
int main(){
int T; cin >> T;
rep(t,T){
int n, k; cin >> n >> k; // 1..100, 2..25
vector<vector<int> > price(n,vector<int>(k));
rep(j,n) rep(i,k) cin >> price[j][i]; //0..1e6
vector<vector<bool> > dir(n,vector<bool>(n,false));
int w=1+n+n+1;
vector<vector<int> > capacity(w, vector<int>(w,0));
rep(i,n) capacity[0][1+i] = 1;
rep(i,n) {
rep(j,n) {
if (i==j) continue;
bool x=true;
rep(h,k) if (price[i][h] >= price[j][h]) { x=false; break; }
if (x) capacity[1+i][1+n+j] = 1;
}
}
rep(i,n) capacity[1+n+i][1+n+n] = 1;
int maxflow = maximumFlow(capacity, 0, 1+n+n);
int ans = n - maxflow;
printf("Case #%d: %d\n", 1+t, ans);
}
return 0;
}
D. Watering Plants
- smallは簡単に解ける。問題はlarge
- あとで見る
トラックバック - http://topcoder.g.hatena.ne.jp/n4_t/20100603
2010-05-28
Member SRM 471 Hard(1000): ConstructPolyline
- たまにはDiv1 Hard問題も眺めてみないとSTL使いこなし以上の実力がつかないと思いHard問題を開いてみる
３次元空間で、最大50本の線分が与えられる。これをクロスさせずに繋いでいった時の両端の距離の最大値を求める
- ノートにうにうに3次元（的な）線を描いてみて、クロスするのって戻ってるってことだから最大値なら必然的にクロスしないのでは？と思った（が証明したわけではない）
- 線分(x_i,y_i,z_i)をどっち向きに繋げるか。p_i={1 or -1}を掛けるとして、合計の長さ（の２乗）は
は50x50個前もって計算できる。正かもしれないし負かもしれない。零もありうるよね
,
（それぞれ+1か-1）の組み合わせが
通りあるので、これを調整して
を最大化したい。
1. サンプルケースは全部通るけどnが大きいと間違いなくTLEなコード：
- というわけでまずは愚直に。
とか馬鹿なの？死ぬの？
#define rep(var,n) for(int var=0;var<(n);var++)
typedef long long ll;
class ConstructPolyline {
int n;
// inline int sign(int x){ return x ? (x > 0 ? 1 : -1) : 0; }
public:
long long maximizeLength(vector <int> x, vector <int> y, vector <int> z) {
n = x.size();
vector<vector<int> > aij(n,vector<int>(n,0));
// vector<vector<int> > sij(n,vector<int>(n,0));
rep(i,n) rep(j,n) {
aij[i][j] = x[i]*x[j] + y[i]*y[j] + z[i]*z[j];
// sij[i][j] = sign(aij[i][j]);
sum += (ll)abs(aij[i][j]);
}
ll lim=1LL << n, summax = 0;
for(ll m=0; m<lim; m++) { // ... 2^50
ll sum = 0;
rep(i,n) {
int pi = (m & (1LL << i)) ? 1 : -1;
rep(j,n) {
int pj = (m & (1LL << j)) ? 1 : -1;
sum += pi * pj * aij[i][j];
}
}
summax = max(summax,sum);
}
return summax;
}
};
- サンプルテストは全部通るけど...N=50に行くまでもなくTLE死の予感
- 2^50通りの計算に相当する部分を時間内で終わらせるにはどうしたらいいか。
- LayCurse先生曰く：
でも，2^50通りしか考えれないし，リスタート＋ランダム局所探索で通っちゃったりするんじゃない？
そう思ったら通る気がしてきたぞ？
いまから，一瞬で局所探索書いて，サブミットして通したら上位狙える．
いいや，やっちゃえ．
（中略）
てか，Hard，やっぱりランダムで通るんかい．まぁ，想定解法ではないはずなのでのちのち勉強．
SRM471 DIV1 参加記録 - ゲームにっき(仮)
コンテスト途中で通信が切れ、再ログインしてもコンテストへのアクセスができずおそらくノーゲーム（だがなぜかレーティングに反映されている感じ・・・ノーゲームになったかどうかとか、TopCoder主催側の公式アナウンスとかってあるとしたらどこで見られるの？）なので解説とか出てなくて、とりあえずあの状況あの時間で1000点問題を通していた超人達(Petrとktuan)のコードを見てみた。なるほど、こういうのでテスト通るのか。勉強になる。
- 以下、コードはコピペできなかったのでスクリーンショットを見て手打ちです
Petr
[image]
import java.util.*;
public class ConstructPolyline {
static class Unit {
double x;
double y;
double z;
Unit(double x, double y, double z) {
double len = Math.sqrt(x*x + y*y + z*z);
if (Math.abs(len) < 1e-12) {
this.x = 0;
this.y = 0;
this.z = 0;
} else {
this.x = x / len;
this.y = y / len;
this.z = z / len;
}
}
}
long res;
int[] x;
int[] y;
int[] z;
public long maximizeLength(int[] x, int[] y, int[] z) {
this.x = x;
this.y = y;
this.z = z;
Unit[] u = new Unit[x.length];
for (int i=0; i<x.length; ++i)
u[i] = new Unit(x[i],y[i],z[i]);
res = 0;
for (int i=0; i<x.length; ++i)
for (int j=i+1; j<x.length; ++j)
for (int k=j+1; k<x.length; ++k) {
Unit sum = new Unit(u[i].x + u[j].x + u[k].x,
u[i].y + u[j].y + u[k].y,
u[i].z + u[j].z + u[k].z);
verify(sum);
double ki = 0.439156431;
double kj = 0.389754875;
double kk = 0.572398221;
sum = new Unit(ki*u[i].x + kj*u[j].x + kk*u[k].x,
ki*u[i].y + kj*u[j].y + kk*u[k].y,
ki*u[i].z + kj*u[j].z + kk*u[k].z);
verify(sum);
}
Random r = new Random(4392714938214321L);
for (int i=0; i<100000; ++i) {
Unit sum = new Unit(r.nextDouble()*2-1, r.nextDouble()*2-1, r.nextDouble()*2-1);
verify(sum);
}
return res;
}
private void verify(Unit sum){
long sx=0;
long sy=0;
long sz=0;
for (int i=0; i<x.length; ++i) {
double prod = sum.x * x[i] + sum.y * y[i] + sum.z * z[i];
if (prod >= 0) {
sx += x[i];
sy += y[i];
sz += z[i];
} else {
sx -= x[i];
sy -= y[i];
sz -= z[i];
}
}
res = Math.max(res, sx*sx + sy*sy + sz*sz);
}
}
- スタート地点からある方向に向かうとして、N個のベクトルがその方向に進む感じなら +1, 戻る感じなら -1 を掛けたベクトルを加算。てのをいろいろな向きで試して最大値を得ている
- N個のベクトルから任意の３つを取り出して足したもの
- なぞの係数を掛けたもの
- あと十万件ランダムで
- なるほど、内積を使って進むか戻るか調べるのか。
- 仮定した進行方向に対してベクトルが成す角度がθなら、内積は|a||b|cosθなので90度未満（進む）なら正、90度（横）で0、90度超（戻る）なら負だ
ktuan
[image]
#include <vector>
#include <list>
#include <map>
#include <set>
#include <deque>
#include <stack>
#include <bitset>
#include <algorithm>
#include <functional>
#include <numeric>
#include <utility>
#include <sstream>
#include <iostream>
#include <iomanip>
#include <cstdio>
#include <cmath>
#include <cstdlib>
#include <ctime>
#include <queue>
using namespace std;
#define Rep(i,n) for(int i=0;i<(n);++i)
#define For(i,a,b) for(int i=(a);i<=(b);++i)
#define Ford(i,a,b) for(int i=(a);i>=(b);--i)
#define fi first
#define se second
#define pb push_back
#define MP make_pair
typedef pair<int,int> PII;
typedef vector<int> VI;
class ConstructPolyline {
public:
long long maximizeLength(vector <int> x, vector <int> y, vector <int> z);
};
const int sogoc = 1200;
int h[55];
int n;
long long ConstructPolyline::maximizeLength(vector <int> x, vector <int> y, vector <int> z) {
double d = 2 * M_PI / sogoc;
n = x.size();
long long result = 0;
for(int i=0; i<sogoc; ++i) {
double alpha = i*d;
double vz = sin(alpha);
double tt = cos(alpha);
for (int j=0; j<sogoc; ++j) {
double beta = j*d;
double vx = tt * cos(beta);
double vy = tt * sin(beta);
for (int t=0; t<x.size(); ++t) {
double r = vx*x[t] + vy*y[t] + vz*z[t];
if (r>0) h[t] = 1;
else h[t] = -1;
}
int tx=0, ty=0, tz=0;
for (int t=0; t<x.size(); ++t) {
tx += h[t] * x[t];
ty += h[t] * y[t];
tz += h[t] * z[t];
}
long long cur = (long long)tx*tx + (long long)ty*ty + (long long)tz*tz;
if (cur > result) result = cur;
}
}
return result;
};
トラックバック - http://topcoder.g.hatena.ne.jp/n4_t/20100528