解法：最小全域木　O(NlogN)？

普通に最小全域木をやろうとすると辺の数O(N^2)で死亡するので辺の数を減らす必要がある

とりあえずサンプル2をxで昇順ソートすると

yでソートするとこう

で、このサンプル2の解答は

{((4,9),(7,6)),((7,6),(8,3)),((8,3),(13,5)),((13,5),(12,19)),((8,3),(18,1))}

の辺集合選択で合計の重みは8

つまり、xかyでソートした時に隣り合う点を繋ぐ辺しか採用されることはない

これらの辺の数は2n-2本なのでクラスカルすればいい、という問題

この日のABCでとけなかったので解説を直後に読んでいたので解法は覚えてたけどクラスカル法の実装に不安を覚えたので6割ほど素で書くことを目標に書きましたとさ

結果：全然だめでした

主にjoinの実装が雑すぎたせいで幾度となく閉路を作ってしまうアホやってたとか

結局こちら↓を参考に修正

http://www.prefield.com/algorithm/container/union_find.html

こちらのソースは1配列で経路圧縮とrank実装を同時実装してunionfindをすんごい小さい計算量に圧縮してるけど自分はrank実装してないので少し遅いです

#include <iostream>
#include <deque>
#include <vector>
#include <cstdio>
#include <cstring>
#include <utility>
#include <algorithm>
#include <string>
#include <cmath>
#include <queue>
#include <numeric>
 
#define i64 long long
#define ui64 unsigned long long
#define REP(i,n) for(int (i)=0;(i)<(n);i++)
#define REP2(i,k,n) for(int (i)=(k);(i)<(n);i++)
#define MDIST(a,b) abs(a-b)
#define DIST(a,b) sqrt((a)*(a)+(b)*(b))
#define ATCODER 1000000007
using namespace std;
 
////////////////////////
 
class point{
public:
  int x,y,id;
  point(int x_,int y_,int i_):x(x_),y(y_),id(i_){}
  point():x(0),y(0){}
};
 
bool compx(const point &b,const point &a){
  return b.x==a.x?b.y<a.y:b.x<a.x;
}
bool compy(const point &b,const point &a){
  return b.y==a.y?b.x<a.x:b.y<a.y;
}
 
class edge{
public:
  int f,t,c;
  bool operator<(const edge &a){
    return c<a.c;
  }
  edge(int f_,int t_,int c_):f(f_),t(t_),c(c_){}
};
 
class uf{
public:
  vector<int> r;
  uf(int n):r(n,-1){};
  int find(int x,int y){
    if(root(x)==root(y))return 0;
    if(root(x)<root(y))return -1;
    if(root(x)>root(y))return 1;
  }
  int root(int x){
    if(r[x]==-1)return x;
    else return r[x]=root(r[x]);
  }
  void join(int x,int y){
    x=root(x);y=root(y);
    if(x!=y){
      r[x]=y;
    }
  }
};
 
class graph{
public:
  int vnum;
  vector<edge> E;
  uf u;
  graph(int n):vnum(n),u(n){};
  int kruscal(){
    int res=0;
    sort(E.begin(),E.end());
    for(int i=0,c=0;i<E.size()&&c<vnum-1;i++){
      if(u.find(E[i].f,E[i].t)){
        u.join(E[i].f,E[i].t);
        res+=E[i].c;
        c++;
      }
    }
    return res;
  }
};
 
int main(){
  int n;
  cin >> n;
  int x,y;
  vector<point> p;
  for(int i=0;i<n;i++){
    cin >> x >> y;
    p.push_back(point(x,y,i));
  }
  graph g(n);
  sort(p.begin(),p.end(),compx);
  for(int i=0;i<n-1;i++){
    g.E.push_back(edge(p[i].id,p[i+1].id,min(abs(p[i].x-p[i+1].x),abs(p[i].y-p[i+1].y))));
  }
  sort(p.begin(),p.end(),compy);
  for(int i=0;i<n-1;i++){
    g.E.push_back(edge(p[i].id,p[i+1].id,min(abs(p[i].x-p[i+1].x),abs(p[i].y-p[i+1].y))));
  }
  cout << g.kruscal() << endl;
}

D問題でこの実装量、絶対理想解じゃない気がするんだよなあ…(˘ω˘)

2017-07-23

AGC018

大爆散☆

http://agc018.contest.atcoder.jp/

AC：Aのみ300点

解法：鳩ノ巣応用

全ての数のGCDを取ってKがその数で割り切れればOKなのになんでこんな実装をしたのか自分でもこれが分からない

因みに実行時間1600ms超

#include <iostream>
#include <deque>
#include <vector>
#include <cstdio>
#include <cstring>
#include <utility>
#include <algorithm>
#include <string>
#include <cmath>
#include <queue>
 
#define i64 long long
#define ui64 unsigned long long
#define REP(i,n) for(int (i)=0;(i)<(n);i++)
#define REP2(i,k,n) for(int (i)=(k);(i)<(n);i++)
#define MDIST(a,b) abs(a-b)
#define DIST(a,b) sqrt((a)*(a)+(b)*(b))
#define ATCODER 1000000007
using namespace std;
 
////////////////////////
/* a */
int d[10005];
 
int main(){
  int n,k;
  cin >> n >> k;
  bool f=true;
  int a[n+1],m=0,m2=ATCODER;
  for(int i=0;i<n;i++){
    cin >> a[i];
    if(m<a[i])m=a[i];
    if(a[i]==k)m2=a[i];
  }
  if(m2==k);
  else if(k>m)f=false;
  else{
    for(int i=0;i<n;i++){
      if(!(a[i]%2)){
        d[2]++;
        while(!(a[i]%2))a[i]/=2;
      }
      for(int j=3;j<=a[i]&&j<10005;j+=2){
        if(!(a[i]%j)){
          d[j]++;
          while(!(a[i]%j))a[i]/=j;
        }
      }
    }
    int c = 0;
    for(int i=2;i<10005;i++){
      // cout << d[i] << " ";
      if(d[i]==n&&(k%i)){f=false;break;}
    }
    // cout << endl;
  }
  
  if(f)cout << "POSSIBLE" << endl;
  else cout << "IMPOSSIBLE" << endl;
}

ちゃんとGCDをとるとこう

実行時間50ms

#include <iostream>
#include <deque>
#include <vector>
#include <cstdio>
#include <cstring>
#include <utility>
#include <algorithm>
#include <string>
#include <cmath>
#include <queue>
 
#define i64 long long
#define ui64 unsigned long long
#define REP(i,n) for(int (i)=0;(i)<(n);i++)
#define REP2(i,k,n) for(int (i)=(k);(i)<(n);i++)
#define MDIST(a,b) abs(a-b)
#define DIST(a,b) sqrt((a)*(a)+(b)*(b))
#define ATCODER 1000000007
using namespace std;
 
////////////////////////
/* a */
int d[10005];
 
int gcd(int l,int r){
  int m;
  while(r){
    m = r;
    r = l%r;
    l = m;
  }
  return l;
}
 
int main(){
  int n,k;
  cin >> n >> k;
  int a[n+1],m=0,m2=ATCODER;
  for(int i=0;i<n;i++){
    cin >> a[i];
    if(m<a[i])m=a[i];
    if(a[i]==k)m2=a[i];
  }
  int t=gcd(a[0],a[1]);
  REP2(i,2,n){
    t = gcd(t,a[i]);
  }
  
  if(k<=m&&!(k%t))cout << "POSSIBLE" << endl;
  else cout << "IMPOSSIBLE" << endl;
}

2017-07-23

TOEICを無勉強で受けた結果

TOEICL&R受けるために昨日は何もせず

受けた感想：

・リスニングがむずい　センターとは比べ物にならない

　日本語でも聞き直すことが多い（）自分には辛いものでした

・一方でリーディングは簡単　センターほどの長文が出ず高々第5問程度…だが数が多い　めちゃんこ多い　でも斜め読みができて案外楽だった（明治大学の全学統一試験の英語を受けた経験からか）

まとめ：単語レベルは大体足りていたので問題はリスニング力

2017-07-21

DPL_1_C

http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=DPL_1_C

制限なしナップサック

解法：漸化式に沿ってO(N*W)

漸化式の立て方は

threestones.hateblo.jp

こちらを参考にした。

なかなかこの漸化式に変形しきれないので今のうちは覚えておくほうが吉なのか

#include <iostream>
using namespace std;
int main(){
  int n,mw;
  int v[1005],w[1005];
  cin >> n >> mw;
  for(int i=0;i<n;i++){
    cin >> v[i] >> w[i];
  }
  int dp[mw+2][n];
  fill(&dp[0][0],&dp[mw+1][n-1],0);
  for(int i=1;i<=mw;i++){
    for(int j=0;j<n;j++){
      dp[i][j] = i-w[j]>=0?max(dp[i][j-1],dp[i-w[j]][j]+v[j]):dp[i][j-1];
    }
  }
  cout << dp[mw][n-1] << endl;
}

2017-07-21

AOJ2330

http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=2330

既視感ある問題。偽物の金貨を探すのが有名な気がする。

解法：O(logN)

要素数が等しい（もしくは差が1以下の）3個の集合に分けて2つを天秤にかける操作を繰り返すことで求まるので

N<=3^nとなる最小のnを探して終わり

#include <iostream>
#include <cmath>
using namespace std;
 
int main(){
 int n;
 cin >> n;
 int r=0;
 while(pow(3,r)<n)r++;
 cout << r << endl;
 return 0;
}

2017-07-20

AOJ2406

http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=2406

解法：割ったあまり考えるだけ O(n)

if文の中を書き間違えた結果1回WA

こういうのはホント減らしたい

#include <iostream>

using namespace std;

int main(){
  int n,t,e;
  cin >> n >> t >> e;
  int a[n];
  for(int i=0;i<n;i++){
    cin >> a[i];
  }
  for(int i=0;i<n;i++){
    if((t%a[i])<=e||(t/a[i]*a[i]+a[i])<=(t+e)){
      cout << i+1 << endl;
      return 0;
    }
  }
  cout << -1 << endl;
  return 0;
}

2017-07-19

AOJ2218

http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=2218

解法：場合分けして点数計算O(1)

とにかくinputが分厚い

デバッグが大変　おわり

結構な時間これに費やしたのでもうやりたくない一問

#include <iostream>
#include <vector>
#include <cstdio>
#include <cstring>
#include <cstdlib>
#include <utility>
#include <algorithm>
#include <string>
#include <cmath>
#include <queue>

#define i64 long long
#define ui64 unsigned long long
using namespace std;

int c_points[5][14];
int h_points[10];

struct card{
  int num;
  int mark;
  card(char n_,char m_):num(),mark(){
    switch(m_){
      case 'S': mark = 0; break;
      case 'H': mark = 2; break;
      case 'D': mark = 3; break;
      case 'C': mark = 1; break;
    }
    if(('0'<=n_)&&(n_<='9'))num=n_-'0';
    else{
      switch(n_){
        case 'T': num = 10; break;
        case 'J': num = 11; break;
        case 'Q': num = 12; break;
        case 'K': num = 13; break;
        case 'A': num = 1; break;
      }
    }
  }
  bool operator< (const card& a){
    return num==a.num?mark<a.mark:num<a.num;
  }
};

bool straight(vector<card>& hand){
  for(int i=0;i<4;i++){
    if((hand[i+1].num-hand[i].num==1)||\
        ((!i)&&(hand[4].num==13&&hand[i].num==1)));
    else return false;
  }
  return true;
}

bool flush(vector<card>& hand){
  for(int i=0;i<4;i++){
    if(hand[i].mark!=hand[i+1].mark)return false;
  }
  return true;
}

bool no_pair(vector<card>& hand){
  for(int i=0;i<4;i++){
    if(hand[i].num==hand[i+1].num)return false;
  }
  return true;
}

bool one_pair(vector<card>& hand){
  int p;
  for(int i=0;i<=4;i++){
    if(i==4)return false;
    if(hand[i].num==hand[i+1].num){
      p=i;break;
    }
  }
  for(int i=p+1;i<4;i++){
    if(hand[i].num==hand[i+1].num)return false;
  }
  return true;
}

bool two_pair(vector<card>& hand){
  int p;
  for(int i=0;i<=2;i++){
    if(i==2)return false;
    if(hand[i].num==hand[i+1].num){
      p=i;break;
    }
  }
  if(p==0){
    return hand[2].num==hand[3].num?hand[3].num!=hand[4].num:hand[3].num==hand[4].num;
  }
  if(p==1){
    return hand[3].num==hand[4].num;
  }
}

bool three_card(vector<card>& hand){
  if(hand[0].num==hand[2].num&&hand[0].num!=hand[3].num)return true;
  if(hand[0].num!=hand[1].num&&hand[1].num==hand[3].num&&hand[3].num!=hand[4].num)return true;
  if(hand[0].num!=hand[1].num&&hand[1].num!=hand[2].num&&hand[2].num==hand[4].num)return true;
  return false;
}

bool fullhouse(vector<card>& hand){
  int p;
  if(hand[1].num!=hand[2].num){
    if(hand[0].num!=hand[1].num)return false;
    for(int i=2;i<4;i++){
      if(hand[i].num!=hand[i+1].num)return false;
    }
    return true;
  }else{
    if(hand[3].num!=hand[4].num)return false;
    for(int i=0;i<2;i++){
      if(hand[i].num!=hand[i+1].num)return false;
    }
    return true;
  }
}

bool straight_flush(vector<card>& hand){
  return straight(hand)&&flush(hand);
}

bool four_card(vector<card>& hand){
  return hand[0].num==hand[3].num||hand[1].num==hand[4].num;
}

bool royal_straight_flush(vector<card>& hand){
  if(straight_flush(hand)){
    if(hand[0].num==1&&hand[4].num==13)return true;
  }
  return false;
}


i64 solve(vector<card>& hand){
  sort(hand.begin(),hand.end());
  i64 res=0LL;
  
  for(int i=0;i<5;i++){
    int m_=hand[i].mark;
    int n_=hand[i].num;
    res+=(i64)c_points[m_][n_-1];
  }
  if(royal_straight_flush(hand)){
    res*=(i64)h_points[8];
    return res;
  }
  if(straight_flush(hand)){
    res*=(i64)h_points[7];
    return res;
  }
  if(four_card(hand)){
    res*=(i64)h_points[6];
    return res;
  }
  if(straight(hand)){
    res*=(i64)h_points[3];
    return res;
  }
  if(flush(hand)){
    res*=(i64)h_points[4];
    return res;
  }
  if(fullhouse(hand)){
    res*=(i64)h_points[5];
    return res;
  }
  if(one_pair(hand)){
    res*=(i64)h_points[0];
    return res;
  }
  if(two_pair(hand)){
    res*=(i64)h_points[1];
    return res;
  }
  if(three_card(hand)){
    res*=(i64)h_points[2];
    return res;
  }
  if(no_pair(hand)){
    return (i64)0;
  }
  
  return -1;
}

int main(){
  int n;
  bool flag = false;
  while(1){
    if(!flag){
      cin >> n;
      if(cin.eof())return 0; 
      flag=true;
    }
    fill(&c_points[0][0],&c_points[4][13],0);
    fill(&h_points[0],&h_points[9],0);
    for(int i=0;i<4;i++){
      for(int k=0;k<13;k++){
        cin >> c_points[i][k];
      }
    }
    for(int i=0;i<9;i++){
      cin >> h_points[i];
    }
    char a[3];
    vector<card> hands;
    for(int i=0;i<n;i++){
      for(int k=0;k<5;k++){
        cin >> a;
        hands.push_back(card(a[0],a[1]));
      }
      cout << solve(hands) << endl;
      hands.clear();
    }
    if(flag){
      cin >> n;
      if(cin.eof())return 0; 
      else cout << endl;
    }
  }
  return 0;
}

そーすにっき

なんかいろいろのせておくばしょ

ARC076_D