ABC171に参加してみた

初めに

ABC171はAB完でした。うーん中々安定してABC完出来ないですね
今回のC問題は考察不足感が否めないかった。。。どうしたら考察力が付くんだろうか。。。
とゆうことで今回はC問題について書いて行きます。

https://atcoder.jp/contests/abc171

※ブログ内で問題の制約事項をすべて記載はしないので、制約事項は↑のURLより参照願います。

C - One Quadrillion and One Dalmatians

この問題は、1～26がそれぞれa～zに対応しており、入力で与えられた数値を
アルファベットの文字列に変換する問題です。

解説を見てからの回答

#include<bits/stdc++.h>

using namespace std;
using ll = long long;
const long long INF = 1LL<<60;

vector<ll> load[100005];

typedef pair<ll,ll> Pair;

int main(){
 
ll i = 0,j = 0;
 
char answer[16];
 
ll N;
 
cin >> N;

// N--;

  while(N > 0) {

    //各桁の0-INDEX化
    N--;
    // 入力した数値を26で割り、その余りと商をだす
    j = N % 26;
    N = N / 26;
    answer[i] = 'a' + j;
    i++;
  }
 
  i--;
 
  for(j=i; j>=0; j--) {
    cout << answer[j];
  }
  cout << endl;
  
return 0;
 
}

まず、1～26まででがa～zに対応していて27からはaa,ab,ac・・・となるので26を超えると
桁上がりしていることが分かったので、26進数で考えれば問題が解けそうです。

問題では1～26がa～zに対応していますが、26進数で考えやすいように0-INDEXで考え
0～25をa～zにそれぞれ対応させるため、入力されたNから1を引きます。

最初は入力されたNを一度だけ引けば良いと思っていましたが、
27を入力したところ何故か"ba"と表示されてしまいました。。。(あれ？)

イメージ

解説見てもピンと来なかったので、絵を書いた見たところ2桁目も0-INDEXに直す必要があるのに
プログラム上では1桁目しか0-indexを行っていないことに気が付きました。。。(下図青枠)

※とゆーかそもそも桁が上がる際はN/26 > 0であり、桁上がりした値は最低でも1から始まるので
　そりゃずれますよね。(0-INDEXをしない限り0から始まることは無いので)

イメージ

なので、1桁目以降の桁も0-INDEXに直すために桁上がりする場合もNから1を引いた状態で
計算を行い、最後は配列に格納した文字列を逆順で出力する事で答えを求められます。

最後に

うーん、今回は考察不足感が否めないですね。ブログ書くときに絵を描いていると
色々見えてきてくるんですけどね。競技中は頭の中だけで考えてやっているんですが
もっと解けるようになるまでは絵を描きがながらやろうと思います。。。ぐんにょり