hotaruの蛍雪日記

競プロとゲームをしています

ABC185に参加しました

ABCDFの5完で水パフォーマンス。

  • Eは解いたことあるのに解けなかった。
  • BDに時間掛けすぎ。Bは10分1ペナ、Dは15分1ペナ。

f:id:hotarunx:20201214120359j:plain
ranking
f:id:hotarunx:20201214120403j:plain
mysubmission

目次

A ABC Preparation

1:02 AC Difficulty: 7 問題へのリンク 自分の提出へのリンク

min。algorithmのstd::minはこう使える。

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

int main() {
    int a, b, c, d;
    cin >> a >> b >> c >> d;
    cout << min({a, b, c, d}) << "\n";
}

B Smartphone Addiction

11:26 AC (1) Difficulty: 93 問題へのリンク 自分の提出へのリンク

やるだけ。 nmを書き間違えたり残量が0でもいいと誤読して10分掛けてしまった。

C Duodecim Ferra

16:15 AC Difficulty: 374 問題へのリンク 自分の提出へのリンク

\binom{l-1}{11}これ使った。

D Stamp

39:46 AC (1) Difficulty: 490 問題へのリンク 自分の提出へのリンク

各青マス🟦同士、青マス🟦と端に挟まれた白マスの数をWとおく。 ただし、白マスの数が0ならWには入れない。 入力例1ならば W = 1,2k = \min(W) W_i \lceil \frac{W_i}{k} \rceil回で赤マス🟥に塗れる。 答えは \sum_i \lceil \frac{W_i}{k} \rceil

Wを計算するときにAはソートされていないといけないのでソートする。

k = \gcd(W)と誤答してしまった。

#include <algorithm>
#include <array>
#include <iostream>
#include <map>
#include <numeric>
#include <queue>
#include <set>
#include <stack>
#include <vector>
using namespace std;
#define int long long

constexpr int ceil(long long a, long long b) { return (a + b - 1) / b; }

signed main() {
    cin.tie(0);
    ios::sync_with_stdio(0);

    int n, m;
    cin >> n >> m;

    if (m == 0) {
        cout << 1 << "\n";
        return 0;
    }

    vector<int> a(m);
    for (int i = 0; i < m; i++) cin >> a[i];

    sort(a.begin(), a.end());

    vector<int> white_streak;
    white_streak.reserve(m);

    if (a[0] - 1 != 0) {
        white_streak.emplace_back(a[0] - 1);
    }

    if (n - a[m - 1] != 0) {
        white_streak.emplace_back(n - a[m - 1]);
    }

    for (int i = 0; i < m - 1; i++) {
        const int dist = abs(a[i + 1] - a[i]) - 1;
        if (dist != 0) {
            white_streak.emplace_back(dist);
        }
    }

    int k = *min_element(white_streak.begin(), white_streak.end());

    int ans = 0;

    for (auto &&i : white_streak) {
        ans += ceil(i, k);
    }

    cout << ans << "\n";
}

E Sequence Matching

nosub during contest Difficulty: 1468 問題へのリンク 自分の提出へのリンク

ABの編集距離が答え。 AOJの編集距離の問題と同じ。

編集距離の計算は最長共通部分列 (Longest Common Subsequence, LCS)の計算とよく似ている。 編集距離も最長共通部分列もDPで計算できる。

編集距離も最長共通部分列も今年の1月に解いたし、もし解いていなくても簡単なDPなので解きたかった。 コンテスト中に蟻本*1見て思いつきたかった。

(注)蟻本でやったのは編集距離ではなくて最長共通部分列だった。

F Range Xor Query

48:43 AC Difficulty: 1453 問題へのリンク 自分の提出へのリンク

セグメントツリーを貼るだけ。 正の整数とXOR演算子の組はモノイドなので、セグメントツリーで扱うことができる。

セグ木であることを隠そうともしないのはちょっと😅😅😅。

感想

  • 簡単回。
  • ABCDFしか解けなかったのは残念。
  • 受験でもそうなのだが、10月前に解いた問題が解けるわけない。
  • 私が復習していないのが悪い。
  • 典型問題でもレートが上がったら楽しいのでいい。

*1:プログラミングコンテストチャレンジブック [第2版] ~問題解決のアルゴリズム活用力とコーディングテクニックを鍛える~