Codeforces Round 158 (Div 2) Problem A - Adding Digits

Codeforces

問題概要

ある数字aに、一ケタの数字を末尾に自由に付け足していく処理をn回行う。
ただし、毎回bで割り切れるようにケタを追加していかなければならない。
n回ケタを追加した後の値を出力せよ。
もし、このような数が作れない場合は、-1を出力せよ。

解法

1ケタ目の追加では、bで割り切れるように付け加える。
この時点でbで割り切れる数字になっているので、残りのn-1回は、0を付け加えるだけで良い。

プログラム

#include <iostream>
using namespace std;

int main(){
  int a, b, n;

  while(cin >> a >> b >> n){
    int added = -1;

    for(int i = 0; i < 10; i++){
      int na = a * 10 + i;

      if(na % b == 0){
        added = i;
        break;
      }
    }

    if(added == -1){
      cout << -1 << endl;
      continue;
    }

    cout << a << added;

    for(int i = 0; i < n - 1; i++){
      cout << "0";
    }
    cout << endl;
  }
}

PKU 2823 - Sliding Window

PKU

問題概要

N個の要素をもつ数列が与えられる。
この数列において、K個の要素をもつ区間それぞれについて、最小値・最大値を求めよ。

解法

セグメントツリーを使って、区間の最小値・最大値をO(log n)で求めてしまいましょう。
セグメントツリーは、プログラミングコンテストチャレンジブックを参照してください。

プログラム

セグメントツリーのコードは、アリ本からの転載です。

#include <iostream>
#include <cstdio>
#include <climits>
using namespace std;

typedef pair<int,int> P; //first : min, second : max

const int MAX_N = 1 << 20;

int n;
int datMin[2 * MAX_N - 1];
int datMax[2 * MAX_N - 1];

P ans[MAX_N];

void init(int n_){
  n = 1;
  while(n < n_) n *= 2;
  for(int i = 0; i < 2 * n - 1; i++){
    datMin[i] = INT_MAX;
    datMax[i] = INT_MIN;
  }
}
 
void update(int k, int a){
  k += n - 1;
  datMax[k] = datMin[k] = a;
  while(k > 0){
    k = (k - 1) / 2;
    datMin[k] = min(datMin[k * 2 + 1], datMin[k * 2 + 2]);
    datMax[k] = max(datMax[k * 2 + 1], datMax[k * 2 + 2]);
  }
}

P query(int a, int b, int k, int l, int r){
  if(r <= a || b <= l) return P(INT_MAX, INT_MIN);
  if(a <= l && r <= b) return P(datMin[k], datMax[k]);
  else{
    P vl = query(a, b, k * 2 + 1, l, (l + r) / 2);
    P vr = query(a, b, k * 2 + 2, (l + r) / 2, r);
    return P(min(vl.first, vr.first), max(vl.second, vr.second));
  }
}

int main(){
  int N, K;

  while(cin >> N >> K){
    init(N);

    for(int i = 0; i < N; i++){
      int x;
      scanf("%d", &x);
      update(i, x);
    }

    for(int i = 0; i + K <= N; i++){
      ans[i] = query(i, i + K, 0, 0, n);
    }

    for(int i = 0; i + K <= N; i++){
      if(i != 0) cout << " ";
      cout << ans[i].first;
    }
    cout << endl;

    for(int i = 0; i + K <= N; i++){
      if(i != 0) cout << " ";
      cout << ans[i].second;
    }
    cout << endl;
  }
}

PKU 1731 - Orders

PKU

問題概要

文字列が入力される。
この文字列の順列全てを辞書順で出力せよ。

解法

next_permutationやるだけで解けました。

プログラム

#include <iostream>
#include <algorithm>
#include <cstdio>
using namespace std;

int n;
char s[1002];

int main(){
  while(scanf("%s", s) != EOF){
    n = strlen(s);
    sort(s, s + n);

    do{
      puts(s);
    }while(next_permutation(s, s + n));
  }
}

PKU 3761 - Bubble Sort

PKU

問題概要

n, kが入力される。
n個の要素がある数列をバブルソートでソートされることを考える。
このとき、数列が並び終わるまでに、バブルソートの一重ループ目を実行した回数がkであるとする。
このようになる数列の初期配置は、何パターンあるか求めよ。

解法

ごめんなさい。
法則性ありそうだったけど、自力で導きだせなかったので、OEIS突っ込みました。
http://oeis.org/A056151

階上は、先に計算しておく。
累乗は、繰り返し二乗法で。
入力は、scanfで。

プログラム

/*
0回でソートできるのならば、各数字はソートされた状態でなければならない。
1 2 3 4

1回でソートできるのならば、各数字は「本来あるべき位置の1つ右」以下に位置すればおk。
さらに、最低でも1つの数字が本来あるべき位置でない位置になければならない。

2 1 3 4 <- 1は、本来あるべき位置より1つ右に位置するのでOK
4 1 2 3 <- 4は、本来あるべき位置より左側に位置するのでOK
2 3 1 4 <- 1は、本来あるべき位置より2つ右に位置しているのでNG
1 2 3 4 <- ソートされちゃってるのでNG

2回でソートできるのであれば、各数字は「本来あるべき位置の2つ右」以下に位置すればOK。
さらに、最低１つの要素は、本来あるべき位置より2つ右の位置になければならない。

2 3 1 <- 1は、本来あるべき位置より2つ右にあるからOK
3 2 1 <- 1は、本来あるべき位置より2つ右にあるからOK
1 2 3 <- sortされちゃってるからNG
3 1 2 <- 条件満たしてないのでNG
 */
#include <iostream>
#include <vector>
#include <cstdio>
using namespace std;

typedef long long ll;

#define MOD 20100713LL

ll fact[1000002];

ll modPow(ll x, ll n){
  if(n == 0) return 1LL;
  ll res = modPow(x * x % MOD, n / 2LL);
  if(n & 1LL) res = res * x % MOD;
  return res;
}

int main(){
  fact[0] = fact[1] = 1;
  for(ll i = 2; i <= 1000000; i++){
    fact[i] = fact[i - 1] * i;
    fact[i] %= MOD;
  }

  int T;
  ll n, k;

  scanf("%d", &T);

  while(T--){
    scanf("%lld%lld", &n, &k);

    ll cal = fact[k] * modPow(k + 1, n - k) % MOD;
    cal -= (fact[k - 1] * modPow(k, n - k + 1)) % MOD;
    cal = (cal + MOD) % MOD;

    printf("%lld\n", cal);
  }
}

PKU 3705 - Reverse

PKU

問題概要

nが入力される。
1, 2, ..., nの昇順数列をn, n-1, ..., 1の降順数列にするための最小の操作数と、操作方法を出力せよ。
数列に対する１回の操作では、次のことをできる。

  • (pos1, length, pos2)
    • まず、数列のpos1番目からlength個を取り出す。
    • 次に、取り出した後の数列のpos2番目の要素の直後に、先ほど取り出したlength個の要素を挿入する。

解法

  • n=1の場合
    • 0回ですね
  • n=2の場合
    • 1回ですね

n>=3の場合、必ずn/2+1回で降順にできます。具体例を見ていただければ、わかりやすいです。

  • n=5（奇数）の場合
    • 1 2 3 4 5 -> 3 4 1 2 5
    • 3 4 1 2 5 -> 3 2 5 4 1
    • 3 2 5 4 1 -> 5 4 3 2 1
  • n=6（偶数）の場合
    • 1 2 3 4 5 6 -> 3 4 1 2 5 6
    • 3 4 1 2 5 6 -> 3 2 5 4 1 6
    • 3 2 5 4 1 6 -> 3 2 1 6 5 4
    • 3 2 1 6 5 4 -> 6 5 4 3 2 1

つまり、n/2以下の要素の降順を左側に寄せて、n/2より大きい要素の降順を右側に寄せるように操作しています。そして、最後に右半分を一番左に挿入してやればいいわけです。

プログラム

#include <iostream>
using namespace std;

int main(){
  int n;

  while(cin >> n){
    if(n == 1){
      cout << 0 << endl;
      continue;
    }
    if(n == 2){
      cout << "1" << endl;
      cout << "1 1 1" << endl;
      continue;
    }

    cout << n / 2 + 1 << endl;

    for(int i = 1; i <= n / 2; i++){
      cout <<  (n - 1) / 2 + i << " " << 2 << " " << i - 1 << endl;
    }
    cout << n / 2 + 1 << " " << n / 2 << " " << 0 << endl;
  }
}

ACM/ICPC 2011 Asia Regional - Daejeon

Problem C - Color Length

問題概要

N台の車の列とM台の車の列が与えられます。
これらの車は、'A'〜'Z'の色のどれかで塗られています。
N台の車の列とM台の車の列を順番を変えずに、マージした列Sを作ります。
文字列Sにおいて、以下の方法によって求めたコストの最小値を求めてください。

＜コストの計算法＞

  • 文字列Sにおいて、「文字Cが存在する末尾index - 文字Cが存在する先頭index」を求める
  • これを全ての文字の種類について求め、それらを合計した値がコスト
方針

動的計画法で考えます。

 dp[i][j] =
   1つ目の列のi文字目、
   2つ目の列のj文字目まで使ったときの、
   最小コスト
プログラム
int n, m;
string a, b;

int dp[5002][5002];
int alpha[128];
int aCnt[5002][128], bCnt[5002][128];

//文字列sの各アルファベットの数の累積和を求める
//t[i][j] = sのi文字目までで、jの文字がいくつあったか
//alpha[i] = iの文字が、2つの文字列を合わせていくつあったか
void countAlpha(const string &s, int t[5002][128]){
  int len = s.length();

  for(int i = 0; i < len; i++){
    alpha[s[i]]++;

    for(int j = 'A'; j <= 'Z'; j++){
      if(s[i] == j){
        t[i + 1][j]++;
      }
      t[i + 1][j] += t[i][j];
    }
  }
}

int getCost(int i, int j, char ch){
  int res = 0;

  //chが先頭文字列であるとき
  if(aCnt[i][ch] + bCnt[j][ch] == 1){
    res -= i + j;
  }
  //chが末尾文字列であるとき
  if(aCnt[i][ch] + bCnt[j][ch] == alpha[ch]){
    res += i + j;
  }

  return res;
}

void solve(){
  for(int i = 0; i <= n; i++){
    for(int j = 0; j <= m; j++){
      dp[i][j] = INT_MAX;
    }
  }

  dp[0][0] = 0;

  for(int i = 0; i <= n; i++){
    for(int j = 0; j <= m; j++){
      if(dp[i][j] == INT_MAX) continue;

      //1つ目の文字列を1文字進められる
      if(i + 1 <= n){
        dp[i + 1][j] = min(dp[i + 1][j], dp[i][j] + getCost(i + 1, j, a[i]));
      }
      //2つ目の文字列を1文字進められる
      if(j + 1 <= m){
        dp[i][j + 1] = min(dp[i][j + 1], dp[i][j] + getCost(i, j + 1, b[j]));
      }
    }
  }

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

int main(){
  int T;
  cin >> T;

  while(T--){
    cin >> a >> b;
    n = a.length();
    m = b.length();

    memset(alpha, 0, sizeof(alpha));
    memset(aCnt, 0, sizeof(aCnt));
    memset(bCnt, 0, sizeof(bCnt));
    countAlpha(a, aCnt);
    countAlpha(b, bCnt);

    solve();
  }
}

会津合宿2012-Day1でコンテストを開催します！

会津合宿の1日目に、AOJでコンテストを開きます。
レベルはそんなに高くないと思うので、気軽にご参加ください。
みなさんの参加お待ちしてます！


日時2012年9月3日(月) 14:00-17:00
コンテスト時間3時間
問題数7問程度
難易度ACM/ICPC国内予選A〜Eレベルを想定
チームチーム参加、個人参加、どちらでも結構です
問題ページ/ジャッジAizu Online Judge
作問者
立命館大学のアジア地区進出チームとその関係者

  • THE 2DM@STER (@Respect2D, @slip0110, @_shnyh)
  • @kioa341, @utisam