日々精進

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

【AOJ 1610】Bamboo Blossoms

AOJ プログラミング

問題

Bamboo Blossoms | Aizu Online Judge

方針

  • エラトステネスの篩的に消していく.
  • Nが0になったときのiが答え.

コード

#include <iostream>
#include <cmath>

using namespace std;

#define MAX 7368791

int main(){
  int m, n;
  bool flag[MAX];

  while(cin >> m >> n, m||n){
    for(int i = 0 ; i <= MAX ; i++) flag[i] = false;
    for(int i = m ;; i++){
      if(!flag[i]){
    if(n == 0){
      cout << i << endl;
      break;
    }else{
      n--;
      for(int j = i ; j <= MAX ; j+=i){
        flag[j] = true;
      }
    }
      }
    }
  }
}

参考

審判長による国内予選講評（確定版） | ACM-ICPC 2016 Asia Tsukuba Regional

【AOJ 2700】Airport Codes

AOJ プログラミング

問題

Airport Codes | Aizu Online Judge

方針

  • 1文字目と母音の直後の文字を順に連結した文字列を作る.
  • k文字未満ならその文字列, k文字以上なら取り出した文字列の先頭からk文字分をコードとする.
  • kを1から50まですべて試す(試しても間に合う制約なので)

コード

#include <iostream>
#include <vector>
#include <map>

using namespace std;

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

string name[101];

bool isvowel(char c){
  return (c == 'a' || c == 'i' || c == 'u' || c == 'e' || c == 'o');
}

string getCode(string s, int k){
  string ans;
  ans = s[0];
  int len = s.size() - 1;
  REP(i, 0, len){
    if(isvowel(s[i])){
      ans += s[i+1];
    }
  }
  if((int)ans.size() < k) return ans;
  
  return ans.substr(0, k);
}

int check(int n){
  bool flag;
  
  REP(k, 1, 51){
    flag = true;
    map<string, bool> mp;
    rep(i, n){
      string s = getCode(name[i], k);
      if(mp.count(s) == 0){
        mp[s] = true;
      }else{
        flag = false;
        break;
      }
    }
    if(flag) return k;
  }
  return -1;
}

int main(){
  int n;

  while(cin >> n, n){
    rep(i, n){
      cin >> name[i];
    }
    int ret = check(n);
    cout << ret << endl;
  }
}

【AOJ 2706】Let's Solve Geometric Problems

AOJ プログラミング

問題

Let's Solve Geometric Problems | Aizu Online Judge

方針

  • b進数k桁の値は以下のように表すことができる.
    {0.d_1 d_2 d_3 \cdots d_k= d_1 \times b^{-1} + d_2 \times b^{-2} + d_3 \times b^{-3} \cdots d_k \times b^{-k}}
  • 上の式を変換すると, {\frac{d_1 b^{k-1}+d_2 b^{k-2} \cdots d_k}{b^k}}となることがわかる.
  • 上記の式の形に変換したときのbが答え.

コード

#include <iostream>
#include <cmath>
#include <utility>
#include <vector>
#include <algorithm>
 
using namespace std;
 
typedef pair<int, int> pii;
 
signed main(){
  int p, q;
  int k;
  cin >> p >> q;
  k = __gcd(p, q);
  p /= k;
  q /= k;
   
  int q_ = q;
  vector<pii> ans;
  for(int i = 2 ; i <= sqrt(q) ; i++){
    if(q_%i == 0){
      pii p = make_pair(i, 1);
      q_ /= i;
      while(q_%i == 0){
        p.second++;
        q_ /= i;
      }
      ans.push_back(p);
    }
  }
 
  if(q_ > 1) ans.push_back(pii(q_, 1));
   
  int a = 1;
  for(int i = 0 ; i <(int) ans.size() ; i++){
    a *= ans[i].first;
  }
 
  cout << a << endl;
}

【AOJ ALDS1_7】B: Tree - Binary Trees

AOJ プログラミング

問題

Binary Trees | Aizu Online Judge

方針

  • 二分木を作ろう.

コード

#include <iostream>

using namespace std;

struct Node{
  int parent, left, right;
};

int n;
Node T[30];
int D[30], H[30];

void depth(int u, int d){
  if(u == -1) return;
  D[u] = d;
  depth(T[u].left, d+1);
  depth(T[u].right, d+1);
}

int height(int u){
  int ret1 = 0, ret2 = 0;
  if(T[u].left != -1) ret1 = height(T[u].left) + 1;
  if(T[u].right != -1) ret2 = height(T[u].right) + 1;
  return (H[u] = max(ret1, ret2));
}

signed main(){
  cin >> n;
  int u, l, r;

  for(int i = 0 ; i < 30 ; i++){
    T[i].parent = T[i].left = T[i].right = -1;
  }

  for(int i = 0 ; i < n ; i++){
    cin >> u >> l >> r;
    T[u].left = l;
    T[u].right = r;
    if(l != -1) T[l].parent = u;
    if(r != -1) T[r].parent = u;
  }

  int root;
  for(int i = 0 ; i < n ; i++){
    if(T[i].parent == -1) root = i;
  }
  
  depth(root, 0);
  height(root);
  
  for(int i = 0 ; i < n ; i++){
    cout << "node " << i << ": ";
    cout << "parent = " << T[i].parent << ", ";
    cout << "sibling = ";
    if(T[i].parent == -1){
      cout << -1 << ", ";
    }else if(T[T[i].parent].left != -1 && T[T[i].parent].left != i){
      cout << T[T[i].parent].left << ", ";
    }else if(T[T[i].parent].right != -1 && T[T[i].parent].right != i){
      cout << T[T[i].parent].right << ", ";
    }else{
      cout << -1 << ", ";
    }
    cout << "degree = " << (T[i].left!=-1?1:0)+(T[i].right!=-1?1:0) << ", ";
    cout << "depth = " << D[i] << ", ";
    cout << "height = " << H[i] << ", ";
    if(root == i) cout << "root" << endl;
    else if(T[i].left != -1 || T[i].right != -1) cout << "internal node" << endl;
    else cout << "leaf" << endl;
  }

}

【AOJ 2331】A Way to Invite Friends

AOJ プログラミング

問題

A Way to Invite Friends | Aizu Online Judge

方針1

  • 配列の[a, b]を++していく. 配列fをf[i]:=i人誘う時行くことができる友達の数とする.
  • i-1（自分を抜いた数）誘うときに, i - 1 <= f[i]となればi-1人誘えるということになる.

方針2

  • aのときにf[a]を1増やし, ｂのときf[b]を1減らす.
  • iを2から増やしつつ配列の値の総和を出し, i以上になったとき誘える人数.

コード（方針1）

#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++)

int f[100005];

signed main(){
  int n;
  int a, b;
  cin >> n;
  rep(i, n){
    cin >> a >> b;

    REP(j,a,(b+1)){
      f[j]++;
    }
  }

  int idx = 0;
  REP(i, 2, 100002){
    if(i-1 <= f[i]){
      idx = i-1;
    }
  }
  
  cout << idx << endl;
}

コード（方針2）

#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++)

int f[100005];

signed main(){
  int n;
  int a, b;
  cin >> n;
  rep(i, n){
    cin >> a >> b;
    f[a]++;
    f[b + 1]--;
  }
  
  int sum = 1;
  int idx = 0;
  rep(i, 100002){   // i人誘う
    sum += f[i];
    if(i <= sum){   // n人中sum人が行くことができる. i<=sumを満たしてればよい
      idx = i;
    }
  }
  
  idx--;
  cout << idx << endl;
}

2の方, なんかimosっぽいなぁと思いました. コミュ力を上げて友達を増やそう.

【AOJ 1193】Chain Disappearance Puzzle

AOJ プログラミング

問題

連鎖消滅パズル | Aizu Online Judge

方針

  1. 横に3つ以上連鎖している箇所は消すことができる.
  2. 消えた部分には, 上にある石が空きを埋めるように落ちてくる.
  3. すべての石を落とした後に消滅の条件をみたすようなものがあればまた繰り返す.
    上の通りにシミュレーションする.

コード

#include <iostream>
#include <algorithm>

using namespace std;

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

int h;
int field[20][10];

signed main(){

  while(cin >> h, h){
    rep(i, h){
      rep(j, 5){
        cin >> field[i][j];
      }
    }
 
    int ans = 0;
    bool flag = true;
    while(flag){
      int tmp = 0;

      rep(i, h){
        int prev = -1;
        int count = 0;
        int start = 0;

        REP(j, 0, 5){
          if(prev == field[i][j] && field[i][j] > 0){
            count++;
        
            if(count >= 3 && field[i][j+1]!=field[i][j]){
              REP(k, 0, count){
                tmp += field[i][start+k];
                field[i][start+k] = -1;
              }
              count = 1;
            }
          }else{
            if(count >= 3){
              REP(k, 0, count){
                tmp += field[i][start+k];
                field[i][start+k] = -1;
              }
            }
            start = j;
            count = 1;
            prev = field[i][j];
          }
        }
      }

      if(tmp == 0){
        cout << ans << endl;
        flag = false;
        continue;
      }
      
      ans += tmp;
      
      REP(k, 1, h){
        rep(l, 5){
          if(field[k][l] == -1 && field[k-1][l]){
            for(int m = k ; m > 0 ; m--){
              swap(field[m][l], field[m-1][l]);
            }
          }
        }
      }      
    } 
  }

}

【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