POJから。某所で解けなかった問題を今更実装。

問題内容：
入力
RPGのクエストのクリアに必要な経験値A、十分な経験値Bと経験値S、初期状態の経験値D

制約
クエストは各1回選択できる。
クエスト1つが終わると成功失敗にかかわらず経験値を得る。
クエストの成功確率はクエスト選択時の経験値をEXPとして以下の通りに定められる。
・0 (EXP<=A)
・1 (EXP>=B)
・(EXP-A)/(B-A) (それ以外)
クエストの数は10以下、入力の経験値は全て1000以下

出力
全クエストを終了時最も成功確率が高くなる場合の成功確率とクエストの順番

解法
全探索
next_permutationして全通り試してみただけ
if(tmpprob>=maxprob)をif(tmpprob>maxprob)
にするとmaxprob=0の時に順番の出力が不正になりWA

およそ800～900ms要しておりやはりO(n*n!)は辛いと感じる一品

（にしても遅いような気がする）

#include <iostream>
#include <vector>
#include <algorithm>
#include <iomanip>

#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))
using namespace std;
 
////////////////////////

double calc(int a,int b,int d){
  if(d<=a)return 0.0;
  else if(d>=b)return 1.0;
  else return (double)(d-a)/(b-a);
}

int main(){
  int n,d;
  int a[10],b[10],s[10];
  cin >> n >> d;
  for(int i=0;i<n;i++){
    cin >> a[i] >> b[i] >> s[i];
  }
  vector<int> res(n),tmp(n);
  double maxprob=0.0;
  double tmpprob;
  int tmpexp;
  REP(i,n)tmp[i]=i;
  do{
    tmpprob = 1.0;
    tmpexp = d;
    for(int i=0;i<n;i++){
      tmpprob *= calc(a[tmp[i]],b[tmp[i]],tmpexp);
      tmpexp += s[tmp[i]];
    }
    if(tmpprob>=maxprob){
      maxprob = tmpprob;
      res = tmp;
    }
  }while(next_permutation(tmp.begin(),tmp.end()));
  cout << fixed << setprecision(3);
  cout << maxprob << endl;
  for(int i=0;i<n;i++){
    cout << res[i]+1 << " ";
  }cout << endl;
  return 0;
}

2017-08-09

怪盗paizaからの挑戦状

paiza.jp

参加してます

f:id:npkk:20170809010517p:plain

今のところこちら

初日なのでどうせすぐ抜かれてランク外に落ちる予定

コードはトラブルがないよう上げずにいる予定です

初めて長期間のもの（マラソン？）に出るので楽しみです

f:id:npkk:20170809010840p:plain

2017-08-06

ABC069

abc069.contest.atcoder.jp

８位でした。わーい

ただ、簡単な問題だったので速度勝負だったのがなんとも

頭悪い自分は600点問題がDに出ると死んでしまうなさけない人だからねしょうがないね

A：-1して乗算するだけ

B：stringを使えばあら不思議な問題

C：これよくわからず全通り場合分け

2の倍数を2,4の倍数を4,残りを1と書き換える

1)141422...2244...44

2)1414...14141

3)22...2244...44

この3通りのいずれかに並べ替えることができない配列はNo

この時要素数c(1),c(2),c(4)に注目すると

1)はc(1)<=c(4),c(2)!=0

2)はc(2)=0,c(1)+1=c(4)

3)はc(1)=0

これをちゃんと分ければOK

でも縮約できそう＆正しいのか疑問

D：ジグザグに数字を埋めていけばOK　Testcaseで分かるレベルのバグを埋めてしまい手間取って順位が3つくらい落ちた模様

#include <iostream>
#include <deque>
#include <vector>
#include <cstdio>
#include <cstring>
#include <utility>
#include <algorithm>
#include <string>
#include <cmath>
#include <queue>
#include <cmath>
 
#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 main(){
  int a,b;
  cin >> a >> b;
  cout << (a-1)*(b-1) << endl;
}
/* b */
int main(){
  string a;
  cin >> a;
  cout << a[0] << a.size()-2 << a[a.size()-1] << endl;
}
/* c */
int main(){
  int n;
  cin >> n;
  int c1=0,c2=0,c4=0;
  int a;
  REP(i,n){
    cin >> a;
    if(!(a%4))c4++;
    else if(!(a%2))c2++;
    else c1++;
  }
  // cout << n << " " << c2 << " " << c4 << endl;
  if(c1){
    if(c2){
      if(c1<=c4)cout << "Yes" << endl;
      else cout << "No" << endl;
    }else{
      if(c1<=c4+1)cout << "Yes" << endl;
      else cout << "No" << endl;
    }
  }else cout << "Yes" << endl;
}
/* d */
int main(){
  int H,W,N;
  cin >> H >> W >> N;
  int a[N];
  REP(i,N){
    cin >> a[i];
  }
  int d[H][W];
  int f=0;
  REP(i,H){
    if(i%2){
      for(int j=W-1;j+1;j--){
        d[i][j]=f+1;
        if(a[f]>1)a[f]--;
        else f++;
      }
    }else{
      for(int j=0;j<W;j++){
        d[i][j]=f+1;
        if(a[f]>1)a[f]--;
        else f++;
      }
    }
  }
  for(int i=0;i<H;i++){
    for(int j=0;j<W;j++){
      cout << d[i][j] << " ";
    }cout << endl;
  }
}

2017-08-05

DSL_2_B

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

この手のクエリが出たときに系が弱すぎる気がしたのでとりあえずBITの実装をやることに

~~幾何はどうしたって…？忙しさで忘れました~~

とりあえずこんなんでいいかなと精進に際してペタリできるようにちゃんとクラスを実装

最近こういうのちゃんとした方がいいかもなと思い始めたのでやることにしました

#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;
  
////////////////////////
 
class BIT{
  int size;
  vector<i64> tree;
  
public:
  BIT():size(0),tree(0){};
  BIT(int n):size(n),tree(n+1,0){};
  void add(i64 x,int n){
    for(int i=n;i<=size;i+=i&-i){
      tree[i]+=x;
    }
  }
  i64 sum(int s,int t){
    if(s>t)return 0;
    i64 res=0;
    for(int i=t;i>0;i-=i&-i){
      res += tree[i];
    }
    for(int i=s-1;i>0;i-=i&-i){
      res -= tree[i];
    }
    return res;
  }
  i64 get(int n){
    return tree[n];
  }
};
 
int main(){
  int n,q;
  cin >> n >> q;
  BIT d(n);
  int com,x,y;
  for(int i=0;i<q;i++){
    cin >> com >> x >> y;
    if(com)cout << d.sum(x,y) << endl;
    else d.add(y,x);
  }
}

2017-07-30

CGL_1_A

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

なかなか忙しい（大嘘）のでとりあえずなかなか手を出していない幾何問題を

これ実装するだけで相当疲れているあたり重症なので早急に問題を解いておきたい

#include <iostream>
#include <deque>
#include <vector>
#include <cstdio>
#include <cstring>
#include <utility>
#include <algorithm>
#include <string>
#include <cmath>
#include <queue>
#include <iomanip>
 
#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))
using namespace std;
  
////////////////////////
 
struct po{
  double x,y;
  po(double x_,double y_):x(x_),y(y_){};
  po():x(0),y(0){};
};
 
struct vc{
  double x,y;
  vc():x(0),y(0){};
  vc(po f ,po t):x(t.x - f.x),y(t.y - f.y){
    // x = t.x - f.x;
    // y = t.y - f.y
  };
};
 
double norm(vc &a){
  return DIST(a.x,a.y);
}
 
double dot(vc &a,vc &b){
  return a.x*b.x+a.y*b.y;
}
 
int main(){
  double a,b,c,d;
  cin >> a >> b >> c >> d;
  po p(a,b),q(c,d);
  vc v1(p,q);
  cin >> a;
  cout << fixed;
  cout << setprecision(10);
  REP(i,a){
    cin >> b >> c;
    po r(b,c);
    vc v2(p,r);
    double t = dot(v1,v2) / (norm(v1) * norm(v1));
    cout << p.x+v1.x*t << " " << p.y+v1.y*t << endl;
  }
   
}

2017-07-27

AOJ2407

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

解放：やるだけ　O(N)

互い違いが奇数なら先手必勝

偶数なら外側が必勝

#include <iostream>
#include <string>

using namespace std;
int main(){
	string s;
	cin >> s;
	int c = 0;
	for(int i=0;i<s.size()-1;i++){
		if(s[i]!=s[i+1])c++;
	}
	// cout << c << endl;
	if(c%2)cout << 'o' << endl;
	else cout << s[0] << endl;
}

2017-07-26

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

そーすにっき

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

POJ3413 - RPG