AtCoder Regular Contest 040 C - Z塗り

問題

 N\times N(N \le 100)のマス目状になっている床を一色に塗ることを考える。一回の塗る操作で、ある整数r,cに対して「i=rかつj\le c」または「i=r + 1かつj \ge c」を満たすような全てのマス(i, j)を塗ることができる。部分的に塗られている初期状態が与えられるので、全てのマスを塗る最小の操作回数を求めよ。

解法

 各行に対して右側からみてまだ塗られていないマスがあったらそこを(r, c)として塗る貪欲法で計算量はO(n^3)でありこの問題が解ける。

反省

 9分4秒(0WA)でAC。特に難しいところもなく。昨日一昨日に比べてこの難易度の差。

コード

#include"bits/stdc++.h"
using namespace std;
using ll = int64_t;

int main() {
    ll N;
    cin >> N;
    vector<string> S(N);
    for (ll i = 0; i < N; i++) {
        cin >> S[i];
    }

    ll ans = 0;
    for (ll i = 0; i < N; i++) {
        for (ll j = N - 1; j >= 0; j--) {
            if (S[i][j] == '.') {
                //(i, j)で一回塗る
                ans++;

                //i段目が塗られる
                for (ll k = 0; k <= j; k++) {
                    S[i][k] = 'o';
                }

                //i + 1段目が塗られる
                if (i != N - 1) {
                    for (ll k = j; k < N; k++) {
                        S[i + 1][k] = 'o';
                    }
                }
            }
        }
    }

    cout << ans << endl;
}

SRM515 Div1 Easy - RotatedClock

問題

 時計の長短針の角度を与えるので時刻として正当なものを出力せよ。

解法

 回して12通り試す。

コード

#include"bits/stdc++.h"
using namespace std;
using ll = int64_t;

class RotatedClock {
public:
    string getEarliest(int hourHand, int minuteHand) {
        for (int i = 0; i < 12; i++) {
            int h = hourHand, m = minuteHand;
            while (h < i * 30) {
                h += 30;
                m += 30;
                m %= 360;
            }
            while (h >= (i + 1) * 30) {
                h -= 30;
                m -= 30;
                m += 360;
                m %= 360;
            }

            if ((h % 30) * 360 == m * 30) {
                string ans;
                if (i < 10) {
                    ans += "0";
                }
                ans += to_string(i);
                ans += ":";
                m /= 6;
                if (m < 10) {
                    ans += "0";
                }
                ans += to_string(m);
                return ans;
            }
        }
        return "";
    }
};

SRM514 Div1 Easy - MagicalGirlLevelOneDivOne

解法

 各nに対して、nが偶数なら適当に式をいじると必ず可能であることがわかる。奇数だけのときはx + y0であるかどうかで判定できる。

コード

#include"bits/stdc++.h"
using namespace std;
using ll = int64_t;

class MagicalGirlLevelOneDivOne {
public:
    string isReachable(vector <int> jumpTypes, int x, int y) {
        x = abs(x);
        y = abs(y);
        for (int n : jumpTypes) {
            if (n % 2 == 0) {
                return "YES";
            }
        }
        return ((x + y) % 2 == 0 ? "YES" : "NO");
    }
};

AtCoder Regular Contest 039 C - 幼稚園児高橋君

問題

 無限に広がる二次元格子について最初(0, 0)から出発し、以下のような行動を繰り返す。

  • 上下左右のうち好きな方向を決めてその方向に今まで訪問したことのない格子に到達するまで直進し、止まる

 直進した回数とそれぞれの方向を与えるので最終的に止まる格子の座標を求めよ。

解法

 二次元座標は無限に広いため各点について情報を保持することはできない。よって到達する格子K個の周囲についてハッシュマップや平衡二分探索木を用いて、次にある方向へ進んだ時に止まる格子を保持することを考える。必要な分だけ情報を更新していくことで計算量はO(K\log{K})となり、この問題が解ける。

反省

 1時間54分(1WA)でAC。20分くらい考えた時点で、到達済みのマスは行および列に関して必ず連続だと勘違いして、各行や列に対して到達した上下限を持っておけばよいというコードを提出してWA。これはちょっと考えれば間違っていることはすぐわかって、たとえばRUDLLUUとかでy = 1において飛び地が形成される。

 結局その後計一時間になるまで考えてわからなかったので解説スライドを見た。mapを使うという発想が頭から飛んでいたのは完全にダメ。行と列についてそれぞれ情報を持つことにしか意識が行っていなかった。

 しかし解説を見た後も実装がよくわからず苦労した。遅延評価というのが何を指していてどう実装するものかピンと来なくて、結局人の提出を写したような感じになってしまった。mapのKey側にどこまで情報を持たせるかというのが結構本質的で、方向をValue側に持たせてしまうとどうしても使わない部分についての初期化が混ざってしまい上手くいかなかった。

 ハッシュを使った提出も見てみたが、うーん、理解ができない……。

コード

#include"bits/stdc++.h"
using namespace std;
using ll = int64_t;

#include<array>

int main() {
    ll K;
    string S;
    cin >> K >> S;

    enum Dir {
        UP, RIGHT, DOWN, LEFT, DIR_NUM
    };
    ll dx[DIR_NUM] = { 0, 1, 0, -1 };
    ll dy[DIR_NUM] = { 1, 0, -1, 0 };

    using Point = pair<ll, ll>;

    //next[{x, y}][i] = (x, y)からiの方向に行くとき次に止まるマス
    map<pair<Point, ll>, Point> next;

    auto update = [&](Point curr) {
        //(x, y)の情報について更新する
        for (ll i = 0; i < DIR_NUM; i++) {
            if (next.find({ curr, i }) == next.end()) {
                next[{curr, i}] = { curr.first + dx[i], curr.second + dy[i] };
            }
        }

        //(x, y)の上下左右について情報を更新する
        for (ll i = 0; i < DIR_NUM; i++) {
            next[{next[{curr, i}], (i + 2) % 4}] = next[{curr, (i + 2) % 4}];
        }
    };

    Point curr(0, 0);

    for (char c : S) {
        update(curr);
        if (c == 'U') {
            curr = next[{curr, UP}];
        } else if (c == 'R') {
            curr = next[{curr, RIGHT}];
        } else if (c == 'D') {
            curr = next[{curr, DOWN}];
        } else if (c == 'L') {
            curr = next[{curr, LEFT}];
        } else {
            assert(false);
        }
    }

    cout << curr.first << " " << curr.second << endl;
}

AtCoder Regular Contest 038 C - 茶碗と豆

問題

 N個の茶碗が横一列に並んでいる。各茶碗iには整数C_iが書かれており、中にはA_i個の豆が入っている。これらを用いて次のゲームを行う。

  • プレイヤーは自分のターンに茶碗0以外の茶碗に入っている豆を1つ選んで取り出す。
  • 茶碗iから豆を取り出したとき、茶碗i - C_i,茶碗i - C_i + 1, \dots, 茶碗i - 1のいずれかの茶碗に豆を入れなければならない。
  • 交互にターンを繰り返し、自分のターンに選べる豆がなくなったプレイヤーの負けとなる。

 両プレイヤーが最適な戦略をとったとき、先手と後手のどちらが勝つか判定せよ。

解法

 Grundy数を考える。i個目の茶碗に入っている豆を遷移させられるのはi - C_iからi - 1までなので、この区間Grundy数に含まれない最小の整数がi番目についてのGrundy数となる。

 これを単純に数えるとO(N^2)以上かかるが、セグメント木を利用して高速化することでO(N(\log{N})^2)で求めることができる。

 具体的な方法としては、まずi番目のGrundy数を求める状況を考えることとする。セグメント木には各Grundy数に対して、そのGrundy数がi - 1番目までで最後にどこで出てきたかを記録しておく。

 このセグメント木を利用して、「i番目のGrundy数としてxが可能かどうか」という二分探索をしていく。セグメント木に[0, x]の範囲でクエリを投げ、x以下のGrundy数として最小の出現位置を得る。これがi - C_iより大きかったらつまりx以下がi - C_iからi - 1の範囲に全て詰まっているということなのでxi番目のGrundy数にはなれない。逆に小さかったらx以下のどれかがi番目のGrundy数として選べる。この判定をもとに二分探索を行うことでこの問題が解ける。

反省

 2時間41分(2WA)でAC。眠気と格闘しながら1時間20分ほど考えたが、そもそもGrundy数という発想がなく全然ダメな考察をしていた。

 そこから解説スライドを見てまず100点分の部分点解法を得る。Grundy数、言われるとなるほどなんだがこれを思いつける気はしない。

 さらに満点を得るためにはセグメント木を実装しなければならず、また他人の提出をいろいろ見てみたところ二分探索部分がセグメント木の中に埋め込まれている? ような感じでよくわからなかった。多少効率は悪いのかもしれないが、セグメント木を用いた値の取得でO(\log{N})、それを使った二分探索でさらにO(\log{N})かかる実装とした。これでも十分間に合う(222msec)。

 セグメント木として確保する範囲が大きすぎて一度REを出してしまった。理解が浅いのでこういうミスが出るという面もあるのだと思う。

 Grundy数とこのセグメント木による高速化は相性が良さそうに思えるが、典型と言えるんだろうか。

コード

#include"bits/stdc++.h"
using namespace std;
using ll = int64_t;

class SegmentTree {
public:
    SegmentTree(ll n, ll value) {
        n_ = (ll)pow(2, ceil(log2(n)));
        nodes_.resize(2 * n_ - 1, value);
    }
    void update(ll x, ll v) {
        nodes_[x + n_ - 1] = v;
        for (ll i = (x + n_ - 2) / 2; i > 0; i = (i - 1) / 2) {
            nodes_[i] = min(nodes_[2 * i + 1], nodes_[2 * i + 2]);
        }
    }

    ll getMin(ll a, ll b, ll k = 0, ll l = 0, ll r = -1) {
        if (r < 0) {
            r = n_;
        }
        if (r <= a || b <= l) {
            return INT_MAX;
        }
        if (a <= l && r <= b) {
            return nodes_[k];
        }
        ll left  = getMin(a, b, 2 * k + 1, l, (l + r) / 2);
        ll right = getMin(a, b, 2 * k + 2, (l + r) / 2, r);
        return min(left, right);
    }

private:
    //2のべき乗
    ll n_;
    vector<ll> nodes_;
};

int main() {
    ll N;
    cin >> N;
    vector<ll> C(N), A(N);
    C[0] = A[0] = 0;
    ll sum = 0;
    for (ll i = 1; i < N; i++) {
        cin >> C[i] >> A[i];
        sum += A[i];
    }

    constexpr ll MAX = 1e5 + 1;
    SegmentTree st(MAX, -1);

    vector<ll> grundy(N);
    grundy[0] = 0;
    st.update(0, 0);
    for (ll i = 1; i < N; i++) {
        //取り得るgrundy数について2分探索をする
        ll ng = -1, ok = MAX;
        while (ng + 1 != ok) {
            ll mid = (ng + ok) / 2;

            //0からmidまでのgrundy数について,今まで出てきた位置の最小値を求める
            ll min_index = st.getMin(0, mid + 1);
            (min_index >= i - C[i] ? ng = mid : ok = mid);
        }
        grundy[i] = ok;
        st.update(grundy[i], i);
    }

    ll xor_value = 0;
    for (ll i = 1; i < N; i++) {
        if (A[i] % 2) {
            xor_value ^= grundy[i];
        }
    }

    cout << (xor_value == 0 ? "Second" : "First") << endl;
}

AtCoder Regular Contest 037 C - 億マス計算

問題

 N個の数列が二つ与えられ、それぞれa_1, \dots, a_Nおよびb_1, \dots, b_Nとする。これらを用いてNN列の表を、ij列目にはa_i \times b_jが書き込まれるように作成する。書き込まれた数字の中でK番目に大きい数字を求めよ。

解法

 K番目に大きい数字とは「その数字以下の数字がK個以上書き込まれているようなもののなかで最小の数字」である。これを二分探索する。

 ある数字X以下の数字が何個書き込まれているかは、あらかじめa_1, \dots, a_Nb_1, \dots, b_Nをソートしておけば、iを固定したときa_ib_jをかけた値がX以下となるjを二分探索で求めることができる。

 よって全体でa_1, \dots, a_Nb_1, \dots, b_Nの中での最大値をそれぞれA, Bとしたとき、計算量はO(N(\log{N})(\log{AB}))となりこの問題が解けた。

反省

 24分12秒(0WA)でAC。最初はよくわからなかったけどまずa,bをソートするんだろうなというのは思いついたところ。そしてサンプルの3個目について表を作ってみたらなんとなく各a_iに対してどこまで小さい数字かは二分探索で求めることができそうだなとわかり、また最近『K番目に大きい数字とは「その数字以下の数字がK個以上書き込まれているようなもののなかで最小の数字」』みたいな変換をARC101のMedian of Mediansでやったのを思い出して想定解がわかった。典型と言えるような変換なんだろう。

コード

#include"bits/stdc++.h"
using namespace std;
using ll = int64_t;

int main() {
    ll N, K;
    cin >> N >> K;
    vector<ll> a(N), b(N);
    for (ll i = 0; i < N; i++) {
        cin >> a[i];
    }
    for (ll i = 0; i < N; i++) {
        cin >> b[i];
    }
    sort(a.begin(), a.end());
    sort(b.begin(), b.end());

    auto isOK = [&](ll x) {
        //x以下のものがK個以上あるか判定
        ll num = 0;
        for (ll i = 0; i < N; i++) {
            if (a[i] * b[0] > x) {
                //ここから先でx以下となることはない
                break;
            }
            if (a[i] * b[N - 1] <= x) {
                //全てx以下
                num += N;
                continue;
            }

            ll low = 0, high = N - 1;
            while (low + 1 != high) {
                ll mid = (low + high) / 2;
                (a[i] * b[mid] <= x ? low = mid : high = mid);
            }
            num += low + 1;
        }
        return num >= K;
    };

    ll ng = 0, ok = pow(1e9, 2) + 1;
    while (ng + 1 != ok) {
        ll mid = (ok + ng) / 2;
        (isOK(mid) ? ok = mid : ng = mid);
    }

    cout << ok << endl;
}

AtCoder Regular Contest 035 C - アットコーダー王国の交通事情

問題

 N個の都市がM本の道路で結ばれている。道路には長さがあり、各都市i,j間の最短距離の総和をSとする。初期状態からK本の新しい道路を建設していくとき、各道路が作られた後のSを求めよ。

解法

 新たな道路が都市X,Yを長さZで結ぶとき、各都市i,jについて最短距離を更新し得るのはi \to X\to Y \to jあるいはi \to Y \to X \to jのどちらか。つまり一般の都市aからbへのコストを保持しておけばこれはO(1)で求まる。i,jの選び方がそれぞれN通りあり、新たな道路はK本なので全体の計算量はO(KN^2)。初期状態において各都市間の最短距離を求めることについてもワーシャルフロイド法を用いればO(N^3)で計算できるので間に合う。

反省

 23分00秒(0WA)でAC。問題を理解できればとくに難しいところもなく。和を差分計算する必要があるかなと一瞬思ったが、計算量的には変わらないので面倒くさくて毎回O(N^2)かけて計算するままに。400^3が間に合うものなのかちょっと不安だったが495msで通った。つまり10^9でも簡単な処理ならギリギリ通ってしまう? このあたりの間に合うかどうかの感覚はよくわからないまま。

コード

#include"bits/stdc++.h"
using namespace std;
using ll = int64_t;

int main() {
    ll N, M;
    cin >> N >> M;
    
    struct Edge {
        ll to, cost;
    };
    vector<vector<Edge>> edges(N);
    for (ll i = 0; i < M; i++) {
        ll A, B, C;
        cin >> A >> B >> C;
        A--; B--;
        edges[A].push_back({ B, C });
        edges[B].push_back({ A, C });
    }

    ll K;
    cin >> K;
    vector<ll> X(K), Y(K), Z(K);
    for (ll i = 0; i < K; i++) {
        cin >> X[i] >> Y[i] >> Z[i];
        X[i]--; Y[i]--;
    }

    vector<vector<ll>> cost(N, vector<ll>(N, INT_MAX));
    for (ll i = 0; i < N; i++) {
        for (auto e : edges[i]) {
            cost[i][e.to] = min(cost[i][e.to], e.cost);
        }
        cost[i][i] = 0;
    }
    for (ll k = 0; k < N; k++) {
        for (ll i = 0; i < N; i++) {
            for (ll j = 0; j < N; j++) {
                cost[i][j] = min(cost[i][j], cost[i][k] + cost[k][j]);
            }
        }
    }

    auto getSum = [&]() {
        ll sum = 0;
        for (ll i = 0; i < N; i++) {
            for (ll j = i + 1; j < N; j++) {
                sum += cost[i][j];
            }
        }
        return sum;
    };

    for (ll i = 0; i < K; i++) {
        for (ll j = 0; j < N; j++) {
            for (ll k = 0; k < N; k++) {
                ll cost1 = cost[j][X[i]] + cost[Y[i]][k] + Z[i];
                ll cost2 = cost[j][Y[i]] + cost[X[i]][k] + Z[i];
                cost[j][k] = min({ cost[j][k], cost1, cost2 });
                cost[k][j] = min({ cost[k][j], cost1, cost2 });
            }
        }
        cost[X[i]][Y[i]] = min(cost[X[i]][Y[i]], Z[i]);
        cost[Y[i]][X[i]] = min(cost[Y[i]][X[i]], Z[i]);

        cout << getSum() << endl;
    }
}

AtCoder Regular Contest 034 C - 約数かつ倍数

問題

 正整数A, Bが与えられる。A!の約数であり、かつB!の倍数でもあるような整数の個数を求めよ。

解法

 求めるものは結局\frac{A!}{B!}の約数の個数である。これはB+1, \dots, Aまでの数字を素因数分解し、登場する素因数の数を数えていくことで求めることができる(約数の個数の公式)。各素因数分解にかかる計算量は数字nに対してO(\sqrt{n})であり、A - B \le 100という制約があるためこれでこの問題を解くことができた。

反省

 56分42秒(1WA)で久々に自力AC。まずこの手の問題を見たら初手としてやることは小さい数字での実験と決めているんだけど、この問題ではあまり有効ではなかったかもしれない。いろいろ見ているうちに、ようやくABの差分のところだけを考えればいいことに気が付く。しかし約数の個数を上手く求める方法を忘れていてその後もかなり手間取ってしまった。しばらくしてから素因数分解すれば求まるんだったなと思ってググって確証を得てから実装し、なんとかAC。一度素因数分解をするところをO(n)で実装してしまいTLEを出してしまった。そこまで難しい問題でもないと思うのでもっとすんなり解きたかった。

コード

#include"bits/stdc++.h"
using namespace std;
using ll = int64_t;

constexpr ll MOD = (ll)1e9 + 7;

vector<pair<ll, ll>> getFactor(ll x) {
    vector<pair<ll, ll>> result;
    for (ll i = 2; i * i <= x; i++) {
        ll num = 0;
        while (x % i == 0) {
            x /= i;
            num++;
        }
        if (num) {
            result.push_back({ i, num });
        }
        if (x <= 1) {
            break;
        }
    }
    if (x > 1) {
        result.push_back({ x, 1 });
    }
    return result;
}

ll solve(ll a, ll b) {
    map<ll, ll> factor;
    for (ll i = b + 1; i <= a; i++) {
        auto f = getFactor(i);
        for (auto p : f) {
            factor[p.first] += p.second;
        }
    }

    ll ans = 1;
    for (auto p : factor) {
        ans *= p.second + 1;
        ans %= MOD;
    }
    return ans;
}

int main() {
    ll A, B;
    cin >> A >> B;
    cout << solve(A, B) << endl;
}

SRM513 Div1 Easy - YetAnotherIncredibleMachine

問題

 n枚の板について長さと設置できる上下限位置が与えられる。またm個のボールが各座標に落とされる。板に一つもボールが落ちないような板の配置方法が何通りあるか求めよ。

解法

 ボールが落ちる位置について累積和を取って、各板が設置可能な範囲を二分探索で求める。

反省

 問題の把握にいくらか時間がかかったのと、端の関係とか二分探索の含める含めない、範囲指定などでかなり混乱した。

コード

#include"bits/stdc++.h"
using namespace std;
using ll = int64_t;

class  YetAnotherIncredibleMachine {
public:
    int countWays(vector<int> platformMount, vector<int> platformLength, vector<int> balls) {
        constexpr int MAX = 2e5;
        vector<int> num(2 * MAX + 2, 0);
       
        int* p = &num[MAX + 1];
        for (int b : balls) {
            p[b]++;
        }
        for (int i = -MAX; i < MAX; i++) {
            p[i + 1] += p[i];
        }

        constexpr ll MOD = 1e9 + 9;
        ll ans = 1;
        for (int i = 0; i < platformMount.size(); i++) {
            ll curr_pattern = 0;

            //可能な左端についてループする
            for (int l = platformMount[i] - platformLength[i]; l <= platformMount[i]; ) {
                if (p[l] == p[l - 1] + 1) {
                    l++;
                    continue;
                }
                int n = p[l];
                int r = upper_bound(&p[l], &p[platformMount[i] + platformLength[i] + 1], n) - &p[0];
                curr_pattern += max(r - l - platformLength[i], 0);
                curr_pattern %= MOD;
                l = r;
            }

            ans *= curr_pattern;
            ans %= MOD;
        }

        return ans;
    }
};

SRM512 Div1 Easy - MysteriousRestaurant

問題

 N日間営業するレストランで夕食を食べることを考える。レストランは常にM種類のパターンを用意しているが、ある曜日にあるパターンの夕食を食べると、同じ曜日には同じパターンの夕食した食べられない。i日目のj番目のパターンに対するコストを与えるので、budgetコスト内で1日目から連続して最大何日食べることができるかを求めよ。

解法

 i日目まで食べられるとして、j曜日に食べるべきパターンはそれぞれ独立に計算することができる。その計算にはO(NM)かかり全体としてO(N^2M\times7)となるが、制約からせいぜい7\times 50^3にしかならないのでこれでこの問題が解けた。

反省

 いろいろガチャガチャいじっていたらなんか解けた。あまり理屈っぽく解いている気がしない。

コード

#include"bits/stdc++.h"
using namespace std;
using ll = int64_t;

class MysteriousRestaurant {
public:
    int maxDays(vector<string> prices, int budget) {
        for (ll i = prices.size(); i >= 0; i--) {
            ll cost = 0;
            for (ll j = 0; j < min((ll)7, i); j++) {
                ll j_cost = INT_MAX;
                for (ll k = 0; k < prices[0].size(); k++) {
                    ll c = 0;
                    for (ll l = j; l < i; l += 7) {
                        c += char2value(prices[l][k]);
                    }
                    j_cost = min(j_cost, c);
                }
                cost += j_cost;
            }
            if (cost <= budget) {
                return (int)i;
            }
        }
        return 0;
    }
private:
    ll char2value(char c) {
        if ('0' <= c && c <= '9') {
            return c - '0';
        } else if ('A' <= c && c <= 'Z') {
            return c - 'A' + 10;
        } else {
            return c - 'a' + 36;
        }
    }
};