2020-11-09

AtCoder Beginner Contest 182 に参加しました

調子よかった回のことばっかり書いてる気がしてきたから、そうでもない回のことも書いておきます。
atcoder.jp

成績

f:id:gyouzasushi:20201109000757p:plain f:id:gyouzasushi:20201109000748p:plain

A - twiblr

問題：（リンク）
$B \leq 2\times A+100$ の制約見落としてた。max とる必要なし

コードを表示

#include <bits/stdc++.h>
using namespace std;
using ll = long long;
int main() {
    ll a, b;
    cin >> a >> b;
    cout << max(0ll, (2 * a + 100) - b) << '\n';
}

B - Almost GCD

問題：（リンク）
std::max_element 使うと楽？

コードを表示

#include <bits/stdc++.h>
#define rep(i, n) for (int i = 0; i < (int)(n); i++)
using namespace std;
int main() {
    int n;
    cin >> n;
    vector<int> a(n);
    rep(i, n) cin >> a[i];
    vector<int> cnt(1010, 0);
    for (int k = 2; k < 1010; k++) {
        rep(i, n) if (a[i] % k == 0) cnt[k]++;
    }
    cout << max_element(cnt.begin(), cnt.end()) - cnt.begin() << '\n';
}

C - To 3

問題：（リンク）
場合分けした。でもbit全探索の方が楽だしバグらせないし賢いね。

コードを表示

#include <bits/stdc++.h>
#define sz(x) int(x.size())
using namespace std;
using ll = long long;
int main() {
    ll n;
    cin >> n;
    string s = to_string(n);
    vector<int> cnt(3);
    for (char c : s) cnt[(c - '0') % 3]++;
    if (n % 3 == 0) {
        cout << 0 << '\n';
    } else if (n % 3 == 1) {
        if (cnt[1] >= 1 && sz(s) > 1) {
            cout << 1 << '\n';
        } else if (cnt[2] >= 2 && sz(s) > 2) {
            cout << 2 << '\n';
        } else {
            cout << -1 << '\n';
        }
    } else if (n % 3 == 2) {
        if (cnt[2] >= 1 && sz(s) > 1) {
            cout << 1 << '\n';
        } else if (cnt[1] >= 2 && sz(s) > 2) {
            cout << 2 << '\n';
        } else {
            cout << -1 << '\n';
        }
    }
}

D - Wandering

問題：（リンク）
累積累積maxみたいなのを見ればOK。

コードを表示

#include <bits/stdc++.h>
#define rep(i, n) for (int i = 0; i < (int)(n); i++)
using namespace std;
using ll = long long;
template <class T>
bool chmax(T& a, const T& b) {
    if (a < b) {
        a = b;
        return 1;
    }
    return 0;
}
int main() {
    int n;
    cin >> n;
    vector<ll> a(n);
    rep(i, n) cin >> a[i];
    vector<ll> maxs(n);
    maxs[0] = a[0];
    rep(i, n - 1) {
        a[i + 1] += a[i];
        maxs[i + 1] = max(maxs[i], a[i + 1]);
    }

    ll ans = 0, pos = 0;
    rep(i, n) {
        chmax(ans, pos + maxs[i]);
        pos += a[i];
    }
    cout << ans << '\n';
}

E - Akari

問題：（リンク）
お前も鬼にならないか？ならない。
またまたグリッドを照らすんか、逆に Lamp とか Lamps とは何が違うんや？と少しフリーズしてしまってもったいない。ブロックとブロックの間に電球が存在するか？を縦横に全部みればOK。
配列外参照で1ペナ。めっちゃ配列外参照しちゃう。配列内参照が難しいんかもしれん。逆にね。

コードを表示

#include <bits/stdc++.h>
#define rep(i, n) for (int i = 0; i < (int)(n); i++)
using namespace std;
int main() {
    int h, w, n, m;
    cin >> h >> w >> n >> m;
    vector<vector<bool>> lamp(h, vector<bool>(w));
    vector<vector<bool>> block(h, vector<bool>(w));
    rep(i, n) {
        int a, b;
        cin >> a >> b;
        lamp[--a][--b] = true;
    }
    rep(i, m) {
        int c, d;
        cin >> c >> d;
        block[--c][--d] = true;
    }

    vector<vector<bool>> ok(h, vector<bool>(w));
    rep(i, h) {
        rep(j, w) {
            if (lamp[i][j]) {
                int k = j;
                for (; k >= 0 && !block[i][k]; k--) {
                    ok[i][k] = 1;
                }
                k = j;
                for (; k < w && !block[i][k]; k++) {
                    ok[i][k] = 1;
                }
                j = k;
            }
        }
    }
    rep(j, w) {
        rep(i, h) {
            if (lamp[i][j]) {
                int k = i;
                for (; k >= 0 && !block[k][j]; k--) {
                    ok[k][j] = 1;
                }
                k = i;
                for (; k < h && !block[k][j]; k++) {
                    ok[k][j] = 1;
                }
                i = k;
            }
        }
    }
    int ans = 0;
    rep(i, h) rep(j, w) ans += ok[i][j];
    cout << ans << '\n';
}

F - Valid payments

問題：（リンク）
タイトルと設定みた段階ですでに苦手意識が止まらん。お金払う系、解けたためしがない（ Payment, Pay to Win ）。

「ルンルンが店員に渡したコインのいずれかと同じ種類のコインが店員から返されることはありませんでした。」という条件から、 $N$ 種類のコインそれぞれについて（基本的には）店員が使うかルンルンが使うかの二択になる（どっちも使わない、もありだけど）。二択を繰り返す問題は DP、と歴史の教科書に書いてあるので、DP！！！
コンテスト終了には間に合わなかったけどなんとか解けて嬉しい。

コードを表示

#include <bits/stdc++.h>
#define rep(i, n) for (int i = 0; i < (int)(n); i++)
using namespace std;
using ll = long long;
int main() {
    int n;
    ll x;
    cin >> n >> x;
    vector<ll> a(n);
    rep(i, n) cin >> a[i];

    auto f = [&](ll num, int i) {
        for (int j = n - 1; j > i; j--) num %= a[j];
        return num / a[i];
    };

    using P = pair<ll, int>;
    map<P, ll> memo;
    auto dp = [&](auto dp, ll num, int i) -> ll {
        if (i >= n) return 0;
        if (i == n - 1) return 1;
        if (memo.count(P(num, i))) return memo[P(num, i)];

        ll ret = 0;
        ll nnum = num / a[i + 1] * a[i + 1];

        ret += dp(dp, nnum, i + 1);
        if (f(num, i) > 0) ret += dp(dp, nnum + a[i + 1], i + 1);

        return memo[P(num, i)] = ret;
    };
    cout << dp(dp, x, 0) << '\n';
}

おわり

Highest まであと14
黄色まであと178

2020-11-07

ICPC2020国内予選に参加しました

チーム紹介

gyouzasushi(僕), ndifix, taizou のチーム「TOYONAKAISER」で出ました。二人とも中学からの友人。こういうのは「仲良い人とやった方が良い！」って麗日お茶子ちゃんも言うてたからね。

結果

f:id:gyouzasushi:20201107051903p:plain
ABCD4完で学内6位でした。4完できたら嬉しいね、みたいな話をしていたので、嬉しい！通過はできませんでしたが、来年も頑張ろう、と思えるぐらいには健闘できたと思うのでよかったです。二人ともありがとう！

朝

僕の家に集合して、2012年の国内予選で最後の練習をしてた。Eの鎖中経路がリハーサルのL問題（確か）にも出てて、半日で二回ACする男になってもうた。

昼

ウーバーイーツで頼んだハンバーグをみんなで食べた。戦いの前の食事はやっぱり肉に限るよ。そのあと僕はたいへん眠たかったので始まるまでお昼寝をすることにした。僕が寝てるあいだ二人はマリオカートしてたらしい。良い雰囲気だ

本番

練習どおり、ndifixがA問題、僕がB問題を解いて、TOYONAKAISER注意力担当のtaizouにC以降を読解していてもらう。AとBの実装がほぼ同じタイミングで終わっていざ提出、というところでWorkspaceに入れなくなって焦る。BANされた？とかひととおり大騒ぎしたけど、taizouが落ち着いていてくれたおかげでギリ冷静でいられた。七年半の付き合いで一番ぐらい尊敬したね、ありがとう…。
Bを提出→AC(2:26)、続けてAもAC(3:45)。
Cがすぐ書けそうでDが構文解析とのことだったので、二人にCを任せてDを考える。とりあえず順序が決まれば構文解析パートはそんなに難しくないな、でも $n!$ 通り全部は調べられないな……と思って途方に暮れてしまう。かなり泣きたい。泣いてるあいだにndifixがCをACしてくれた(42:10)神。
一旦休憩を挟んで落ち着いて考えてみると、こんなん $n!$ を $2^n$ に落とすやつしかないやろ、という気持ちになる。順列じゃなくて集合、集合、集合……という気持ちでもう一度考察すると、「 $X$ より先に来る文字の集合」を決定すれば「式の値が $X$ になるかどうか」を判定できることに気づいた！！！さすが僕。ここまでわかればあとは $X$ と各文字が $X$ より先に来るか後に来るかを全部試して適当な係数をかければ答えが得られる。もろたで工藤
実装もそんなに複雑じゃない、はずなのに、サンプルが全然合わない、終わった……と思っていたら、アルファベットを整数に直すところで 'A' ではなく 'a' を引いていた。しかも $\neq$ とするべきところが全部 $=$ になっていて、綺麗に余事象の場合の数が出力されていた。全部直して提出→AC(1:51:44)。考察も実装もかなり時間がかかってしまったけれど、これは実力不足だなあ〜〜。
残り一時間。二人がずっとEを考えてくれていたが、厳しいらしい。順位表をみるとEとFが同じぐらい通されていたのでFも読む。
Eは地道に詰めていけばいつかは解けそうな感じで、Fは何かひらめきさえすれば解けそうな感じ？みたいな話をした。相談の結果、残り時間のことも考えてFに賭けることになった。
Dを通したことでどこか満足してしまった気持ち、Eを諦めきれない気持ち、Fの手がかりが見えずに辛い気持ちのトリプルパンチでなかなか集中できず、競プロがメンタルスポーツであることを実感……。終盤taizouがよさげな解法を持ってきてくれたものの間に合わず、コンテスト終了。

夜

めっちゃ寝た。

さいごに

Asia　遠そうで近そうで遠いなあ。

2020-10-27

今日の競プロ(2020/10/26)

久しぶりに書く。寝れへん

AOJ-2883 知識の証明(350点)

リンク
問題概要：4 桁のパスワード "0000" から "9999" それぞれに対し、以下のBNFで定義されるハッシュ関数<Hash>から得られるハッシュ値を計算せよ。但し、 'a', 'b', 'c', 'd' はそれぞれ 4 桁のパスワードの先頭から 1 桁目，2 桁目，3 桁目，4 桁目の数字を表し、演算子 '+', '*', '^' はそれぞれ bitwise or, bitwise and, bitwise xor を表す。

<Hash> ::= <Letter> | '['<Op> <Hash> <Hash>']' 
<Op> ::= '+' | '*' | '^' 
<Letter> ::= 'a' | 'b' | 'c' | 'd'

構文解析　ずっとどうしていいかわからんくて怪しい再帰でなんとかしてたけど、これ構文解析 Howto · GitHub読んでからだいぶわかってきた。ありがとうございます。この問題は考えること少なめで優しいね。

コードを表示

#include <bits/stdc++.h>
using namespace std;
using state = string::const_iterator;
int Letter(state &begin) {
    int ret = *begin - '0';
    begin++;
    return ret;
}
int Hash(state &begin) {
    if (*begin == '[') {
        begin++;
        char op = *begin;
        begin++;
        int lhs = Hash(begin);
        int rhs = Hash(begin);
        begin++;
        if (op == '+') {
            return lhs | rhs;
        }
        if (op == '*') {
            return lhs & rhs;
        }
        if (op == '^') {
            return lhs ^ rhs;
        }
    }
    return Letter(begin);
}
int main() {
    while (1) {
        string s;
        int p;
        cin >> s;
        if (s == ".") break;
        cin >> p;
        vector<int> cnt(16);
        int ans = 0;
        for (int i = 0; i <= 9999; i++) {
            string t = to_string(i);
            while (t.size() < 4) t = "0" + t;
            string ss = s;
            for (char &c : ss) {
                if (c == 'a') c = t[0];
                if (c == 'b') c = t[1];
                if (c == 'c') c = t[2];
                if (c == 'd') c = t[3];
            }
            state begin = ss.begin();
            int hs = Hash(begin);
            if (i == p) ans = hs;
            cnt[hs]++;
        }
        cout << ans << ' ' << cnt[ans] << '\n';
    }
}

AOJ-2608 Minus One(350点)

リンク
問題概要： $N$ 頂点 $M$ 辺の無向グラフ $G$ とふたつの頂点 $s,t$ が与えられる。 $G$ の異なる頂点 $(u,v)$ の組であって、 $G$ に辺 $(u,v)$ を追加したグラフにおける $s$ から $t$ への最短経路長が、 $G$ における $s$ から $t$ への最短経路長よりもちょうど $1$ 短くなるようなものはいくつか？

制約： $N \leq 10^5,M \leq 3\times 10^5$

$G$ における頂点 $i$ から頂点 $j$ への最短経路長を $dist_{i,j}$ と表すことにする。このとき、求めるべきは $dist_{s,u}+1+dist_{v,t}=dist_{s,t}$ を満たすような $(u,v)$ の組の総数で、これは $dist_{s,i}, dist_{t,i}$ のヒストグラムを作っておけば高速に求まる。

コードを表示

#include <bits/stdc++.h>
using namespace std;
int main() {
    int n, m, s, t;
    cin >> n >> m >> s >> t;
    s--, t--;
    vector<vector<int>> g(n);
    while (m--) {
        int x, y;
        cin >> x >> y;
        x--, y--;
        g[x].push_back(y);
        g[y].push_back(x);
    }
    auto d = [&](int s) {
        vector<int> ret(n, -1);
        queue<int> q;
        ret[s] = 0;
        q.push(s);
        while (!q.empty()) {
            int pos = q.front();
            q.pop();
            for (int nxt : g[pos]) {
                if (~ret[nxt]) continue;
                ret[nxt] = ret[pos] + 1;
                q.push(nxt);
            }
        }
        return ret;
    };
    using ll = long long;
    auto ds = d(s);
    auto dt = d(t);
    vector<ll> cnts(n), cntt(n);
    for (int i = 0; i < n; i++) {
        if (~ds[i]) cnts[ds[i]]++;
        if (~dt[i]) cntt[dt[i]]++;
    }
    ll ans = 0;
    int SUM = ds[t] - 2;
    for (int i = 0; i < n; i++) {
        if (SUM - i >= 0) ans += cnts[i] * cntt[SUM - i];
    }
    cout << ans << '\n';
}

AOJ-2426 宝探し(350点)

リンク
問題概要： $n$ 個のお宝があり、 $i$ 個目のお宝は座標 $(x_i,y_i)$ に埋まっている。「長方形領域 $x_1 \leq x \leq x_2, y_1\leq y \leq y2$ に埋まっているお宝は全部でいくつか？」という形式のクエリ $m$ 個を処理せよ。

制約： $n \leq 5000,m \leq 5\times 10^5,|x|\leq10^9,|y|\leq10^9$

座標圧縮＋二次元累積和。かなりやりたくなかったけど、この程度で音をあげとったらICPCは戦えへんのやろなあ、と思ってがんばったよ。

コードを表示

#include <bits/stdc++.h>
using namespace std;
int main() {
    int n, m;
    cin >> n >> m;
    vector<pair<int, int>> p(n);
    vector<int> xs(n), ys(n);
    for (int i = 0; i < n; i++) {
        int x, y;
        cin >> x >> y;
        xs[i] = x;
        ys[i] = y;
        p[i] = make_pair(x, y);
    }
    sort(xs.begin(), xs.end());
    xs.erase(unique(xs.begin(), xs.end()), xs.end());
    sort(ys.begin(), ys.end());
    ys.erase(unique(ys.begin(), ys.end()), ys.end());

    vector<vector<int>> v(n + 2, vector<int>(n + 2));
    for (auto &[x, y] : p) {
        x = lower_bound(xs.begin(), xs.end(), x) - xs.begin() + 1;
        y = lower_bound(ys.begin(), ys.end(), y) - ys.begin() + 1;
        v[y][x]++;
    }

    for (int i = 0; i < n + 1; i++) {
        for (int j = 0; j < n + 1; j++) {
            v[i + 1][j + 1] += v[i + 1][j] + v[i][j + 1] - v[i][j];
        }
    }

    for (int i = 0; i < m; i++) {
        int x1, y1, x2, y2;
        cin >> x1 >> y1 >> x2 >> y2;
        x1 = lower_bound(xs.begin(), xs.end(), x1) - xs.begin();
        y1 = lower_bound(ys.begin(), ys.end(), y1) - ys.begin();
        x2 = upper_bound(xs.begin(), xs.end(), x2) - xs.begin();
        y2 = upper_bound(ys.begin(), ys.end(), y2) - ys.begin();
        cout << v[y2][x2] - v[y2][x1] - v[y1][x2] + v[y1][x1] << '\n';
    }
}

AOJ-2613 Unordered Operators(350点)

リンク
問題概要：以下のBNFで示される形式の数式が与えられる。演算子 '+', '-', '*' の優先順位を適切に定めたときの、数式の計算結果の最大値を求めよ。

<expr> ::= ( <expr> ) | <number> | <expr> <op> <expr>
<op> ::= + | - | *
<number> は非負整数を表す。

優先順位を全部試す。括弧付きの四則演算のときとほぼ一緒で、演算子のとこだけちょっと抽象化すればいける。

コードを表示

#include <bits/stdc++.h>
using namespace std;
using state = string::const_iterator;
using ll = long long;
const ll LINF = (((1ll << 62) - 1) << 1) + 1;
string ops1, ops2, ops3;
ll expr(state &begin);
ll number(state &begin) {
    ll ret = 0;
    while (isdigit(*begin)) {
        ret *= 10;
        ret += *begin - '0';
        begin++;
    }
    return ret;
}
ll factor(state &begin) {
    if (*begin == '(') {
        begin++;
        ll ret = expr(begin);
        begin++;
        return ret;
    }
    return number(begin);
}
ll term1(state &begin) {
    ll ret = factor(begin);
    while (1) {
        if (!count(ops1.begin(), ops1.end(), *begin)) break;
        if (*begin == '*') {
            begin++;
            ret *= factor(begin);
        } else if (*begin == '+') {
            begin++;
            ret += factor(begin);
        } else if (*begin == '-') {
            begin++;
            ret -= factor(begin);
        }
    }
    return ret;
}
ll term2(state &begin) {
    ll ret = term1(begin);
    while (1) {
        if (!count(ops2.begin(), ops2.end(), *begin)) break;
        if (*begin == '*') {
            begin++;
            ret *= term1(begin);
        } else if (*begin == '+') {
            begin++;
            ret += term1(begin);
        } else if (*begin == '-') {
            begin++;
            ret -= term1(begin);
        }
    }
    return ret;
}
ll expr(state &begin) {
    ll ret = term2(begin);
    while (1) {
        if (!count(ops3.begin(), ops3.end(), *begin)) break;
        if (*begin == '*') {
            begin++;
            ret *= term2(begin);
        } else if (*begin == '+') {
            begin++;
            ret += term2(begin);
        } else if (*begin == '-') {
            begin++;
            ret -= term2(begin);
        }
    }
    return ret;
}
int main() {
    string s;
    cin >> s;
    ll ans = -LINF;
    string ops = "+-*";
    sort(ops.begin(), ops.end());
    do {
        for (int l = 0; l <= 3; l++) {
            for (int m = 0; l + m <= 3; m++) {
                int r = 3 - l - m;
                ops1 = ops.substr(0, l);
                ops2 = ops.substr(l, m);
                ops3 = ops.substr(l + m, r);
                state begin = s.begin();
                ans = max(ans, expr(begin));
            }
        }
    } while (next_permutation(ops.begin(), ops.end()));
    cout << ans << '\n';
}

AOJ-2601 Evacuation Route(350点)

リンク
問題概要： $W$ 個のユニットに分けられた通路がある。ユニットには、以下の三種類が存在する。

入り口：時刻 $t=0,1,\ldots,a_i-1$ のそれぞれにおいてちょうど一人の人が現れる。時刻 $t$ にユニット $i$ にいる人は、時刻 $t+1$ にはユニット $i-1,i,i+1$ のいずれかに移動できる。時刻 $t$ に現れた人は、時刻 $t+1$ 以降から移動を開始する。

出口：出口。

防火扉：時刻 $|a_i|$ 以降、遮断されてしまう。

出口にたどり着くことができる人は最大で何人か？
制約： $W\leq 10^5,|a_i| \leq 10^4$

人々が目指すのは、左右どちらか一方の最寄りの出口であると考えてよい。よって、各入り口について「左側の最寄り出口にたどり着くことができるのは最大何人か？」「右側の最寄り出口にたどり着くことができるのは最大何人か？」をそれぞれ計算できれば解けて、これは index をガチャガチャやってると RangeMinimumQuery で処理できることがわかる。セグ木。

ACLのやつを写経してみたけど意外としんどくなかった。本番も　迷うくらいなら書いちゃえ！w　ぐらいでいいんかもね。

コードを表示

#include <bits/stdc++.h>
using namespace std;
const int INF = 1'000'000'000;
template <class S, S (*op)(S, S), S (*e)()>
struct SegmentTree {
public:
    SegmentTree(const vector<S>& v) : _n(int(v.size())) {
        log = ceil_pow2(_n);
        size = 1 << log;
        d = vector<S>(2 * size, e());
        for (int i = 0; i < _n; i++) d[size + i] = v[i];
        for (int i = size - 1; i >= 1; i--) {
            update(i);
        }
    }
    void set(int p, S x) {
        p += size;
        d[p] = x;
        for (int i = 1; i <= log; i++) update(p >> i);
    }
    S get(int p) {
        return d[p + size];
    }
    S prod(int l, int r) {
        S sml = e(), smr = e();
        l += size;
        r += size;
        while (l < r) {
            if (l & 1) sml = op(sml, d[l++]);
            if (r & 1) smr = op(d[--r], smr);
            l >>= 1;
            r >>= 1;
        }
        return op(sml, smr);
    }

private:
    int _n, size, log;
    vector<S> d;
    int ceil_pow2(int n) {
        int x = 0;
        while ((1U << x) < (unsigned int)(n)) x++;
        return x;
    }
    void update(int k) {
        d[k] = op(d[2 * k], d[2 * k + 1]);
    }
};
using S = int;
S op(S a, S b) {
    return min(a, b);
}
S e() {
    return INF;
}
int main() {
    int w;
    cin >> w;
    vector<int> a(w), ex = {-INF, INF};
    for (int i = 0; i < w; i++) {
        cin >> a[i];
        if (a[i] == 0) ex.push_back(i);
    }
    sort(ex.begin(), ex.end());

    vector<int> ans(w, 0);
    {
        vector<int> seg(w, INF);
        for (int i = 0; i < w; i++) {
            if (a[i] < 0) seg[i] = -a[i] - i;
        }
        SegmentTree<S, op, e> segt(seg);
        for (int i = 0; i < w; i++) {
            if (a[i] <= 0) continue;
            int r = *lower_bound(ex.begin(), ex.end(), i);
            if (r == INF) continue;
            int MIN = segt.prod(i, r) + i;
            ans[i] = max(ans[i], min(a[i], MIN));
        }
    }
    {
        vector<int> seg(w, INF);
        for (int i = 0; i < w; i++) {
            if (a[i] < 0) seg[i] = -a[i] - (w - 1 - i);
        }
        SegmentTree<S, op, e> segt(seg);
        for (int i = 0; i < w; i++) {
            if (a[i] <= 0) continue;
            int l = *(--lower_bound(ex.begin(), ex.end(), i)) + 1;
            if (l < 0) continue;
            int MIN = segt.prod(l, i) + (w - 1 - i);
            ans[i] = max(ans[i], min(a[i], MIN));
        }
    }
    cout << accumulate(ans.begin(), ans.end(), 0) << '\n';
}

AOJ-1132 Circle and Points(450点)

リンク
問題概要：座標平面上に $N$ 個の点がある。半径 $1$ の円を自由に動かすとき、円の周または内部にある点の個数の最大値を求めよ。
制約： $N\leq 300$

円が二つの点を含むとき、その点が周上にくるように円を動かしても損しない。こうすると注目している二点に対して円の候補が二つ（こっち側かあっち側か）に絞られるので、あとはその二点の選び方を全探索すればOK（そのような二点が選べない場合は $1$ が答え）。

コードを表示

#include <bits/stdc++.h>
using namespace std;
const double PI = acos(-1);
const double EPS = 1e-9;
int sgn(double a) {
    return (a < -EPS) ? -1 : (a > EPS) ? 1 : 0;
};
struct Point {
    double x, y;
    Point(double _x, double _y) : x(_x), y(_y) {
    }
    Point operator+(const Point &rhs) {
        Point res(*this);
        return res += rhs;
    }
    Point operator-(const Point &rhs) {
        Point res(*this);
        return res -= rhs;
    }
    Point operator*(const double &rhs) {
        Point res(*this);
        return res *= rhs;
    }
    Point operator/(const double &rhs) {
        Point res(*this);
        return res /= rhs;
    }
    inline bool operator<(const Point &b) {
        if (sgn(x - b.x)) return sgn(x - b.x) < 0;
        return sgn(y - b.y) < 0;
    }
    Point operator+=(const Point &rhs) {
        x += rhs.x, y += rhs.y;
        return *this;
    }
    Point operator-=(const Point &rhs) {
        x -= rhs.x, y -= rhs.y;
        return *this;
    }
    Point operator*=(const double &rhs) {
        x *= rhs, y *= rhs;
        return *this;
    }
    Point operator/=(const double &rhs) {
        x /= rhs, y /= rhs;
        return *this;
    }
    Point rotate(const double &theta) {
        double px = x, py = y;
        x = px * cos(theta) - py * sin(theta);
        y = px * sin(theta) + py * cos(theta);
        return *this;
    }
    double abs() {
        return sqrt(x * x + y * y);
    }
    double dot(const Point &rhs) {
        return x * rhs.x + y * rhs.y;
    }
    double det(const Point &rhs) {
        return x * rhs.y - y * rhs.x;
    }
    double arg() {
        return atan2(y, x);
    }
};
inline bool operator<(const Point &a, const Point &b) {
    if (sgn(a.x - b.x)) return sgn(a.x - b.x) < 0;
    return sgn(a.y - b.y) < 0;
}
ostream &operator<<(ostream &os, Point &p) {
    return os << fixed << setprecision(10) << p.x << ' ' << p.y;
}
int main() {
    while (1) {
        int n;
        cin >> n;
        if (n == 0) break;
        vector<Point> p;
        for (int i = 0; i < n; i++) {
            double x, y;
            cin >> x >> y;
            p.emplace_back(x, y);
        }
        int ans = 1;
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < i; j++) {
                Point c = (p[i] + p[j]) / 2;
                Point v = p[i] - p[j];
                if (sgn(v.abs() - 2) > 0) continue;
                Point w = Point(-(v.y), v.x);
                w *= sqrt(1.0 - (v / 2).abs() * (v / 2).abs()) / w.abs();
                for (Point o : {c + w, c - w}) {
                    int cnt = 0;
                    for (int k = 0; k < n; k++) {
                        if (sgn((p[k] - o).abs() - 1) <= 0) cnt++;
                    }
                    ans = max(ans, cnt);
                }
            }
        }
        cout << ans << '\n';
    }
}

AOJ-1140 Cleaning Robot(450点)

リンク
問題概要： $h\times w$ のタイルがある。それぞれのタイルはきれいか、汚れているか、障害物が置かれているである。お掃除ロボットは初期位置を出発し、汚れているタイルを全て掃除してまわりたい。このとき、ロボットの最小移動回数を求めよ。
制約： $w,h\leq 20,$ 汚れているタイルは $10$ 個以下

初期位置と汚れているタイルの全点対最短経路長を求めておいて、bitDP。

コードを表示

#include <bits/stdc++.h>
#define rep(i, x) for (int i = 0; i < (int)(x); i++)
using namespace std;
const int INF = 1'000'000'000;
const vector<int> dx = {0, 1, 0, -1};
const vector<int> dy = {1, 0, -1, 0};
int main() {
    while (1) {
        int w, h;
        cin >> w >> h;
        if (w == 0) return 0;
        vector<string> v(h, string(w, '.'));
        vector<int> ys, xs;
        rep(i, h) rep(j, w) {
            cin >> v[i][j];
            if (v[i][j] == 'o') {
                ys.push_back(i);
                xs.push_back(j);
            }
        }
        rep(i, h) rep(j, w) {
            if (v[i][j] == '*') {
                ys.push_back(i);
                xs.push_back(j);
            }
        }
        int n = int(xs.size());
        vector<vector<int>> d(n, vector<int>(n));
        bool ok = 1;
        rep(i, n) {
            vector<vector<int>> dd(h, vector<int>(w, INF));
            queue<pair<int, int>> q;
            dd[ys[i]][xs[i]] = 0;
            q.emplace(ys[i], xs[i]);
            while (!q.empty()) {
                auto [y, x] = q.front();
                q.pop();
                rep(j, 4) {
                    int ny = y + dy[j], nx = x + dx[j];
                    if (!(0 <= ny && ny < h && 0 <= nx && nx < w)) continue;
                    if (dd[ny][nx] != INF) continue;
                    if (v[ny][nx] == 'x') continue;
                    dd[ny][nx] = dd[y][x] + 1;
                    q.emplace(ny, nx);
                }
            }
            rep(j, n) {
                d[i][j] = dd[ys[j]][xs[j]];
            }
        }

        vector<vector<int>> dp(1 << n, vector<int>(n, INF));
        dp[1][0] = 0;
        rep(bit, 1 << n) {
            rep(pos, n) if (bit >> pos & 1) {
                rep(nxt, n) if (~bit >> nxt & 1) {
                    int nbit = bit | (1 << nxt);
                    dp[nbit][nxt] =
                        min(dp[nbit][nxt], dp[bit][pos] + d[pos][nxt]);
                }
            }
        }
        int ans =
            *min_element(dp[(1 << n) - 1].begin(), dp[(1 << n) - 1].end());
        cout << (ans == INF ? -1 : ans) << '\n';
    }
}

完

2020-10-25

AtCoder Regular Contest 106 に参加しました。

atcoder.jp

成績

f:id:gyouzasushi:20201025033527p:plain
f:id:gyouzasushi:20201025033941p:plain

A - 106

問題概要： $3^A+5^B=N$ を満たす正の整数の組 $(A,B)$ を一組求めよ（存在しなければ $-1$ を出力）。
制約： $N \leq 10^{18}$
こういうやつは変に数学せずに全探索した方がいいって歴史の教科書に書いてました。オーバーフローに気を使いたくないので雑に Python でやる。

f:id:gyouzasushi:20201025015743p:plain — ゼロは正の整数ではありません（一敗）

コードを表示

n = int(input())
for a in range(1,40):
    for b in range(1,30):
        if 3 ** a + 5 ** b == n:
            print(a, b)
            exit()
print(-1)

B - Values

問題概要： $N$ 頂点 $M$ 辺の単純無向グラフがあり、頂点 $i$ には値 $a_i$ が書かれている。次の操作を適切に行うことで、操作後の各頂点の値を $b_1, \cdots ,b_N$ にできるか？

（操作）辺を一つ選ぶ。選んだ辺が頂点 $x$ と頂点 $y$ を結んでいるとき、次のいずれかを行う。

・値 $a_x$ を $-1$ し、値 $a_y$ を $+1$ する。

・値 $a_x$ を $+1$ し、値 $a_y$ を $-1$ する。

制約： $N,M \leq 2 \times 10^5, -10^9 \leq a_i,b_i \leq 10^9$

どちらの操作を選んでも $\sum a$ は不変なので、「連結成分ごとに $\sum a = \sum b$ 」が必要。そしてこれは実は十分条件にもなってると思う。違ったらそのときにまた考えればいいかな……の気持ちで提出してもうた。Aでいきなりペナルティつけて焦ってたね。ACしたのでヨシ！

コードを表示

#include <bits/stdc++.h>
#define rep(i, n) for (int i = 0; i < (int)(n); i++)
#define sz(x) int(x.size())
using namespace std;
using ll = long long;
struct UnionFind {
    vector<int> data;
    UnionFind(int size) : data(size, -1) {
    }
    int root(int x) {
        return (data[x] < 0) ? x : data[x] = root(data[x]);
    }
    bool unite(int x, int y) {
        x = root(x);
        y = root(y);
        if (x != y) {
            if (data[y] < data[x]) swap(x, y);
            data[x] += data[y];
            data[y] = x;
        }
        return x != y;
    }
    bool find(int x, int y) {
        return root(x) == root(y);
    }
    int size(int x) {
        return -data[root(x)];
    }
};
int main() {
    int n, m;
    cin >> n >> m;
    vector<ll> a(n), b(n);
    rep(i, n) cin >> a[i];
    rep(i, n) cin >> b[i];
    UnionFind uf(n);
    while (m--) {
        int c, d;
        cin >> c >> d;
        uf.unite(--c, --d);
    }
    vector<ll> aa(n), bb(n);
    rep(i, n) {
        aa[uf.root(i)] += a[i];
        bb[uf.root(i)] += b[i];
    }
    cout << (aa == bb ? "Yes\n" : "No\n");
}

C - Solutions

問題 & 制約：（リンク）

$M$ の符号で場合分けしたい気持ちになる。

( $M \lt 0$ のとき) 高橋くんのアルゴリズムは正解なので、青木くんの方が大きい値を出力することはないです。 $-1$ 。

( $M=0$ のとき) $[1,2], [3,4],\cdots, [2N-1,2N]$ みたいにすれば二人とも $N$ を出力して平和。

( $M \gt 0$ のとき) $[1,\infty]$ みたいな区間を作ることで、青木くんの値を $1$ に抑えることができる。あとは高橋くんが丁度 $M+1$ 個の区間を選ぶことになるように調節（できなければ $-1$ ）。

コードを表示

#include <bits/stdc++.h>
using namespace std;
const int INF = 1e8;
int main() {
    int n, m;
    cin >> n >> m;
    if (m < 0) {
        cout << -1 << '\n';
        return 0;
    }
    if (m == 0) {
        for (int i = 1; i <= n; i++) {
            cout << 2 * i << ' ' << 2 * i + 1 << '\n';
        }
        return 0;
    }
    if (m > 0) {
        if (m >= n - 1) {
            cout << -1 << '\n';
            return 0;
        }
        for (int l = 1; l <= n - m - 1; l++) {
            cout << l << ' ' << l + INF << '\n';
        }
        for (int i = 1; i <= m + 1; i++) {
            int l = n - m - 1 + 2 * i;
            int r = l + 1;
            cout << l << ' ' << r << '\n';
        }
        return 0;
    }
}

D - Powers

問題概要：整数列 $A=(A_1,A_2,\cdots,A_N)$ と整数 $K$ が与えられる。 $1\leq X \leq K$ を満たす整数 $X$ それぞれについて、 $\displaystyle \sum_{L=1}^{N-1} \sum_{R=L+1}^{N} (A_L+A_R)^X$ の値を $\mod 998244353$ で求めよ。

制約： $2\leq N \leq 2\times 10^5, 1\leq K\leq 300, 1\leq A_i\leq 10^8$

$1\leq i \lt j \leq N$ の和をとるときには、まず $1\leq i , j\leq N$ について求めてから $i=j$ を引いて $2$ で割る、って歴史の教科書に書いてました。本問でいうと、求めるべきは $\displaystyle \sum_{i=1}^{N} \sum_{j=1}^{N} (A_i+A_j)^X$ と $\displaystyle \sum_{i}^{N} (A_i+A_i)^X$ 。後者はすぐ求まりそうなので前者を考えよう。ゴリゴリ展開していく。 \begin{eqnarray}　\displaystyle \sum_{i=1}^{N} \sum_{j=1}^{N} (A_i+A_j)^X &=& \sum_{i=1}^{N} (\sum_{j=1}^{N} \sum_{k=0}^{X} ({}_{N} C_{k} {A_j}^{X-k} \times {A_i}^k)) \\ &=& \sum_{i=1}^{N} (\sum_{k=0}^{X} ({}_{N} C_{k} \sum_{j=1}^{N} {A_j}^{X-k}) \times {A_i}^k) \\ &=&\sum_{k=0}^{X} ({}_{N} C_{k} \times (\sum_{j=1}^{N} {A_j}^{X-k}) \times(\sum_{i=1}^{N} {A_i}^k)) \\ \end{eqnarray} $\sum A^k=f(k)$ とすると \begin{eqnarray}　\displaystyle \sum_{i=1}^{N} \sum_{j=1}^{N} (A_i+A_j)^X &=&\sum_{k=0}^{X} ({}_{N} C_{k} \times f(X-k) \times f(k)) \\ \end{eqnarray} で、やっと計算できそうな見た目になってくれた😭 式変形で疲れ切ってもうて実装かなり時間かかった…… f:id:gyouzasushi:20201025032054p:plain

残り一分とちょっとのところでAC。めっちゃ気持ちいい、これだからやめられないんですよね。安心しすぎて変な呼吸はいった。

コードを表示

#include <bits/stdc++.h>
#include <atcoder/modint>
#define rep(i, n) for (int i = 0; i < (int)(n); i++)
using namespace std;
using mint = atcoder::modint998244353;
int main() {
    const int N = 200200;
    vector<mint> fact(N + 1), ifact(N + 1);
    fact[0] = 1;
    for (int i = 1; i <= N; i++) {
        fact[i] = fact[i - 1] * i;
    }
    ifact[N] = fact[N].inv();
    for (int i = N; i >= 1; i--) {
        ifact[i - 1] = ifact[i] * i;
    }
    auto comb = [&](int n, int r) {
        if (n < r || r < 0) return mint(0);
        return fact[n] * ifact[r] * ifact[n - r];
    };

    int n, k;
    cin >> n >> k;
    vector<mint> a(n);
    vector<mint> f(k + 1);
    f[0] = mint(n);
    rep(i, n) {
        int x;
        cin >> x;
        a[i] = mint(x);
        f[1] += a[i];
    }

    auto b = a;
    for (int i = 2; i <= k; i++) {
        rep(j, n) {
            f[i] += b[j] * a[j];
            b[j] *= a[j];
        }
    }
    for (int x = 1; x <= k; x++) {
        mint ans = 0;
        for (int i = 0; i <= x; i++) {
            ans += comb(x, i) * f[i] * f[x - i];
        }
        ans -= mint(2).pow(x) * f[x];
        ans /= 2;
        cout << ans.val() << '\n';
    }
}

E - Medals, F - Figures

todo

ところで

今年も残すところあと二ヶ月！w GPAはなんか3ぐらいしかないです。オワオワリ

2020-05-10

AtCoder Beginner Contest 167 に参加しました

成績

f:id:gyouzasushi:20200510232837p:plain

1級！

A - Registration

問題

ちょっと難しめ？ T.substr(0, |S|) == S かどうか。

提出

B - Easy Linear Programming

問題

書かれてる数が大きい方から $K$ 枚使う。

提出

C - Skill Up

問題

$N$ がめっちゃ小さいので、 $N$ 冊の本を買う / 買わないの $2^N$ 通りを全部試せる。

提出

D - Teleporter

問題

競技コピーアンドペースト…

atcoder.jp

提出

E - Colorful Blocks

問題

これ好き。「隣り合うブロックの組であって同じ色で塗られている組」が $i$ 組になるような塗り方はこんな感じで作れる：

初めから色が塗られたブロックを用意する
$N-i$ 個のブロックを同じ色が隣合わないように並べる
（ブロックの総数が $N$ 個になるように）いくつかのブロックを合計 $i$ 回砕く

なので、各 $i \leq K$ に対して

ブロックの並べ方　 $M \times (M-1)^{N-i-1}$ 通り
砕くブロックの選び方　 ${}_{N-i} H_{i}$ 通り

をかけたものを足し上げればOK。

提出

F - Bracket Sequencing

問題

文字列 $T$ が括弧列であるための条件は

「' ( ' の数　＝　' ) ' の数」になること
前から見ていったときに、「' ( ' の数　<　' ) ' の数」となる瞬間がないこと

よって、各 $S_i$ について興味があるのは

' ( ' の数　-　' ) 'の数（ $cnt_i$ とする）
前から見ていったときの「' ( ' の数　-　' ) 'の数」の最小値（ $min_i$ とする）

だけ。 $\sum cnt_i \neq 0$ のときは明らかに"No"なのでそれ以外の場合を考えればいい。

直前までの「' ( ' の数　-　' ) 'の数」が $x$ のとき、次に $S_i,S_j$ の順で連結する場合と $S_j,S_i$ の順で連結する場合とを比べてみる。前者がアウトにならない条件は、 $x+min_i \geq 0$ かつ $x+cnt_i+min_j \geq 0$ 、つまり $x \geq max(-min_i,-cnt_i-min_j)$ 。同様に、後者がアウトにならない条件は $x \geq max(-min_j,-cnt_j-min_i)$ 。よって、 $max(-min_i,-cnt_i-min_j) \lt max(-min_j,-cnt_j-min_i)$ なら $S_i$ を前に、そうでなければ $S_j$ を前に持ってきた方がお得。