そーすにっき

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

AOJ2502

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

ボカロかな?()
解法:制限なしナップサック同様のDP 計算量謎
ナップサック問題の重さに幅があるというだけ
数の制約が小さいのでこれでOK

#include <iostream>
#include <vector>
 
using namespace std;
 
int main(){
    int n,m;
    cin >> n;
    int s,l,p;
    int w[400]={0,};
    for(int i=0;i<n;i++){
        cin >> s >> l >> p;
        for(int j=s;j<=l;j++){
            for(int k=0;k+j<=399;k++){
                w[k+j]=max(w[k+j],w[k]+p);
            }
        }
    }
    cin >> m;
    int d[m];
    bool ans = true;
    for(int i=0;i<m;i++){
        cin >> d[i];
        if(!w[d[i]])ans=false;
    }
    if(!ans)cout << -1 << endl;
    else{
        for(int i=0;i<m;i++){
            cout << w[d[i]] << endl;
        }
    }
}

ARC076_D

arc076.contest.atcoder.jp

解法:最小全域木 O(NlogN)?

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

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

4 9
7 6
8 3
12 19
13 5
18 1

yでソートするとこう

18 1
8 3
13 5
7 6
4 9
12 19

で、このサンプル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問題でこの実装量、絶対理想解じゃない気がするんだよなあ…(˘ω˘)

AGC018

大爆散☆

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

AC:Aのみ300点

A

解法:鳩ノ巣応用

全ての数の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;
}

TOEICを無勉強で受けた結果

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

受けた感想:

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

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

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

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

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;
}

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;
}

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;
}