Zenn
🔵

【ABC345】AtCoder Beginner Contest 345【C++】

2024/03/17に公開
C++
競技プログラミング
AtCoder
アルゴリズム
tech

コンテスト名

モノグサプログラミングコンテスト2024（AtCoder Beginner Contest 345）

コンテストURL

https://atcoder.jp/contests/abc345

開催日

2024/03/16 21:00-22:40

A: Leftrightarrow

解法

  • 条件を満たすかそれぞれ確かめる
    1. 1 文字目は <
    2. S.size() 文字目は >
    3. ほかはすべて =
ABC345A.cpp
#include <iostream>
#include <string>
using namespace std;

int main(){
    string s;
    cin >> s;

    if(s[0]!='<'){
        cout << "No" << endl;
        return 0;
    }
    if(s.back()!='>'){
        cout << "No" << endl;
        return 0;
    }
    for(int i=1; i<s.size()-1; i++){
        if(s[i]!='='){
            cout << "No" << endl;
            return 0;
        }
    }

    cout << "Yes" << endl;
    return 0;
}

B: Integer Division Returns

解法

  • a \geqq 0, b > 0 のとき \left\lceil\frac{a}{b}\right\rceil = \left\lfloor\frac{a + b - 1}{b}\right\rfloor
  • C++ の整数除算は正でも負でも小数点以下を切り捨てる
  • X が負のときはそのまま出力
ABC345B.cpp
#include <iostream>
using namespace std;

int main(){
    long long int x;
    cin >> x;

    if(x>=0){
        cout << (x + (10-1))/10 << endl;
    }else{
        cout << x/10 << endl;
    }

    return 0;
}

C: One Time Swap

解法

  • 文字列 S において i 文字目と j 文字目が異なる整数の組 (i, j) の個数を求める
  • 1 \leqq i < j \leqq N を満たす整数の組 (i, j) は {}_N \mathrm{C}_2 通り
  • i 文字目と j 文字目が同じときは入れ替えても元の文字列 S と変わらない
  • 文字 x が文字列 S に 2 \leqq k \leqq N 個含まれているとき x 同士を入れ替えてできる元の文字列 S と変わらない文字列は {}_k \mathrm{C}_2 通り
  • 各文字の個数を unordered_map<char, long long int> で管理して元の文字列 S と変わらない場合を引く
  • 「元の文字列 S と変わらない場合」も 1 通りと数えるため +1 する
ABC345C.cpp
#include <iostream>
#include <string>
#include <unordered_map>
using namespace std;

int main(){
    string s;
    cin >> s;

    unordered_map<char, long long int> M;
    bool same = false;
    long long int n = s.size();
    for(int i=0; i<n; i++){
        M[s[i]]++;
        if(M[s[i]]>1){
            same = true;
        }
    }

    long long int sum = (n*(n-1))/2;
    long long int cnt = 0;
    for(unordered_map<char, long long int>::iterator it=M.begin(); it!=M.end(); it++){
        pair<char, long long int> item = *it;
        if((item.second*(item.second-1))/2){
            cnt += (item.second*(item.second-1))/2;
        }
    }

    if(same){
        cout << sum - cnt + 1 << endl;
    }else{
        cout << sum << endl;
    }
    
    return 0;
}

D: Tiling

解法

  • 全探索
    1. 順列全探索 + bit 全探索 + マス目全探索
    2. 深さ優先探索 (DFS)
  • 左上からタイルを敷き詰めて全マス埋まれば Yes
  • 標準エラー出力 cerr << endl でどのように埋まったか確認できる
  1. 順列全探索 + bit 全探索 + マス目全探索
    • タイルを並べる順番を順列全探索
    • タイルの向きを bit 全探索
    • 「使用されないタイル」は順列の後ろのほうにあると考える
    • 順列の最後のタイルまで使用する場合（ N 枚すべて利用する場合）の判定場所に注意
    • 空いているマスの座標を代入する変数を -1 などで初期化しておくと判定が楽
  2. 深さ優先探索 (DFS)
    • vector<int> で使用したタイルを記録する
    • for と swap で向きを探索
ABC345D_1.cpp
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

int main(){
    int n, h, w;
    cin >> n >> h >> w;

    vector<int> A(n), B(n);
    for(int i=0; i<n; i++){
        cin >> A[i] >> B[i];
    }

    vector<int> P(n);
    for(int i=0; i<n; i++){
        P[i] = i;
    }

    do{
        for(int i=0; i<(1<<n); i++){
            vector<vector<int>> M(h, vector<int>(w));
            for(int j=0; j<n; j++){
                int check = (i & (1<<j));
                int a, b;
                if(check){
                    a = A[P[j]];
                    b = B[P[j]];
                }else{
                    a = B[P[j]];
                    b = A[P[j]];
                }

                int nh = -1, nw = -1;
                for(int k=0; k<h; k++){
                    for(int l=0; l<w; l++){
                        if(!M[k][l] && nh==-1){
                            nh = k;
                            nw = l;
                        }
                    }
                }

                if(nh+a>h || nw+b>w){
                    break;
                }
                
                bool flag = true;
                for(int k=0; k<a; k++){
                    for(int l=0; l<b; l++){
                        if(M[nh+k][nw+l]){
                            flag = false;
                        }
                        M[nh+k][nw+l] = P[j] + 1;
                    }
                }

                if(!flag){
                    break;
                }

                flag = true;
                for(int k=0; k<h; k++){
                    for(int l=0; l<w; l++){
                        if(!M[k][l]){
                            flag = false;
                        }
                    }
                }
                if(flag){
                    cout << "Yes" << endl;
                    for(int k=0; k<h; k++){
                        for(int l=0; l<w; l++){
                            cerr << M[k][l];
                        }
                        cerr << endl;
                    }
                    return 0;
                }
            }
        }
    }while(next_permutation(P.begin(), P.end()));

    cout << "No" << endl;
    return 0;
}
ABC345D_2.cpp
#include <iostream>
#include <vector>
using namespace std;

int n, h, w;
vector<int> A, B;

bool dfs(vector<vector<int>> &M, vector<int> &used){
    int ni = -1, nj = -1;
    for(int i=0; i<h; i++){
        for(int j=0; j<w; j++){
            if(!M[i][j] && ni==-1){
                ni = i;
                nj = j;
            }
        }
    }

    if(ni==-1){
        for(int k=0; k<h; k++){
            for(int l=0; l<w; l++){
                cerr << M[k][l];
            }
            cerr << endl;
        }
        return true;
    }

    for(int i=0; i<n; i++){
        if(used[i]){
            continue;
        }
        int a = A[i], b = B[i];
        for(int j=0; j<2; j++){
            swap(a, b);
            if(ni+a>h || nj+b>w){
                continue;
            }

            bool flag = true;
            vector<vector<int>> Ms = M;
            vector<int> useds = used;
            for(int k=0; k<a; k++){
                for(int l=0; l<b; l++){
                    if(Ms[ni+k][nj+l]){
                        flag = false;
                    }
                    Ms[ni+k][nj+l] = i + 1;
                }
            }
            if(!flag){
                continue;
            }
            useds[i] = 1;
            if(dfs(Ms, useds)){
                return true;
            }
        }
    }

    return false;
}

int main(){
    cin >> n >> h >> w;

    A.resize(n);
    B.resize(n);
    for(int i=0; i<n; i++){
        cin >> A[i] >> B[i];
    }

    vector<vector<int>> M(h, vector<int>(w, 0));
    vector<int> used(n, 0);
    if(dfs(M, used)){
        cout << "Yes" << endl;
    }else{
        cout << "No" << endl;
    }

    return 0;
}

Discussion