AtCoder Recommendation 埋め

C - Unification

最初は配列の最後尾から０と１を取り除くことを考えました。
しかし計算量が多いと思い組むだけにしました。

C++

#include <bits/stdc++.h>

#define rep(i,n) for(int i=0; i<(n); ++i)
#define fixed_setprecision(n) fixed << setprecision((n))
#define execution_time(ti) printf("Execution Time: %.4lf sec\n", 1.0 * (clock() - ti) / CLOCKS_PER_SEC);
#define pai 3.1415926535897932384
#define NUM_MAX 2e18
#define NUM_MIN -1e9

using namespace std;
using ll =long long;
using P = pair<int,int>;
template<class T> inline bool chmax(T& a, T b){ if(a<b){ a=b; return 1; } return 0; }
template<class T> inline bool chmin(T& a, T b){ if(a>b){ a=b; return 1; } return 0; }
const long long INF = 1LL << 60;

int main(int argc, const char * argv[]) {
    string s;
    cin >> s;

    int cnt=s.length();
    int res=0;
    while(cnt>0){
        if((s[cnt-1] == '1' && s[cnt-2] == '0') || (s[cnt-1] == '0' && s[cnt-2] == '1')){
            s.erase(cnt-2, 2);
            cnt=s.length();
            res+=2;
        }else{
            cnt--;
        }
    }
    cout << res << endl;

    return 0;
}

上記のコードをサンプルケースで動かすと分かることは、0か１の少ない数の分*２だけキューブを取り除きます。

C++

#include <bits/stdc++.h>

#define rep(i,n) for(int i=0; i<(n); ++i)
#define fixed_setprecision(n) fixed << setprecision((n))
#define execution_time(ti) printf("Execution Time: %.4lf sec\n", 1.0 * (clock() - ti) / CLOCKS_PER_SEC);
#define pai 3.1415926535897932384
#define NUM_MAX 2e18
#define NUM_MIN -1e9

using namespace std;
using ll =long long;
using P = pair<int,int>;
template<class T> inline bool chmax(T& a, T b){ if(a<b){ a=b; return 1; } return 0; }
template<class T> inline bool chmin(T& a, T b){ if(a>b){ a=b; return 1; } return 0; }
const long long INF = 1LL << 60;

int main(int argc, const char * argv[]) {
    string s;
    cin >> s;

    int cnt=0;
    int cnt_0=0;
    int cnt_1=0;
    while(cnt<s.length()){
        if(s[cnt] == '0'){
            cnt_0++;
        }else if(s[cnt] == '1'){
            cnt_1++;
        }
        cnt++;
    }
    cout << 2 * min(cnt_0, cnt_1) << endl;

    return 0;
}

B - 高橋君とパスワード

setでもmapでも同じことができた。
しかし集合だからsetかな。

C++

#include <bits/stdc++.h>

#define rep(i,n) for(int i=0; i<(n); ++i)
#define fixed_setprecision(n) fixed << setprecision((n))
#define execution_time(ti) printf("Execution Time: %.4lf sec\n", 1.0 * (clock() - ti) / CLOCKS_PER_SEC);
#define pai 3.1415926535897932384
#define NUM_MAX 2e18
#define NUM_MIN -1e9

using namespace std;
using ll =long long;
using P = pair<int,int>;
template<class T> inline bool chmax(T& a, T b){ if(a<b){ a=b; return 1; } return 0; }
template<class T> inline bool chmin(T& a, T b){ if(a>b){ a=b; return 1; } return 0; }
const long long INF = 1LL << 60;

int main(int argc, const char * argv[]) {
    string s;
    int k;
    cin >> s >> k;

    set<string> s_list;
    for(int i=0; i+k<=s.length(); i++){
        s_list.insert(s.substr(i, k));
    }
    cout << s_list.size() << endl;

    return 0;
}

C - Many Requirements

一番最初に考えた実装

C++

#include <bits/stdc++.h>

#define rep(i,n) for(int i=0; i<(n); ++i)
#define fixed_setprecision(n) fixed << setprecision((n))
#define execution_time(ti) printf("Execution Time: %.4lf sec\n", 1.0 * (clock() - ti) / CLOCKS_PER_SEC);
#define pai 3.1415926535897932384
#define NUM_MAX 2e18
#define NUM_MIN -1e9

using namespace std;
using ll =long long;
using P = pair<int,int>;
template<class T> inline bool chmax(T& a, T b){ if(a<b){ a=b; return 1; } return 0; }
template<class T> inline bool chmin(T& a, T b){ if(a>b){ a=b; return 1; } return 0; }
const long long INF = 1LL << 60;

int main(int argc, const char * argv[]) {
    int n, m, q;
    cin >> n >> m >> q;

    vector<int> A(q), B(q), C(q), D(q);
    rep(i, q) cin >> A[i] >> B[i] >> C[i] >> D[i];

    int res = 0;
    for (int a = 1; a <= m; ++a) {
        for (int b = a; b <= m; ++b) {
            for (int c = b; c <= m; ++c) {
                for (int d = c; d <= m; ++d) {
                    for (int e = d; e <= m; ++e) {
                        for (int f = e; f <= m; ++f) {
                            for (int g = f; g <= m; ++g) {
                                for (int h = g; h <= m; ++h) {
                                    for (int i = h; i <= m; ++i) {
                                        for (int j = i; j <= m; ++j) {
                                            //cout << a << b << c << d << e << f << g << h << i << j << endl;
                                            int sum = 0;
                                            for (int k = 0; k < q; ++k) {
                                                int X;
                                                switch (A[k])
                                                {
                                                case 1:
                                                    X = a;
                                                    break;
                                                case 2:
                                                    X = b;
                                                    break;
                                                case 3:
                                                    X = c;
                                                    break;   
                                                case 4:
                                                    X = d;
                                                    break;
                                                case 5:
                                                    X = e;
                                                    break;  
                                                case 6:
                                                    X = f;
                                                    break;
                                                case 7:
                                                    X = g;
                                                    break;
                                                case 8:
                                                    X = h;
                                                    break;
                                                case 9:
                                                    X = i;
                                                    break;
                                                case 10:
                                                    X = j;
                                                    break;                                                                                 
                                                default:
                                                    break;
                                                }

                                                int Y;
                                                switch (B[k])
                                                {
                                                case 1:
                                                    Y = a;
                                                    break;
                                                case 2:
                                                    Y = b;
                                                    break;
                                                case 3:
                                                    Y = c;
                                                    break;   
                                                case 4:
                                                    Y = d;
                                                    break;
                                                case 5:
                                                    Y = e;
                                                    break;  
                                                case 6:
                                                    Y = f;
                                                    break;
                                                case 7:
                                                    Y = g;
                                                    break;
                                                case 8:
                                                    Y = h;
                                                    break;
                                                case 9:
                                                    Y = i;
                                                    break;
                                                case 10:
                                                    Y = j;
                                                    break;                                                                                 
                                                default:
                                                    break;
                                                }

                                                if(Y - X == C[k]){
                                                    sum += D[k];
                                                }
                                            }

                                            res = max(res, sum);
                                        }
                                    }
                                }
                            }
                        }
                    }
                }
            }
        }
    }
    cout << res << endl;

    return 0;
}

綺麗に実装すると、

C++

#include <bits/stdc++.h>

#define rep(i,n) for(int i=0; i<(n); ++i)
#define fixed_setprecision(n) fixed << setprecision((n))
#define execution_time(ti) printf("Execution Time: %.4lf sec\n", 1.0 * (clock() - ti) / CLOCKS_PER_SEC);
#define pai 3.1415926535897932384
#define NUM_MAX 2e18
#define NUM_MIN -1e9

using namespace std;
using ll =long long;
using P = pair<int,int>;
template<class T> inline bool chmax(T& a, T b){ if(a<b){ a=b; return 1; } return 0; }
template<class T> inline bool chmin(T& a, T b){ if(a>b){ a=b; return 1; } return 0; }
const long long INF = 1LL << 60;

int n, m, q;
vector<int> a, b, c, d;

ll score(const vector<int> &A){
    ll res=0;
    rep(i, q) if(A[b[i]] - A[a[i]] == c[i]) res += d[i];
    return res;
}

ll dfs(vector<int> &A){
    if(A.size() == n){
        return score(A);
    }

    ll res=0;
    int prev_last = (A.empty()? 0:A.back());
    for(int add=prev_last; add<m; add++){
        A.push_back(add);
        res = max(res, dfs(A));
        A.pop_back();
    }
    return res;
}

int main(int argc, const char * argv[]) {
    cin >> n >> m >> q;

    a.resize(q), b.resize(q), c.resize(q), d.resize(q);
    rep(i, q){
        cin >> a[i] >> b[i] >> c[i] >> d[i];
        a[i]--, b[i]--;
    }

    vector<int> A;
    cout << dfs(A) << endl;

    return 0;
}

B - 時計盤

長針は３６０/６０とみんな思い浮かぶ。
短針は 360/12 と 360/12/60の組み合わせを知っているか。

C++

#include <bits/stdc++.h>

#define rep(i,n) for(int i=0; i<(n); ++i)
#define fixed_setprecision(n) fixed << setprecision((n))
#define execution_time(ti) printf("Execution Time: %.4lf sec\n", 1.0 * (clock() - ti) / CLOCKS_PER_SEC);
#define pai 3.1415926535897932384
#define NUM_MAX 2e18
#define NUM_MIN -1e9

using namespace std;
using ll =long long;
using P = pair<int,int>;
template<class T> inline bool chmax(T& a, T b){ if(a<b){ a=b; return 1; } return 0; }
template<class T> inline bool chmin(T& a, T b){ if(a>b){ a=b; return 1; } return 0; }
const long long INF = 1LL << 60;

int main(int argc, const char * argv[]) {
    int n, m;
    cin >> n >> m;

    n = n % 12;
    m = m % 60;

    double l = 360 / 60 * (double)m;
    double r = 360.0 / 12.0 / 60.0 * (double)m + 360 / 12 * (double)n;
    double res = (abs(r - l) < 180)? abs(r - l):360 - abs(r - l);
    cout << fixed_setprecision(10) << res << endl;

    return 0;
}

A - 鉛筆リサイクルの新技術

C++

#include <bits/stdc++.h>

#define rep(i,n) for(int i=0; i<(n); ++i)
#define fixed_setprecision(n) fixed << setprecision((n))
#define execution_time(ti) printf("Execution Time: %.4lf sec\n", 1.0 * (clock() - ti) / CLOCKS_PER_SEC);
#define pai 3.1415926535897932384
#define NUM_MAX 2e18
#define NUM_MIN -1e9

using namespace std;
using ll =long long;
using P = pair<int,int>;
template<class T> inline bool chmax(T& a, T b){ if(a<b){ a=b; return 1; } return 0; }
template<class T> inline bool chmin(T& a, T b){ if(a>b){ a=b; return 1; } return 0; }
const long long INF = 1LL << 60;

int main(int argc, const char * argv[]) {
    int m, n, N;
    cin >> m >> n >> N;

    int l = 0;
    int res = N;
    while((N + l) >= m){
        res += ((N + l) / m) * n;
        int tmp = N;
        N = ((N + l) / m) * n;
        l = (tmp + l) % m;
    }
    cout << res << endl;

    return 0;
}

B - 回転

図を書くだけ。

C++

#include <bits/stdc++.h>

#define rep(i,n) for(int i=0; i<(n); ++i)
#define fixed_setprecision(n) fixed << setprecision((n))
#define execution_time(ti) printf("Execution Time: %.4lf sec\n", 1.0 * (clock() - ti) / CLOCKS_PER_SEC);
#define pai 3.1415926535897932384
#define NUM_MAX 2e18
#define NUM_MIN -1e9

using namespace std;
using ll =long long;
using P = pair<int,int>;
template<class T> inline bool chmax(T& a, T b){ if(a<b){ a=b; return 1; } return 0; }
template<class T> inline bool chmin(T& a, T b){ if(a>b){ a=b; return 1; } return 0; }
const long long INF = 1LL << 60;

char c[4][4];

int main(int argc, const char * argv[]) {

    rep(i, 4){
        rep(j, 4){
            cin >> c[i][j];
        }
    }

    for(int i=3; i>=0; i--){
        for(int j=3; j>=0; j--){
            if(j>0) cout << c[i][j] << ' ';
            else cout << c[i][j] << endl;
        }
    }

    return 0;
}

B - ss

２で割って中心点を見つける。

C++

#include <bits/stdc++.h>

#define rep(i,n) for(int i=0; i<(n); ++i)
#define fixed_setprecision(n) fixed << setprecision((n))
#define execution_time(ti) printf("Execution Time: %.4lf sec\n", 1.0 * (clock() - ti) / CLOCKS_PER_SEC);
#define pai 3.1415926535897932384
#define NUM_MAX 2e18
#define NUM_MIN -1e9

using namespace std;
using ll =long long;
using P = pair<int,int>;
template<class T> inline bool chmax(T& a, T b){ if(a<b){ a=b; return 1; } return 0; }
template<class T> inline bool chmin(T& a, T b){ if(a>b){ a=b; return 1; } return 0; }
const long long INF = 1LL << 60;

int main(int argc, const char * argv[]) {
    string s;
    cin >> s;

    for(int i=1; i<s.length(); i++){
        int r = s.length() - i, l;
        string s1, s2;

        if(r%2==0){
            l = r / 2;
            s1 = s.substr(0, l);
            s2 = s.substr(l, l);
        }else{
            l = r / 2;
            s1 = s.substr(0, l+1);
            s2 = s.substr(l+1, l);
        } 

        if(s1 == s2){
            cout << s.length() - i << endl;
            break;
        }
    }

    return 0;
}

B - String Rotation

C++

#include <bits/stdc++.h>

#define rep(i,n) for(int i=0; i<(n); ++i)
#define fixed_setprecision(n) fixed << setprecision((n))
#define execution_time(ti) printf("Execution Time: %.4lf sec\n", 1.0 * (clock() - ti) / CLOCKS_PER_SEC);
#define pai 3.1415926535897932384
#define NUM_MAX 2e18
#define NUM_MIN -1e9

using namespace std;
using ll =long long;
using P = pair<int,int>;
template<class T> inline bool chmax(T& a, T b){ if(a<b){ a=b; return 1; } return 0; }
template<class T> inline bool chmin(T& a, T b){ if(a>b){ a=b; return 1; } return 0; }
const long long INF = 1LL << 60;

int main(int argc, const char * argv[]) {
    string s, t;
    cin >> s >> t;

    int n = t.length();
    bool res = false;
    rep(i, n){
        if(s == t){
            res = true;
            break;
        }else{
            char tmp = t[0];
            t.erase(0, 1);
            t += tmp;
        }
    }
    if(res) cout << "Yes" << endl;
    else cout << "No" << endl;

    return 0;
}

A - 大文字と小文字

C++

#include <bits/stdc++.h>

#define rep(i,n) for(int i=0; i<(n); ++i)
#define fixed_setprecision(n) fixed << setprecision((n))
#define execution_time(ti) printf("Execution Time: %.4lf sec\n", 1.0 * (clock() - ti) / CLOCKS_PER_SEC);
#define pai 3.1415926535897932384
#define NUM_MAX 2e18
#define NUM_MIN -1e9

using namespace std;
using ll =long long;
using P = pair<int,int>;
template<class T> inline bool chmax(T& a, T b){ if(a<b){ a=b; return 1; } return 0; }
template<class T> inline bool chmin(T& a, T b){ if(a>b){ a=b; return 1; } return 0; }
const long long INF = 1LL << 60;

int main(int argc, const char * argv[]) {
    char A, a;
    cin >> A >> a;

    a = a - 32;
    if(A == a) cout << "Yes"<< endl;
    else cout << "No"<< endl;

    return 0;
}

A - 立方数

python

N = int(input())

for i in range(1, N+1):
  if i * i * i == N:
    print("YES")
    break
else:
  print("NO")

A - ホリドッグ

C++

#include <bits/stdc++.h>

#define rep(i,n) for(int i=0; i<(n); ++i)
#define fixed_setprecision(n) fixed << setprecision((n))
#define execution_time(ti) printf("Execution Time: %.4lf sec\n", 1.0 * (clock() - ti) / CLOCKS_PER_SEC);
#define pai 3.1415926535897932384
#define NUM_MAX 2e18
#define NUM_MIN -1e9

using namespace std;
using ll =long long;
using P = pair<int,int>;
template<class T> inline bool chmax(T& a, T b){ if(a<b){ a=b; return 1; } return 0; }
template<class T> inline bool chmin(T& a, T b){ if(a>b){ a=b; return 1; } return 0; }
const long long INF = 1LL << 60;

int main(void) {
    int n;
    cin >> n;
    int sum = n * (n + 1) / 2;

    if(sum == 1){
        cout << "BOWWOW" << endl;
        return 0;
    }

    bool is_prime_number = true;
    for(int i=2; i*i<=sum; i++){
        if(sum % i == 0){
            is_prime_number = false;
            break;
        }
    }
    if(is_prime_number) cout << "WANWAN" << endl;
    else cout << "BOWWOW" << endl;

    return 0;
}

B - Shiritori

python

N = int(input())

A = [""] * N
is_ok = True
for i in range(0, N):
  S = str(input())
  if A.count(S) > 0:
    is_ok = False

  A[i] = S
  if i>0:
    if A[i-1][len(A[i-1])-1] != A[i][0]:
      is_ok = False

if(is_ok):
  print("Yes")
else:
  print("No")

A - 長方形

python

l1, l2, l3 = list(map(int, input().split()))

print(l1 ^ l2 ^ l3)