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
過去問 | | 
寝倒し回
- なんだ最大フローで解ける問題じゃん
- あ。答えが２倍になってる。最後に２で割ればおｋ
- 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;
}
};
コメント
トラックバック - https://topcoder-g-hatena-ne-jp.jag-icpc.org/n4_t/20100730