LoginSignup
0
0

Delete article

Deleted articles cannot be recovered.

Draft of this article would be also deleted.

Are you sure you want to delete this article?

More than 1 year has passed since last update.

@testcampus

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

Posted at

コンテスト名

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

コンテストURL

開催日

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;
}
0
0
0

Register as a new user and use Qiita more conveniently

  1. You get articles that match your needs
  2. You can efficiently read back useful information
  3. You can use dark theme
What you can do with signing up
Sign upLogin
0
0

Delete article

Deleted articles cannot be recovered.

Draft of this article would be also deleted.

Are you sure you want to delete this article?