AtCoder Beginner Contest 099 解説備忘録

前書き

AtCoder Beginner Contest 099 を解いてみた．解けなかった問題の備忘録．

C問題

[問題はこちら]

・Nのうち，いくらかが$6^p$($p$：非負整数)の和で表され，残りが$9^p$($p$：非負整数)の和で表される．

(例) N=127場合，
例えば，いくらか $i=80$ は $6^2 \times 2 + 6^1 \times 1 +6^0 \times 2$で表される．これは $6^p$ を $2+1+2=5$回使っている．
一方，残りの $m=N-i=47$ は $9^1 \times 5 + 9^0 \times 2 $で表される．これは $9^p$ を $5+2=7$回使っている．
よって，127は，80と47に分けた場合，$5+7=12$回で表される．
このiについて，全探索すれば良い．

以下ACのコード：

main.cpp

#include <iostream>
#include <vector>
#include <algorithm>
#include <string>
#include <cmath>
#include <set>
#include <sstream>
#include <bitset>
#include <stack>
#include <cstdlib>

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

typedef long long ll;

using namespace std;

int main() {

    int n;
    cin >> n;

    int ans=n;

    for(int i=0;i<=n;i++){
        int m=n-i;

        int a=m;
        int p=0;
        while(a>0){
            p += a%6;
            a = a/6;
        }

        int b=i;
        int q=0;
        while(b>0){
            q += b%9;
            b = b/9;
        }

        if(p+q < ans){
            ans =p+q;
        }
    }

    cout << ans << endl;

    return 0;
}

D問題

[問題はこちら]

・N×Nのマスを3色に色分けする．塗り替える時のコストが最小になるようにする．

・$1 \leq C \leq 30$ なので，Cに関するfor文は4回程度なら回せる．

main.cpp

#include <iostream>
#include <vector>
#include <algorithm>
#include <string>
#include <cmath>
#include <set>
#include <sstream>
#include <bitset>
#include <stack>
#include <cstdlib>

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

typedef long long ll;

using namespace std;

int main() {

    int n,c;
    cin >> n >> c;

    vector<vector<int>> d(c, vector<int>(c));

    FOR(i, 0, c){
        FOR(j, 0, c){
            cin >> d[i][j]; //色をiからjに変えるコスト
        }
    }

    vector<vector<int>> x(n, vector<int>(n)); // x：c
    vector<vector<int>> t(3, vector<int>(30,0)); // t[(i+j)%3][a]： あまりが(i+j)%3のときの色aの個数

    FOR(i, 0, n){
        FOR(j, 0, n){
            cin >> x[i][j];
            t[(i+j)%3][x[i][j]-1]++;
        }
    }

    int ans=1<<30; //int型でとりあえず大きい数字

    FOR(i, 0, c){
        FOR(j, 0, c){
            FOR(k, 0, c){
                if((i!=j)&&(j!=k)&&(k!=i)){
                    int tmp=0;
                    FOR(l, 0, c){
                        tmp += d[l][i]*t[0][l]; //あまり0のマス全ての色をlからiに変えたときのコスト
                    }
                    FOR(l, 0, c){
                        tmp += d[l][j]*t[1][l]; //あまり1のマス全ての色をlからjに変えたときのコスト
                    }
                    FOR(l, 0, c){
                        tmp += d[l][k]*t[2][l]; //あまり2のマス全ての色をlからkに変えたときのコスト
                    }

                    if(tmp<ans){
                        ans=tmp;
                    }
                }
            }
        }
    }

    cout << ans << endl;

    return 0;
}

あとがき

精進します．