制限なしナップサック

解法：漸化式に沿って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;
}

2017-07-19

AOJ2501

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

解法：商と余のマンハッタン距離を求める　

計算量：O(N)

サンプルを見ればなんとなく分かるだろうか。

図が丁寧に書かれているのが分かりやすい。

但し入力の数字をそれぞれ-1しないと余りがw=4の時の出力が合わない。（それを注視したケースもある）

#include <iostream>
#include <cmath>
using namespace std;

int main(){
  int n,a,b,c,d,p,q,res=10000;
  cin >> n >> a >> b >> c >> d;
  a--;b--;c--;d--;
  for(int w=1;w<=n;w++){
    p = abs(a/w-b/w) + abs(a%w-b%w);
    q = abs(c/w-d/w) + abs(c%w-d%w);
    //cout << p <<" " << q << endl;;
    res = min(res,p+q);
  }
  cout << res << endl;
}

2017-07-17

AOJ2101

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

解法：線形に調べるだけ

コーナーケースがN=1の場合というのは恐れ入った。流石UT

N=1をどう弾いてやるかと思ったが結局最後の出力で無理やりdeficientにする方法で落ち着いた。

#include <cstdio>
  
#define i64 long long
using namespace std;
int main(){
  i64 r,n;
  while(scanf("%lld",&n),n){
    r=0LL;
    for(i64 i=1LL;i*i<n;i++){
      if(!(n%i)){
        r+=i;if(i>1)r+=n/i;
      }
    }
    // printf("%d %d\n",n,r);
    if(r>n){
      puts("abundant number");
    }
    else if(r==n&&n!=1){
      puts("perfect number");
    }
    else{
      puts("deficient number");
    }
  }
}

2017-07-15

AOJ2440

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

解法：やるだけ O(nm)

制約がゆるいのでソートの必要もない

ソートすると二分探索できるのでクエリが早く終わるはず

#include <bits/stdc++.h>
 
using namespace std;
 
int main(){
  int n,m;
  vector<string> u(257);
  string t;
  cin >> n;
  for(int i=0;i<n;i++){
    cin >> u[i];
  }
  cin >> m;
  bool open=false;//opened : true //closed : false
  for(int i=0;i<m;i++){
    cin >> t;
    if(find(u.begin(),u.end(),t)!=u.end()){
      if(open){
        cout << "Closed by " << t << endl;
        open = false;
      }else{
        cout << "Opened by " << t << endl;
        open = true;
      }
    }else{
      cout << "Unknown " << t << endl;
    }
  }
}

そーすにっき

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

DPL_1_C