日々精進

aikoと旅行とプログラミング

【AOJ DPL1】B: Combinatorial - 0-1 Knapsack Problem

AOJ プログラミング

問題

ナップザック問題 | 動的計画法 | Aizu Online Judge

方針

  • 各要素を入れる, 入れないというパターンを試して価値を高める.
  • ただし, すべての商品に対して上のパターンを試すと {O(2^N)}となるため終わらない.
  • 動的計画法を用いることにより, {O(NW)}にまで落とすことができる.
  • {dp[i][j]:=} i個までのものを使って重さjのナップサックに詰めたときの最大値 として計算する.

コード

#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<cmath>
#include<ctime>
#include<cctype>
#include<climits>
#include<iostream>
#include<string>
#include<vector>
#include<map>
#include<list>
#include<queue>
#include<deque>
#include<algorithm>
#include<numeric>
#include<utility>
#include<complex>
#include<memory>
#include<functional>
 
#define rep(i, n) REP(i, 0, n)
#define REP(i, a, n) for(int i = a ; i < (int)n ; i++)

using namespace std;
 
signed main(){
  int w[1001];
  int v[1001];
  int dp[101][10001];
  int N, W;
  cin >> N >> W;
  REP(i, 1, N+1){
    cin >> v[i] >> w[i]; 
  }
  rep(i, 101){
    rep(j, 1001){
      dp[i][j] = 0;
    }
  }
 
  REP(i, 1, N+1){
    REP(j, 1, W+1){
      if(j >= w[i]){
        dp[i][j] = max(dp[i-1][j], dp[i-1][j-w[i]] + v[i]);
      }else{
        dp[i][j] = dp[i-1][j];
      }   
    }
  }
   
  cout << dp[N][W] << endl;
}

【AOJ DPL1】A: Combinatorial - Coin Changing Problem

AOJ プログラミング

問題

コイン問題 | 動的計画法 | Aizu Online Judge

方針

  • 動的計画法を用いて解く.
    • dp[i] := i円支払うときのコインの最小枚数

コード

#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<cmath>
#include<ctime>
#include<cctype>
#include<climits>
#include<iostream>
#include<string>
#include<vector>
#include<map>
#include<list>
#include<queue>
#include<deque>
#include<algorithm>
#include<numeric>
#include<utility>
#include<complex>
#include<memory>
#include<functional>

#define rep(i, n) REP(i, 0, n)
#define REP(i, a, n) for(int i = a ; i < (int)n ; i++)
#define eps 1e-14
#define INF 1e9

using namespace std;

int c[30];
int dp[50001];

signed main(){
  int n, m;
  cin >> n >> m;
  rep(i, m){
    cin >> c[i];
  }
  
  rep(i, 50001){
    dp[i] = INF;
  }
  
  // dp[i] := i円払うときの最小の枚数
  dp[0] = 0;
  rep(i, m){    
    for(int j = 0 ; j + c[i] <= n ; j++){
      dp[j+c[i]] = min(dp[j + c[i]], dp[j] + 1);
    }
  }

  cout << dp[n] << endl;
}

DPってどうやって考えたら良いのかいまいちわからない。（解法を見たらなんとなくわかるんだが…）

【AOJ 2102】Rummy

AOJ プログラミング 競プロ

問題

Rummy | Aizu Online Judge

方針

  • 数字と記号のペアが与えられるので, 全通り試してセットであるか試す.
  • セットである条件は
    1. 3枚とも同じ色であること
    2. 番号がすべて同じか連番になっていること（ただし, 8, 9, 1のような連番は認められない）
  • これが3枚3セットになっているか判定する.

コード

#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<cmath>
#include<ctime>
#include<cctype>
#include<climits>
#include<iostream>
#include<string>
#include<vector>
#include<map>
#include<list>
#include<queue>
#include<deque>
#include<algorithm>
#include<numeric>
#include<utility>
#include<complex>
#include<memory>
#include<functional>

#define rep(i, n) REP(i, 0, n)
#define REP(i, a, n) for(int i = a ; i < (int)n ; i++)
#define mp make_pair

using namespace std;

typedef pair<int, string> pis;

int n;
pair<int, string> v[9];
int num[9];
string mark[9];

bool check_num(pis a, pis b, pis c){
  if(a.first > b.first) swap(a, b);
  if(a.first > c.first) swap(a, c);
  if(b.first > c.first) swap(b, c);
  return (a.first + 1 == b.first && b.first + 1 == c.first) || (a.first == b.first && b.first == c.first);
}

bool check_mark(pis a, pis b, pis c){
  return a.second == b.second && b.second == c.second;
}

bool check(){
  bool ret = true;
  rep(i, 3){
    ret &= (check_num(v[i*3], v[i*3+1], v[i*3+2]) && check_mark(v[i*3], v[i*3+1], v[i*3+2]));
  }
  return ret;
}

signed main(){
  bool flag;
  cin >> n;
  while(n--){
    flag = false;
    rep(i, 9) cin >> num[i];
    rep(i, 9){
      cin >> mark[i];
      v[i] = mp(num[i], mark[i]);
    }

    do{
      if(check()){
        cout << 1 << endl;
        flag = true;
        break;
      }
    }while(next_permutation(v, v+9));
    if(!flag) cout << 0 << endl;
  }
}

【AOJ ALDS1_13】B: Heuristic Search - 8 Puzzle

AOJ プログラミング

問題

| アルゴリズムとデータ構造 | Aizu Online Judge

方針

  • DFSをして正しい並びになったかを判定し, その時のターン数を返す.
  • 探索した盤面はフラグを立てておき, 同じ状態を２回以上探索しないようにする.
    • mapって比較の"<“が定義されてないと使えないのを初めて知った.

コード

#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<cmath>
#include<ctime>
#include<cctype>
#include<climits>
#include<iostream>
#include<string>
#include<vector>
#include<map>
#include<list>
#include<queue>
#include<deque>
#include<algorithm>
#include<numeric>
#include<utility>
#include<complex>
#include<memory>
#include<functional>

#define rep(i, n) REP(i, 0, n)
#define REP(i, a, n) for(int i = a ; i < (int)n ; i++)

using namespace std;

int dx[4]={1,0,-1,0};
int dy[4]={0,1,0,-1};

struct Puzzle{
  int field[9];
  int space;
  int turn;

  bool operator < (const Puzzle& a) const{
    rep(i, 9){
      if(a.field[i] == field[i]) continue;
      return field[i] >  a.field[i];
    }
    return false;
  }
};

bool check(Puzzle p){
  rep(i, 9){
    if(p.field[i] != i+1) return false;
  }
  return true;
}

int solve(Puzzle in){
  queue<Puzzle> q;  
  map<Puzzle, bool> mp;

  q.push(in);
  mp[in] = true;
  
  // bfs
  while(!q.empty()){
    Puzzle p = q.front(); q.pop();
    if(check(p)) return p.turn;
    int x = p.space % 3;
    int y = p.space / 3;
    rep(i, 4){
      int nx = x + dx[i];
      int ny = y + dy[i];
      if(nx < 0 || 2 < nx || ny < 0 || 2 < ny) continue;
      Puzzle tmp = p;
      swap(tmp.field[p.space], tmp.field[3 * ny + nx]);
      tmp.space = 3 * ny + nx;
      if(mp[tmp] == false){
    mp[tmp] = true;
    tmp.turn++;
    q.push(tmp);
      }
    }
  }
  return -1;
}

signed main(){
  Puzzle in;
  
  rep(i, 9){
    cin >> in.field[i];
    if(in.field[i] == 0){
      in.field[i] = 9;
      in.space = i;
    }    
  }

  in.turn = 0;
  cout << solve(in) << endl;
}

【ICPC World Final 2017】E : Need for Speed

プログラミング 競プロ

問題

Need for Speed – Kattis, ICPC

  • ある区間の距離と移動速度がそれぞれ {d_i, s_i}として与えられる.
  • {s_i}は実際の速度s+c(cは定数)として表示されている.
  • 実際にかかった時間tが与えられるので, cが何であるかを求めよ.

方針

  • {\sum_{i=1}^{n} \frac{d_i}{s_i-c} = t}となったときのCが答えとなる.
  • 二分探索を行い, Cを試して答えを求める.
  • 区間の設定が重要で, sの最小値から[tex: {106+1000}]までの区間で二分探索した.

コード

#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<cmath>
#include<ctime>
#include<cctype>
#include<climits>
#include<iostream>
#include<string>
#include<vector>
#include<map>
#include<list>
#include<queue>
#include<deque>
#include<algorithm>
#include<numeric>
#include<utility>
#include<complex>
#include<memory>
#include<functional>

#define rep(i, n) REP(i, 0, n)
#define REP(i, a, n) for(int i = a ; i < (int)n ; i++)
#define eps 1e-14

using namespace std;

signed main(){
  int n;
  double t;
  double d[1001], s[1001];
  double _min = 1500.0, _max = -1200;

  scanf("%d %lf", &n, &t);
  rep(i, n){
    scanf("%lf %lf", &d[i], &s[i]);
    _min = min(s[i], _min);
  }
  
  double right = _min; 
  double left = -1001000;
  double c;
  double prev = 0.0;
  
  rep(i, 100){  
    c = (left + right)/2.0;
    double sum = 0.0;
    rep(i, n) sum += (d[i] / (s[i] - c));  
    if(fabs(sum - t) < eps){
      break;
    }else if(sum > t){
      right = c;
    }else{
      left = c;
    }
    prev = sum;
  }
  printf("%.9f\n", -c);
}
``

【AOJ 2015】Square Route

AOJ プログラミング 競プロ

問題

Square Route | Aizu Online Judge

方針

  • 道と道の間隔が与えられるので, 正方形の区画がいくつあるか数える問題
  • すべてのパターンを試す方法では, {O(N^2 M^2)}となり終わらない.
  • そこで, 辺の長さの全パターンを予め求め, その出現個数を元に計算する.（この場合は {O(N^2)}となる）
    • 長さが出現する場所, 順序はあまり関係がないため.

コード

#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<cmath>
#include<ctime>
#include<cctype>
#include<climits>
#include<iostream>
#include<string>
#include<vector>
#include<map>
#include<list>
#include<queue>
#include<deque>
#include<algorithm>
#include<numeric>
#include<utility>
#include<complex>
#include<memory>
#include<functional>

#define rep(i, n) REP(i, 0, n)
#define REP(i, a, n) for(int i = a ; i < (int)n ; i++)
#define ALL(v) v.begin(), v.end()
#define pb push_back
#define m0(x) memset(x, 0, sizeof(x))

using namespace std;

int x[2000], y[2000];
int count_x[1500001], count_y[1500001];

signed main(){
  int n, m;
  vector<int> w, h;
  while(cin >> n >> m, n||m){
    rep(i, n) cin >> y[i];  
    rep(i, m) cin >> x[i];  
    m0(count_x);
    m0(count_y);
    rep(i, n){
      int sum = 0;
      REP(j, i, n){
        sum += y[j];
        count_y[sum]++; // 長さがsumの個数を数える
      }
    }
    
    rep(i, m){
      int sum = 0;
      REP(j, i, m){
        sum += x[j];
        count_x[sum]++;
      }
    }
    
    int ans = 0;
    rep(i, 1500001){
      ans += count_x[i] * count_y[i]; // 同じ長さの個数の積が答えになる.
    }
    
    cout << ans << endl;
  }
}

参考

Square Route 解説
こちらの図がとてもわかり易い.

【AOJ ALDS1_12】C: Graph Ⅱ - Single Source Shortest Path Ⅱ

AOJ プログラミング 競プロ

問題

最短経路 | アルゴリズムとデータ構造 | Aizu Online Judge

方針

  • 隣接行列を用いたダイクストラ法はグラフG=(V, E)において {O(|V|^2)}となる.
  • 今回はノード数が {1 \leq n \leq 10000}であるので, 隣接リストを使った実装を行う.
  • 隣接リストでグラフを表現し, 二分ヒープ(priority_queue)を用いることで飛躍的に高速化することができる.

コード

#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<cmath>
#include<ctime>
#include<cctype>
#include<climits>
#include<iostream>
#include<string>
#include<vector>
#include<map>
#include<list>
#include<queue>
#include<deque>
#include<algorithm>
#include<numeric>
#include<utility>
#include<complex>
#include<memory>
#include<functional>

#define rep(i, n) REP(i, 0, n)
#define REP(i, a, n) for(int i = a ; i < (int)n ; i++)
#define ALL(v) v.begin(), v.end()
#define mp make_pair
#define INF 1e9
#define MAX 10000

using namespace std;

typedef pair<int, int> pii;

int n;
// pair.first : 距離
// pair.second : 頂点
vector<pii> node[MAX];
bool root[MAX];
int d[MAX];

void dijkstra(){
  priority_queue<pii> pq;  
  rep(i, MAX){
    d[i] = INF;
    root[i] = false;
  }
  
  d[0] = 0;
  pq.push(mp(0, 0));

  while(!pq.empty()){
    pii p = pq.top(); pq.pop();
    int u = p.second;
    
    root[u] = true;
    
    if(d[u] < p.first * -1) continue;
    
    rep(i, node[u].size()){
      int v = node[u][i].first;
      if(root[v]) continue;
      if(d[v] > d[u] + node[u][i].second){
    d[v] = d[u] + node[u][i].second;
    pq.push(mp(d[v] * -1, v));
      }
    }
  }
}

signed main(){
  cin >> n;
  int u, k, v, c;
  rep(i, n){
    cin >> u >> k;
    rep(j, k){
      cin >> v >> c;
      node[u].pb(mp(v, c));
    }
  }

  dijkstra();
    
  rep(i, n){
    cout << i << " " << (d[i] == INF?-1:d[i]) << endl;
  }
}