KUPC2017 C - Best Password

解説

できるだけ一文字目の方に大きい文字(z,y,x,...,a)を作っていく。繰り上げしていくイメージ。

Aⁱ C[S_i] + Aⁱ⁺¹ C[S_(i+1)] => Aⁱ (C[S_i] + A) + Aⁱ⁺¹ * (C[S_(i+1)] - 1)。

N文字目から繰り上げできるだけしていく。

コード

#include <algorithm>
#include <cstdio>
#include <iostream>
#include <map>
#include <cmath>
#include <queue>
#include <set>
#include <sstream>
#include <stack>
#include <string>
#include <vector>
#include <stdlib.h>
#include <stdio.h>
#include <bitset>
#include <cstring>
#include <deque>
using namespace std;
#define FOR(I,A,B) for(int I = (A); I < (B); ++I)
#define CLR(mat) memset(mat, 0, sizeof(mat))
typedef long long ll;
int main()
{
  ios::sync_with_stdio(false);
  cin.tie(0);
  int A; cin >> A;
  string s; cin >> s;
  int N = s.length();
  int C[N];
  FOR(i,0,N) C[i] = s[i] - 'a' + 1;
  FOR(i,0,N) {
    for(int j = N - 1; j > 0; j--) {
      // j -> j - 1にできるだけ繰り上げする
      while(C[j-1] + A <= 26 && C[j] > 0) {
        C[j-1] += A;
        C[j]--;
      }
    }
  }
  FOR(i,0,N) {
    if(C[i] == 0) break;
    cout << char(C[i]-1+'a');
  }
  cout << endl;
  return 0;
}