日々精進

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

【AOJ ALDS1_6】A: Counting Sort

AOJ プログラミング

問題

Counting Sort | Aizu Online Judge

方針

  • 計数ソート（バケットソート）をしよう.
  • アルゴリズムは問題をそのまま実装.

コード

#include<bits/stdc++.h>

#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 a[2000001];
int b[2000001];  
int c[2000001];

signed main(){
  int n;
  cin >> n;
  
  memset(c, 0, sizeof(c));

  rep(i,n){
    cin >> a[i+1];
    c[a[i+1]]++;
  }

  REP(i, 1, 2000001){
    c[i] += c[i-1];
  }
  
  REP(i,1,n+1){
    b[c[a[i]]] = a[i];
    c[a[i]]--;
  }

  cout << b[1];
  REP(i,2,n+1){
    cout << " " << b[i];
  }
  cout << "\n";
}

【AOJ 1285】Grey Area

AOJ プログラミング

問題

Grey Area | Aizu Online Judge

方針

  • ヒストグラムを印刷するために必要なインク量を求めようという問題.
  • vを入力する際に, 区画の最大値(imax), 頻度の最大値(hmax)を求める.
  • hist[i] := {i \leq v \leq (i+1)w}の頻度としたとき, {\sum _{i=0}^{imax} \frac{hist[i]}{hmax} \times \frac{imax-i} {imax}} を計算する.
  • 最後に0.01を足す(線とかを引くためのコストっぽい？)

コード

#include <bits/stdc++.h>

using namespace std;

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

signed main(){
  int n, w;
  int hist[50];
  int v;
  
  while(cin >> n >> w, n||w){
    int i_max = -1;
    int h_max = -1;
    memset(hist, 0, sizeof(hist));

    REP(i, 0, n){
      cin >> v;
      int idx = (int)(v/w);
      hist[idx]++;
      i_max = max(i_max, idx);
      h_max = max(h_max, hist[idx]);
    }
    
    double ans = 0.0;
    REP(i, 0, i_max+1){
      ans += ((double)hist[i]/h_max)*(double)(i_max-i)/(i_max);
    }
    
    ans += 0.01;
    cout << ans << endl;
  }
}

AtCoder Beginner Contest #59

プログラミング AtCoder

問題A：Three-letter acronym

3つ文字列が与えられるので, それぞれの1文字目を大文字にしてつなげ表示する. 文字コードでやった.

#include <iostream>
#include <cstring>

using namespace std;

int main(){
  string s1, s2, s3;
  
  cin >> s1 >> s2 >> s3;
  cout << (char)('A'+s1[0]-'a') << (char)('A'+s2[0]-'a') << (char)('A'+s3[0]-'a') << endl;
}

問題B：Comparison

与えられる数字が {1 \leq A, B \leq 10^{100}}であるので, 文字列として受け取る. 文字列の長さで比較し, 同じ長さの場合は左から順に大きいか小さいか見ていく.

#include <iostream>
#include <cstdlib>

using namespace std;

int main(){
  string A, B;
  bool flag = true;
  cin >> A >> B;
  
  if(A.size() > B.size()){
    cout << "GREATER" << endl;
  }else if(A.size() < B.size()){
    cout << "LESS" << endl;
  }else{
    for(int i = 0 ; i <(int)A.size() ; i++){
      if((A[i]-'0') > (B[i]-'0')){
    cout << "GREATER" << endl;
    flag = false;
    break;
      }else if((A[i]-'0') < (B[i] - '0')){
    cout << "LESS" << endl;
    flag = false;
    break;
      }
    }
    if(flag) cout << "EQUAL" << endl;
  }
}

問題C：Sequence

偶数番目が正, 奇数番目が正の2通りを考え, それらの小さい方を取る. ある桁が期待した符号と異なる場合, ほしい符号の絶対値最小まで変更する(1 or -1)

#include <iostream>
#include <cmath>

using namespace std;

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

signed main(){
  long long a[100001];
  long long n;

  cin >> n;
  rep(i,n){
    cin >> a[i];
  }
  
  long long c1 = 0, c2 = 0;
  long long sum = 0;
  long long c = 1;

  // 奇数番目を正
  REP(i,0,n){
    sum += a[i];
    if(sum * c <= 0){
      c1 += (abs(sum)+1);
      sum = c;
    }
    c*=(-1);
  }
  
  // 偶数番目が正
  c = -1;
  sum = 0;
  REP(i,0,n){
    sum += a[i];
    if(sum * c <= 0){
      c2 += abs(sum)+1;
      sum = c;
    }
    c*=(-1);
  }

  cout << min(c1, c2) << endl;
}

問題D：Alice&Brown

#include <iostream>
#include <cmath>

using namespace std;

int main(){
  long long x, y;
  cin >> x >> y;
  if(abs(x-y) <= 1) cout << "Brown" << endl;
  else cout << "Alice" << endl;
}

【AOJ 1257】And Then There Was One

AOJ プログラミング

問題

And Then There Was One | Aizu Online Judge

方針

  • Josephus problemという有名な問題らしい.
  • {f(n, k) = (f(n-1, k)+k) \bmod n } (ただし, {f(1, k) = 0 }) という漸化式を解くことで {O(n)}で求まる.

コード

#include <iostream>

using namespace std;

int f(int n, int k){
  if(n == 1) return 0;
  return (f(n-1, k)+k)%n;
}
signed main(){
  int n, k, m;
  while(cin >> n >> k >> m, n || k || m){
    cout << (f(n-1,k)+m)%n+1 << endl;
  }
}

【AOJ 2242】Era Name

AOJ プログラミング

問題

Era Name | Aizu Online Judge

方針

  • EraBasedYearとWesternYearが入力し, それらをs(start), e(end)という変数に代入.
  • queryが (EraBasedYear_i - WesternYear_i, WesternYear_i ]にはいってるとき, {EraName_i}が答え.
  • 当てはまらない時はUnknownとなる.

コード

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

using namespace std;

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

struct YEAR{
  string _en;
  int s, e;

  YEAR(string en, int eby, int wy){
    _en = en;
    s = wy - eby;
    e = wy;
  }

  bool operator < (const YEAR& another) const {
    return s < another.s;
  }
};

vector<YEAR> v;

string getEraBasedYear(int query){
  rep(i, v.size()){
    if(v[i].s < query && query <= v[i].e){
      return (v[i]._en + " " + to_string(query-v[i].s));
    }
  }
  return "Unknown";
}

signed main(){
  int n, q, eby, wy, query;
  string en;

  while(cin >> n >> q, n||q){
    v.clear();
    rep(i,n){
      cin >> en >> eby >> wy;
      v.push_back(YEAR(en, eby, wy));
    }
    
    sort(v.begin(), v.end());

    rep(i,q){
      cin >> query;
      cout << getEraBasedYear(query) << endl;
    }
  }
}

残ってるAOJ−ICPCの200問題が全部英語なのでつらい. 誤読祭り.

【ALDS1_10】B: Dynamic Programming - Matrix Chain Multiplication

AOJ プログラミング

問題

連鎖行列積 | アルゴリズムとデータ構造 | Aizu Online Judge

方針

行列が5個与えられた時, 計算の順序は

1. {((((M_1 M_2) M_3) M_4) M_5)}
2. {(M_1 (M_2 (M_3 (M_4 M_5))))}
3. {( ( M_1 M_2 ) ( ( M_3 M_4)M_5))}

など様々な順序がある. すべてのパターンを試すアルゴリズムでは, {O(n!)}となってしまうため, これよりも計算効率の良いアルゴリズムを考える必要がある. 結果からいうと, この問題は動的計画法を用いることで効率よく計算することができる.
　まずはじめに, 2つの行列の演算について考える. M_{i-1}M{i} の演算方法は1通りであり, 行列 {M_i} の行と列をそれぞれ p\_{i-1}, p\_iとしたとき, 演算回数は p_{i-1} \times p_i \times p_{i+1}回となる. これらの結果はdpテーブルにメモしておく.
　次に, (M_{0}M_{1}M_{2}), (M_{1}M_{2}M_{3}), (M_{2}M_{3}M_{4}) \cdots (M_{n-2}M_{n-1}M_{n}) の計算を考える. (M_{0}M_{1}M_{2})の計算では, ( (M_{0}M_{1})M_{2})と (M_{0}(M_{1}M_{2}) )の二通りが存在し, それらの小さいほうが最適解となる. このとき, (M\_{0}M\_{1})や (M\_{1}M\_{2})は事前に計算済みであることから, 改めて計算する必要はない.
　以上より, 以下のような式を実装することで最適解を得ることができる.

{\begin{equation} m[i][j] = \begin{cases} 0 & \text{(if i = j)} \\\min_{i \leq k \leq j} \{m[i][k] + m[k+1][j] + p[i-1] \times p[k] \times p[j] \} & \text{(if i < j)} \end{cases} \end{equation}}


コード 

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

#define N 101

int dp[N+1][N+1], p[N+1];

int main(){
  int n;
    
  cin >> n;
  REP(i, 1, n+1){
    cin >> p[i-1] >> p[i];
  }
    
  REP(l, 2, n+1){           // 対象とする行列の数
    REP(i, 1, n-l+2){     
      int j = i + l - 1;   
      dp[i][j] = (1 << 20); // dp[i][j] := [Mi, Mj]の最小回数
      REP(k, i, j){
	dp[i][j] = min(dp[i][j], dp[i][k] + dp[k+1][j] + p[i-1] * p[k] * p[j]);
      }
    }
  }

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

  return 0;
}

【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