【ABC341】AtCoder Beginner Contest 341【C++】

コンテスト名

トヨタ自動車プログラミングコンテスト2024#2（AtCoder Beginner Contest 341）

コンテストURL

開催日

2024/02/17 21:00-22:40

---

A: Print 341

解法

• 10 を $N$ 回出力したあとに 1 を 1回出力する

ABC341A.cpp

#include <iostream>
using namespace std;

int main(){
    int n;
    cin >> n;
    for(int i=0; i<n; i++){
        cout << 10;
    }
    cout << 1 << endl;
    return 0;
}

B: Foreign Exchange

解法

• 国 $i$ の通貨を可能な限り国 $(i + 1)$ の通貨に交換する
• 国 $i$ の通貨を $\lfloor \frac{A_i}{S_i} \rfloor$ 単位交換して国 $(i + 1)$ の通貨を $\lfloor \frac{A_i}{S_i} \rfloor × T_i$ 単位獲得することを $i = 0, 1,..., N - 2$ の順に繰り返す
• 答えは $A[N - 1]$

ABC341B.cpp

#include <iostream>
#include <vector>
using namespace std;

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

    long long int t, s;
    for(int i=0; i<n-1; i++){
        cin >> s >> t;
        A[i+1] += (A[i]/s)*t;
    }
    
    cout << A[n-1] << endl;
    return 0;
}

C: Takahashi Gets Lost

解法

• 問題文をシミュレーションする
• すべての陸を始点（不時着したマス）として文字列 $T$ の移動ができるかを確かめる

ABC341C.cpp

#include <iostream>
#include <string>
using namespace std;

int A[600][600];

int move(string t, int x, int y, int h, int w){
    for(int i=0; i<t.size(); i++){
        if(t[i]=='L'){
            y--;

            if(y<0 || !A[x][y]){
                return 0;
            }
        }else if(t[i]=='R'){
            y++;
            if(y>w-1 || !A[x][y]){
                return 0;
            }
        }else if(t[i]=='U'){
            x--;
            if(x<0 || !A[x][y]){
                return 0;
            }
        }
        else if(t[i]=='D'){
            x++;
            if(x>h-1 || !A[x][y]){
                return 0;
            }
        }
    }
    return 1;
}   

int main(){
    int h, w, n;
    cin >> h >> w >> n;
    string t;
    cin >> t;
    char c;
    
    for(int i=0; i<h; i++){
        for(int j=0; j<w; j++){
            cin >> c;
            if(c=='.'){
                A[i][j] = 1;
            }else{
                A[i][j] = 0;
            }
        }
    }

    long long int sum = 0;
    for(int i=0; i<h; i++){
        for(int j=0; j<w; j++){
            if(A[i][j]){
                sum += move(t, i, j, h, w);
            }
        }
    }

    cout << sum << endl;
    return 0;
}

D: Only one of two

解法

• 二分探索
• $N, M$ の最小公倍数 $L = lcm(N, M)$
• $X$ 以下の整数のうち $N$ と $M$ のちょうど一方のみで割り切れる数の個数は $\lfloor \frac{X}{N} \rfloor + \lfloor \frac{X}{M} \rfloor - 2 × \lfloor \frac{X}{L} \rfloor$
• 今回の問題の制約下では必ず $\lfloor \frac{X}{N} \rfloor + \lfloor \frac{X}{M} \rfloor - 2 × \lfloor \frac{X}{L} \rfloor \leqq 2 × 10^{18}$ となる
• $l = 0, r = 2 × 10^{18}$ とおいて $r - l \geqq 2$ である限り二分探索
  1. $mid = \lfloor \frac{l + r}{L} \rfloor$
  2. $\lfloor \frac{mid}{N} \rfloor + \lfloor \frac{mid}{M} \rfloor - 2 × \lfloor \frac{mid}{L} \rfloor \geqq K$ ならば $r = mid$ 、そうでないならば $l = mid$
• 答えは $r$

ABC341D.cpp

#include <iostream>
#include <numeric>
using namespace std;

int main(){
    long long int n, m, k;
    cin >> n >> m >> k;

    long long int L = lcm(n, m);
    long long int l = 0;
    long long int r = 2e18;
    long long int mid;
    while(r-l>=2){
        mid = (l+r)/2;
        if((mid/n + mid/m - 2*(mid/L)) >= k){
            r = mid;
        }else{
            l = mid;
        }
    }
    
    cout << r << endl;
    return 0;
}