日々精進

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

【AOJ ALDS1_5】D: Recursion / Divide and Conquer - The Number of Inversions

AOJ プログラミング

問題

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

方針

  • 反転数を求める問題.
  • バブルソートの要領で探すと {O(n^2)}になってTLEするので効率よく探す必要がある.
  • タイトルの通り, 分割統治法（マージソート）を活用することで {O(n log{n})}でカウントすることができる.
  • 反転数は, 対象データが格納されている配列を二分しLとRを作った時, 配列Rの各要素R[j]について, R[j]よりもあとに移動するようなLの要素は, (Lの要素数)-(Lの現在のインデックス)で求められる.

コード

#include <iostream>

using namespace std;

typedef long long ll;

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

ll n;
ll input[200001];
ll l[100002];
ll r[100002];

ll merge(int left, int right, int mid){
  rep(i, mid - left) l[i] = input[left + i];
  rep(i, right - mid) r[i] = input[mid + i];
  
  // 番兵
  l[mid -left] = r[right - mid] = INF;
  int l_idx, r_idx;
  ll cnt;
  l_idx = r_idx = 0;
  cnt = 0;
  REP(i, left, right){
    if(l[l_idx] <= r[r_idx]){
      input[i] = l[l_idx];
      l_idx++;
    }else{
      input[i] = r[r_idx];
      r_idx++;
      cnt += ((mid - left) - l_idx);
    }
  }
  return cnt;
}

ll mergeSort(int left, int right){
  if(right - left > 1){
    int mid = (right + left)/2;
    ll ret = mergeSort(left, mid);
    ret += mergeSort(mid, right);
    return (ret + merge(left, right, mid));
  }else{
    return 0;
  }
}

signed main(){
  cin.tie(0);
  ios::sync_with_stdio(false);
  
  cin >> n;
  rep(i, n){
    cin >> input[i];
  }

  cout << mergeSort(0, n) << endl;
}

参考

www.slideshare.net

【AOJ 2253】Brave Force Story

AOJ プログラミング

問題

Brave Force Story | Aizu Online Judge

方針

  • BFSをする.
  • その際にそこにたどり着ける距離を保存し, 最後にたどり着けたマスの数を数える.
  • 普通に探索するとインデックスが負になって悲しくなるので, 適当に座標をずらす.

コード

#include <algorithm>
#include <iostream>
#include <queue>
 
using namespace std;
 
#define INF 1<<20
#define rep(i, n) REP(i,0,n)
#define REP(i,a,n) for(int i = a; i < (int)n ; i++)
 
bool barrier[200][200];
int d[200][200];
int dx[] = {0,  0, -1, -1, 1, 1};
int dy[] = {1, -1,  0, -1, 0, 1};
 
struct NODE{
  int x_, y_, d_;
  NODE(int x, int y, int d){
    x_ = x; y_ = y; d_ = d;
  }
};
 
 
int solve(int x, int y, int turn){
  queue<NODE> que;
  que.push(NODE(x, y, 0));
   
  d[x][y] = 0;
 
  while(!que.empty()){
    NODE p = que.front(); que.pop();
     
    if(p.d_ >= turn) continue;
     
    d[p.x_][p.y_] = p.d_;
 
    rep(i, 6){
      int nx = p.x_ + dx[i]; int ny = p.y_ + dy[i];
      if(nx < 0 || 200 <= nx || ny < 0 || 200 <= ny || d[nx][ny] <= p.d_+1 || barrier[nx][ny]) continue;
      d[nx][ny] = p.d_+1;
      que.push(NODE(nx, ny, p.d_+1));
    }
  }
   
  int ans = 0;
  rep(i, 200){
    rep(j, 200){
      if(d[i][j] != INF) ans++;
    }
  }
  queue<NODE>().swap(que); 
  return ans;
}
 
signed main(){
  int t, n;
   
  while(cin >> t >> n, t || n){
    int x, y;
 
    rep(i, 200){
      rep(j, 200){
    barrier[i][j] = false;
    d[i][j] = INF;
      }
    }
 
    rep(i, n){
      cin >> x >> y;
      barrier[x+100][y+100] = true;
    }
     
    cin >> x >> y;
    cout << solve(x+100, y+100, t) << endl;
  }
   
  return 0;
}

【AOJ ALDS1_5】B: Recursion/Divide and Conquer - Merge Sort

AOJ プログラミング

問題

Merge Sort | Aizu Online Judge

方針

コード

#include <iostream>
#include <cstdio>

using namespace std;

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

int n;
int data[MAX_N+1];
int comp;
int l[MAX_N/2+2];
int r[MAX_N/2+2];

void merge(int left, int right, int mid){
  rep(i, mid-left){
    l[i] = data[left + i];
  }

  rep(i, right-mid){
    r[i] = data[mid + i];
  }

  l[mid-left] = r[right-mid] = INF;
  
  int left_idx, right_idx;
  left_idx = right_idx = 0;
  REP(i,left,right){
    comp++;
    if(l[left_idx] <= r[right_idx]){
      data[i] = l[left_idx];
      left_idx++;
    }else{
      data[i] = r[right_idx];
      right_idx++;
    }
  }
}

void mergeSort(int left, int right){
  if(right - left > 1){
    int mid = (right + left)/2;
    mergeSort(left, mid);     // 左
    mergeSort(mid, right);    // 右
    merge(left, right, mid);  // マージ
  }
}

signed main(){
  cin.tie(0);
  ios::sync_with_stdio(false);

  cin >> n;
  rep(i, n){
    cin >> data[i];
  }
  comp = 0;
  
  mergeSort(0, n);

  rep(i, n-1){
    cout << data[i] << " ";
  }
  cout << data[n-1] << endl;
  cout << comp << endl;

}

【AOJ 2330】Earth Invasion Diary of Miyabi-sensei

AOJ プログラミング

問題

Earth Invasion Diary of Miyabi-sensei | Aizu Online Judge

方針

  • 天秤に乗せるものをA, B, Cという3つに分け, AとBを天秤に載せたとき, 釣り合っているならばCにオリジナルが載っているし, どちらかに傾いたら傾いたグループにオリジナルが存在することがわかる.
  • {N \leq 3^k}が成り立つときの {k}が答えとなるので, k = log_3{N}とし最後にceilで切り上げれば良い.

コード

#include <iostream>
#include <cmath>
 
using namespace std;
 
int main(){
  long long n;
  cin >> n;
  cout << ceil(log(n)/log(3)) << endl;
}

【AOJ ALDS1_4】D: Allocation

AOJ プログラミング

問題

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

方針

  • 積載量 {P}の最小値を求めたい.
  • 0から順に {P}を試し, そのPでk台のトラックを使いすべて積むことができたならそれが答えになる.
  • しかし, 順番に調べていくと {O(Pn)}のアルゴリズムになって終わらなさそう.
  • 二分探索を使うと {O(n logP)}となる.

コード

#include <iostream>

using namespace std;

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

typedef long long ll;

int n, k;
int w[100001];

bool check(int p){
  ll sum=0;
  int idx = 0;

  rep(i, k){
    sum = 0;
    while(w[idx] + sum <= p){
      sum+=w[idx];
      idx++;
      if(idx == n) return true;
    }
  }
  return false;
}

signed main(){
  cin >> n >> k;

  rep(i, n) cin >> w[i];
  
  // binary search
  ll left = 0, right = 100000 * 10000;
  while(right - left > 1){
    ll mid = (left + right) / 2;
    if(check(mid)) right = mid;
    else left = mid;
  }
  
  cout << right << endl;
}

【AOJ ALDS1_4】C: Dictionary

AOJ プログラミング

問題

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

方針

  • mapを実装する問題
  • STLのmap使えば簡単にできるんだけども, 「プログラミングコンテスト攻略のためのアルゴリズムとデータ構造」を見つつ愚直に実装.
  • ハッシュ関数は「ダブルハッシュをつかったオープンアドレス法」を利用した. オープンアドレス法は最初のハッシュ値の場所が埋まっていたら別のところを見つけて入れようねと言った感じ.
  • オープンアドレス法の探索方法としては, ダブルハッシュの他にも線形探索したり平方探索ってのがあるみたい.

    コード

#include <iostream>

using namespace std;

#define M 1046527
#define h1(key) (key%M)
#define h2(key) (1+(key%(M-1)))
string s[M];

int getCode(char c){
  switch(c){
  case 'A':
    return 1;
    break;
  case 'C':
    return 2;
    break;
  case 'G':
    return 3;
    break;
  }
  return 4;
}

long long getKey(string in){
  long long sum = 0, p = 1;
  for(int i = 0 ; i < (int)in.size() ; i++){
    sum += (getCode(in[i]) * p);
    p *= 5;
  }
  return sum;
}

long long hash_f(long long key, int i){
  return (h1(key) + i * h2(key)) % M;
}

bool find(string in){
  long long key = getKey(in);
  
  for(int i=1;;i++){
    long long h = hash_f(key, i);
    if(s[h] == in) return true;
    else if(s[h].size() == 0) return false;
  }
}

void insert(string in){
  long long key = getKey(in);
  int i;
  for(i=1;;i++){
    long long h = hash_f(key, i); 
    if(s[h].size() == 0){
      s[h] = in;
      break;
    }
  }
}

int main(){
  int n;
  string command, in;
  cin >> n;
  for(int i = 0 ; i < n ; i++){
    cin >> command >> in;
    if(command == "insert"){
      insert(in);
    }else{
      if(find(in)){
    cout << "yes" << endl;
      }else{
    cout << "no" << endl;
      }
    }
  }
    
}

参考

http://yamweb.comp.ae.keio.ac.jp/japanese/2011-A論/5-before-20111028.pdf

【AOJ 2198】Moonlight Farm

AOJ

問題

Moonlight Farm | Aizu Online Judge

方針

  • 入力が色々あるので1度図に起こして考えてみると非常に簡単
  • 収入効率の分母は {A_i + B_i + C_i + (D_i + E_i) \times M_i}, 分子は {S_i \times F_i \times M_i - P_i}となるのでこれをクラスにいれてソートをするだけ.
  • 効率が同じ場合は名前を辞書順で表示する.

ソース

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

using namespace std;

class Log{
public:
  string name;
  double efficiency;
    
  Log(string name, double numerator, double denominator){
    this->name = name;
    efficiency = numerator/denominator;
  }

  bool operator < (const Log& another) const{
    if(efficiency == another.efficiency){
      return name < another.name;
    }
    return (efficiency > another.efficiency);
  }

};

signed main(){
  int n;
  
  while(cin >> n, n){
    vector<Log> v;  
    for(int i = 0 ; i < n ; i++){
      double p, a, b, c, d, e, f, s, m;
      string l;
      cin >> l >> p >> a >> b >> c >> d >> e >> f >> s >> m;
      v.push_back(Log(l, s*f*m-p, a+b+c+(d + e)*m));
    }

    sort(v.begin(), v.end());

    for(int i = 0 ; i < n ; i++){
      cout << v[i].name << endl;
    }
    cout << "#" << endl;
  }
  
}