AtCoder Beginner Contest 341 振り返り

ABC341

概要

A - Print 341

考えてたこと
n回1,0の順番に足して最後にもう一回1を足したら解になります。

提出したもの

a.cpp

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

振り返り
特になし。

B - Foreign Exchange

考えてたこと
左から全部右の通貨に変えていって最終的に一番最後の通貨を数える。

提出したもの

b.cpp

int main() {
    ll n;
    cin >> n;
    vector<ll> vec(n);
    rep(i, 0, n) {
        cin >> vec[i];
    }
    rep(i, 0, n - 1) {
        ll s, t;
        cin >> s >> t;
        vec[i + 1] += t * (vec[i] / s);
    }
    cout << vec[n - 1] << endl;
    return 0;
}

振り返り
一回intにしていてWA, longlongに変えてAC。

C - Takahashi Gets Lost

考えてたこと
全部のマス、全部の移動パターンを考えても、hwnで500**3なので計算量足りると最初に気づいたので気楽に解けました。気合いで全探索。

提出したもの

c.cpp

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

    char glid[h][w];
    rep(i, 0, h) {
        rep(j, 0, w) {
            cin >> glid[i][j];
        }
    }

    int ans = 0;
    // 各マススタート地点、n会の移動パターン、計算量h*w*n
    for (int i = 0; i < h; i++) {
        for (int j = 0; j < w; j++) {
            if (glid[i][j] == '#')
                continue;
            bool judge = true;
            int h_now = i;
            int w_now = j;
            fore(a, t) {
                if (a == 'L')
                    w_now--;
                if (a == 'R')
                    w_now++;
                if (a == 'U')
                    h_now--;
                if (a == 'D')
                    h_now++;
                if (glid[h_now][w_now] == '#' || h_now < 0 || h <= h_now || w_now < 0 || w <= w_now) {
                    judge = false;
                    break;
                }
            }
            if (judge)
                ans++;
        }
    }
    cout << ans << endl;
    return 0;
}

振り返り
最初、スタート地点が海の時でもスタートするようにしてたのでテストケースでこける。そこの分岐を作成してAC、ちょっと反省。

D - Only one of two

考えてたこと
解法がよくわからなくてどうせ解けないかな...となんとなくでやっていたら解けてしまった問題、そのため変数名がすごい適当。
方針としてはNとMの最小公倍数でループになるからK番目までに何回ループを通るか、ループの中の何番目かを考えて解く。

提出したもの

d.cpp

ll lcm(ll a, ll b) {
    return a * b / gcd(a, b);
}

int main() {
    ll n, m, k;
    cin >> n >> m >> k;
    ll lcm_num = lcm(n, m);
    // loupの個数で公倍にぶつかる、n=2, m=3とかなら(2-1)+(3-1)=3でループ (2,3,4) (8,9,10)
    ll loup = (lcm_num / n - 1) + (lcm_num / m - 1);
    ll start = k / loup * lcm_num;
    ll nokori = k - (k / loup) * loup;
    if (nokori == 0) {
        start -= min(n, m);
    } else {
        ll n_now = n;
        ll m_now = m;
        for (int i = 0; i < nokori - 1; i++) {
            if (n_now < m_now) {
                n_now += n;
            } else {
                m_now += m;
            }
        }
        start += min(n_now, m_now);
    }
    cout << start << endl;
    return 0;
}

振り返り
解答を見てみたらユーザー解説の別解と方針が同じそう。模範的な回答は二部探索...? 全然思いつかなかったです。とはいえ、解けたこと自体は嬉しい。

感想

お仕事とかでコードに触れることが多いせいか、知識足りなくてもその場で良い感じに回答できるようになってきた気がする。とはいえ、勉強不足であることの証明でもあるのでもっと座学もしていきたいです。