2020-12-13

JOI 2020/2021 二次予選参加記

2020/12/13 (日) 13:00 ~ 16:00 に行われた JOI 2020/2021 二次予選に参加したので、~~明後日の英語の追試という現実から逃避するために~~世界一内容が薄い参加記を書きます。

第20回日本情報オリンピック

前日

前日は HACK TO THE FUTURE 2021 決勝に出ていたので、JOI 対策は特にしなかった。（ここ要る？）

当日

コンテスト開始前

確か 9 時くらいに起きた。

そのあとは適当に JOI の過去問を見て、いくつか通したり昼食を食べたりしたら開始時刻になった。

IOIOI カード占い (IOIOI Cards)
差分をとると二点flipになるので、ダイクストラで頑張るhttps://t.co/6Km8rSWVbi
— Series_205@精進 (@Series_204) 2020年12月13日

小籠包 (Xiao Long Bao)　難易度 10
D が小さいので、直前 D 個だけ気合で持って DPhttps://t.co/RYSY9ueEsw
— Series_205@精進 (@Series_204) 2020年12月13日

最終問は難易度11と予想しています。当たるかな？
— 205 (@205_series) 2020年12月13日

コンテスト中

13:00　A 問題を読んだ。普通に解法がわかったので書いて提出し、AC だった。

13:07　B 問題を読んだ。よくある全部前計算する系のやつだな～と思って std::unordered_map を使って実装した。手元で動かしたら意外と遅かったのでコードテストに張り付けて再度実行、普通に TLE だった。文字列を 3 進数に直して提出したら 623 ms で AC が取れた。高速化は大事。

13:25　C 問題を読んだ。町がたくさんあるのかと思って「難しそ～」とか言っていたが、よく読んだら 2 つしかなかった。

13:54　やっと実装が終わったので提出したら RE が出た。ちょっとコードを眺めてもどこが壊れているのかわからなかったので、ランダムチェッカーを書いたら、配列外参照と無限ループが起きていて泣いた。

14:10 頃　このまま C が通らないとやばいと思い、D 問題を読んだ。楽勝そうだったので C を通してからやることにした。

14:24　C を通せたので、D をもう一度読んで実装をした。二分探索の判定部分が意外と難しく感じた。

14:41　D を提出して、WA だった。よく考えたら二分探索の初期値に不備があったので直し、14:46 に AC した。

14:46　やっと最後の E 問題にたどり着いた。遅いな～と思ったが、別に JOI は早解きと関係ないので救われた。タブレットをつまみながら考えていたら、「どっちでも良さげな人はスパイじゃない方がいいのでは」という核心に気づいた。ありがとうタブレット。

15:37　E を通して全完した。やったぜ

残りの時間は解法ツイートを書いたりおやつを食べたりした。

コンテスト後

解法ツイートをして、得点表に結果を記入、難易度表に投票した。

JOI 二次予選
2時間37分全完 (遅い...)
A set
B N 文字の文字列すべてに対する答えを前計算　C 二分探索しながら DP (尺取りでも行けそう) 普通にバグらせて一時間溶けた
D 二分探索初期値は十分大きく (戒め)
E 適当に書いて投げたら通った未証明でごめんなさい
— 205 (@205_series) 2020年12月13日

あとはだらだらしながら解説放送を聞いていた。意外な人が解説で出てきてびっくりするなどした。

まとめ・反省

やはり自分は実装が弱いなと思わされたコンテストだった。特に C 問題はデバッグに 30 分、合計では 1 時間もかけてしまった。実装ってどうやったら強くなるの？（精進を、しなさい）

また、今年は去年と違って小課題がたくさんあったが、全く小課題のことを考えていなかった。本選では部分点をどの段階で取りに行くかとか考えないとな～

まあ、数字ではこれ以上ない結果なので、満足。

2020-12-06

クイックソートを、かいた

不意にはてブロの存在を思い出したので書きますが、タイトルの通りです。他に何もありません。クイックソートの説明は面倒なのでしていません (誰がこの記事を読むのだろうか)

ja.wikipedia.org

動機

久しぶりに競プロ以外でコードを書きたくなったので、書いたことのなかった結構速めのソートアルゴリズムを書いた。 ~~ついでに~~学校の課題に同じ内容のを提出した。

1

最初に書いたコード。ググって見つけたコードを適当にパクった（コピペではないので、セーフ）

template <class RandomAccessIterator>
void quicksort(RandomAccessIterator first, RandomAccessIterator last) {
    if(last - first <= 1) return;
    RandomAccessIterator i = first, j = last - 1, pivot = first;
    while(true) {
        while(*i < *pivot) ++i;
        while(*pivot < *j) --j;
        if(i >= j) break;
        std::iter_swap(i, j);
        ++i;
        --j;
    }
    quicksort(first, i);
    quicksort(j + 1, last);
}

pivot として範囲の一番前方を選んでいるので、ソート済みの配列等が来ると計算時間が $\mathrm{O}(n^2)$ になる(死)。

2

先ほどのコードの問題点を解消するために、pivot の位置を工夫した。具体的には範囲の両端と真ん中の値の中央値とした。

実はこれはパクリではなく、普通に自分で考えた (だから何だと)

template <class RandomAccessIterator>
void quicksort(RandomAccessIterator first, RandomAccessIterator last) {
    if(last - first <= 1) return;
    RandomAccessIterator i = first, j = last - 1,
                         pivot = first + (last - first) / 2;
    if(*i > *pivot) std::iter_swap(i, pivot);
    if(*pivot > *j) std::iter_swap(pivot, j);
    if(*i > *pivot) std::iter_swap(i, pivot);
    while(true) {
        while(*i < *pivot) ++i;
        while(*pivot < *j) --j;
        if(i >= j) break;
        std::iter_swap(i, j);
        ++i;
        --j;
    }
    quicksort(first, i);
    quicksort(j + 1, last);
}

これでソート済みの配列が飛んできても死ななくなった。

速度が気になったので、ランダムな $10^6$ 要素の順列のソートにかかった時間を測定した。 (ちなみに 100 回平均)

my sort   : 85.9655 ms
std::sort : 83.5029 ms

3

std::sort に負けて悔しいので改良した。

小さい $n$ では挿入ソートが最速という噂を夢の中で聞いたので、調べてみたら、確かにそうだった。 $n\le100$ なら挿入ソートに移行することにした。

template <class RandomAccessIterator>
void insertion_sort(RandomAccessIterator first, RandomAccessIterator last) {
    if(last - first <= 1) return;
    for(RandomAccessIterator i = first + 1; i < last; ++i)
        for(RandomAccessIterator j = i; j > first && *(j - 1) > *j; --j)
            std::iter_swap(j - 1, j);
}

template <class RandomAccessIterator>
void quicksort(RandomAccessIterator first, RandomAccessIterator last) {
    if(last - first <= 1) return;
    if(last - first <= 100) {
        insertion_sort(first, last);
        return;
    }
    RandomAccessIterator i = first, j = last - 1,
                         pivot = first + (last - first) / 2;
    if(*i > *pivot) std::iter_swap(i, pivot);
    if(*pivot > *j) std::iter_swap(pivot, j);
    if(*i > *pivot) std::iter_swap(i, pivot);
    while(true) {
        while(*i < *pivot) ++i;
        while(*pivot < *j) --j;
        if(i >= j) break;
        std::iter_swap(i, j);
        ++i;
        --j;
    }
    quicksort(first, i);
    quicksort(j + 1, last);
}

これって多分だけど最悪計算量は落ちてませんよね。

んで測定

my sort   : 75.2429 ms
std::sort : 89.9799 ms

俺の勝ち。なんで負けたか明日までに考えといてください。そしたら何かが見えてくるはずです。

おわりに

std::sort は最悪計算時間が $\mathrm{O}(n \log n)$ だったと思うので、それを考えると勝利ではない (Hack される可能性がある)

cpprefjp には、std::sort はイントロソートで実装されていることが多いみたいな記述があった。クイックソートとヒープソートを組み合わせる的なやつらしい。

2020-06-22

ABC171 - F を余事象からアプローチする

本番で「簡単じゃーん」とか言ってたら、解説と違う解法だったので

F - Strivore

言いかえ・余事象

操作を逆から見ると、「長さ $|S|+K$ で、部分列に $S$ を持つ文字列」の個数を求めればいいことがわかります。（Editorialではこれを直接求めていますが、僕にはこれを直接求めるのが困難に感じたので、余事象を考えました。）

余事象を考えると、「長さ $|S|+K$ で、部分列に $S$ を持たない文字列 $T$ 」の個数がわかればいいです。

余事象を解く

$L$ を、「 $T$ の部分列かつ $S$ の接頭辞である最長の文字列の長さ」とします。

$0\le L \lt |S|$ なので、各 $L$ について $O(1)$ で求められれば良いです。

$p_i$ を、「 $p_{i-1}\lt j$ かつ $T_j=S_i$ となる最小の $j$ 」とします。

$p$ の選び方は ${}_{|S|+K}C_L$ 通りあります。

$T$ の $p$ として採用されないindex $i$ の、文字の選び方を考えます。 $i\lt p_j$ となる最小の $j$ を考えたとき、 $S_{p_j}$ は $T_i$ として使えません。

逆にそれ以外の文字は使えるので、 $26-1=25$ 通りの文字を選べます。

よって、各 $L$ について ${}_{|S|+K}C_L\times 25^{|S|+K-L}$ を足し合わせればいいです。

コード：Submission #14557607 - AtCoder Beginner Contest 171

おわり

なんか説明が苦手なので駄文になってしまった気がしています。

考察はどっちが楽かわかりませんが、僕には余事象の方が簡単に感じます。あと、実装は明らかにこっちのほうが楽です（どっちでも楽だろ）。

2020-05-05

PAST2 バチャ記

atcoder.jp

どういう記事？

第二回PAST のバチャで全完をキメたので適当に振り返る、誰得？な記事です。

解法ネタバレのような何かを含みます。

解法・問題ごとの感想

適当に解法を書くだけです。解説ではありません。

A - エレベーター

階と整数をうまく一対一対応させるとできる。 (地上0階が存在しないという罠...)

B - 多数決

全部数えるだけ。

C - 山崩し

これを書いているときに、山崩しという設定だったことを初めて知った。

問題文で丁寧に説明されている通り実装するとできる。

D - パターンマッチ

いい解法が思いつかなかったが、 $T$ としてあり得る文字列を全部試せばよい。

E - 順列

問題文に書いてある操作をやりまくればとけると思う。UnionFind を持っていれば貼るだけ。

F - タスクの消化

この辺から制約が大きくなるので、適当にやりすぎるとTLEする。

タスクを std::priority_queue などで管理すればいい

G - ストリング・クエリ

文字をひとつずつ追加・削除していると日が暮れる。

std::queue<char, int> のような感じで管理すると解ける。

H - 1-9 Grid

問題設定が割と好きかもしれない。

実装は、適当にやればできそう。

I - トーナメント

トーナメントをシミュレーションすればいい。(優勝者だけは、最後に出場した試合で勝利しているという罠...)

J - 文字列解析

問題文に書かれている通りに操作をすると解ける、それだけ。

ちなみに、僕の感覚ではこの問題までが自明枠

K - 括弧

括弧列は、初項 $0$ で、(で $+1$ 、)で $-1$ する数列を考えると分かりやすかったりする。(我流なのでもっといい方法がありそう)

正しい括弧列は、このような数列の内、全ての項が非負で末項が $0$ である数列と対応する。

このことを考えながら超適当に DP を書くと通る。

L - 辞書順最小

「適当に前から貪欲すれば通るじゃん！」と思って適当に書いたらTLEした。

区間 min をしたかったので、セグ木で殴る、おしまい。

バチャ終わった後思いつきましたが、優先度付きqueue でも書けそう。

M - 食堂

個人的にこの問題が最難だと思う。

問題の日本語を読み解くのが難しいですが、頑張って前処理をすると二分探索を使ってクエリあたり対数時間で解ける。

N - ビルの建設

なんか JOI にありそうな雰囲気。座圧してBITで解ける。(非本質な座標圧縮は、書くために多くのモチベを必要とすることで知られている。)

O - 可変全域木

この中で一番好きな問題。

適当に最小全域木を作る。 $(その重み)+(注目している辺u,vの重み)-(最小全域木のパスu,vの辺で最大の重み)$ を求めたい。右の項以外は自明なので、右の項を求めることを考える。

これは、クラスカル法で、クエリあたり $O(N\alpha(N))$ で解ける。(これだとTLE)

全てのクエリに対して並列で二分探索をすることで、解ける。(計算量を書くのを面倒くさがる人)

感想

N 以外はそんなに知識を必要とはしない問題だった気がすると書いてから思ったが、並列二分探索などは結構高レベルな知識なのかもしれない (?)

尾張に

本当に誰得？な記事が完成してしまった。永久に下書き保存しておいても意味がないので、とっとと世に放つことにする。

2020-05-03

ABC165F LIS on Tree の解説のような何か

この問題割と好き (まあ、好きじゃなかったら記事書かない気がする)

atcoder.jp

問題

各頂点に整数が書かれた木が与えられる。各 $1\le k\le N$ について、次を求めよ。

頂点 $1$ から頂点 $k$ までのパス上の整数列の、LIS (最長増加部分列) の長さ

制約

$N\le2\times10^5$

前提 (普通の LIS)

次(リンク)のような問題を考えます。

onlinejudge.u-aizu.ac.jp

この問題はDPで $O(N \log N)$ で解くことができます。二分探索を用いる解法とセグメント木 (若しくはBIT) を用いる解法があります。詳しい解法については、調べましょう。(丸投げ)

二分探索解をこの後使うので、一応実装を書きます。

#include <bits/stdc++.h>
using namespace std;

constexpr int INF = 1 << 30;

int N, A[100009];
int dp[100009];

int main() {
    cin >> N;
    for(int i = 0; i < N; i++)
        cin >> A[i];

    fill(dp, dp + N, INF);

    for(int i = 0; i < N; i++)
        *lower_bound(dp, dp + N, A[i]) = A[i];

    cout << lower_bound(dp, dp + N, INF) - dp << endl;

    return 0;
}

本題

先ほどの実装で各 $i$ での DP 配列の書き換え回数が $O(1)$ だったことに注目します。

書き換えが $O(1)$ なので、元の値を覚えておいて、その値に戻すのも $O(1)$ でできます。

よって、DP 配列を適宜更新したり元の値にもどしたりしながら木の上を dfs することで、全体で $O(N \log N)$ 時間で解けます。

#include <bits/stdc++.h>
using namespace std;

constexpr int INF = 1 << 30;

int N, a[200009];
vector<int> G[200009];
int dp[200009];
int ans[200009];

void dfs(int v, int p) {
    int *it = lower_bound(dp, dp + N, a[v]);
    swap(*it, a[v]);

    ans[v] = lower_bound(dp, dp + N, INF) - dp;

    for(int u : G[v])
        if(u != p) dfs(u, v);

    swap(*it, a[v]);
}

int main() {
    cin >> N;
    for(int i = 1; i <= N; i++)
        cin >> a[i];
    for(int i = 1; i < N; i++) {
        int u, v;
        cin >> u >> v;
        G[u].push_back(v);
        G[v].push_back(u);
    }

    fill(dp, dp + N, INF);

    dfs(1, -1);

    for(int i = 1; i <= N; i++)
        cout << ans[i] << endl;

    return 0;
}

2020-04-20

ABC163F path pass i 解説

はじめに

黄色diff下位くらいかと思ってたら橙だったので、自分の考察を整理する意味も込めて書いてみることにしました。

問題

ABC163 F - path pass i

木の各頂点に色が塗られている
各 $1\le k\le N$ について、色 $k$ が塗られている頂点を一度以上通るパスを数える

制約

$1\le N\le 2\times 10^5$

考察

はじめに (当たり前な話)

パスは $O(N^2)$ 個あるので、パスごとに考えていると間に合いません。(当たり前かもしれないけど、一応)

余事象を考えるという話

色 $k$ を通るパスを直接数え上げようとすると、ダブりが出たりしてとてつもなく難しそうですが、こういう時は落ち着いて余事象を求めることを考えるといいです。(この考えは割と大事な気がする)

「色 $k$ を一度以上通る」の余事象は「色 $k$ を一度も通らない」です。これを数えて、パスの総数から引き算すればいいです。

その余事象はどう求めるのか

超当たり前ですが、グラフに色 $k$ の頂点が存在しないなら、その中でどんなパスをとっても色 $k$ の頂点を一度も通りません。

なので、色 $k$ を通らないパスを数えたいなら、色 $k$ の各頂点で木を切断して、各連結成分内で個別に求めてやればいいです。

実は、木の頂点数から、パスの数は一意に定まります (二頂点の選び方と一対一対応するので)。ちなみに頂点数を $x$ とするとパスは $\frac{x\left(x+1\right)}{2}$ 個です。

以上から、色 $k$ の頂点で切断したときの連結成分の頂点数を知りたくなります。これは、木を根付き木にして、各部分木の頂点数を求めておくとできます。

f:id:Series_205:20200420111848p:plain

たとえばこのような木の赤い頂点について考えます。根は頂点 $1$ です。

赤い頂点で木を切断すると、 $\{2,4,6\},\{3\}$ という連結成分ができます。

頂点 $v$ を根とする部分木の頂点数を $\mathrm{sz}[v]$ とすると、 $\{2,4,6\}$ の方の頂点数は $\mathrm{sz}[2]-\mathrm{sz}[5]$ 、 $\{3\}$ の方は $\mathrm{sz}[3]$ として求められます。

実装の際は、色ごとに stack を用意して dfs をすると、きれいに書ける気がします。(実装例を見てね)

実装

オーバーフローしない！(素振り)

#include <bits/stdc++.h>
using namespace std;

constexpr int MAX = 200010;

// 関数にしておくと便利
long long subcalc(long long x) { return x * (x + 1) / 2; }

int n;
int c[MAX];
vector<int> G[MAX];

int sz[MAX];
stack<int> last[MAX];
long long ans[MAX];

// 部分木のサイズを求める
void dfs1(int v, int p) {
    sz[v] = 1;
    for(int u : G[v]) {
        if(u != p) {
            dfs1(u, v);
            sz[v] += sz[u];
        }
    }
}

// 答えの計算
void dfs2(int v, int p) {
    if(v == 0) { // 根にアクセスする前に切断しておく
        for(int i = 1; i <= n; i++)
            last[i].push(n);
        dfs2(1, 0);
        for(int i = 1; i <= n; i++)
            ans[i] += subcalc(last[i].top());
    } else {
        last[c[v]].top() -= sz[v];

        for(int u : G[v]) {
            if(u != p) {
                last[c[v]].push(sz[u]);
                dfs2(u, v);
                ans[c[v]] += subcalc(last[c[v]].top());
                last[c[v]].pop();
            }
        }
    }
}

int main() {
    cin >> n;
    for(int i = 1; i <= n; i++) {
        cin >> c[i];
        last[i].push(n);
    }
    for(int i = 0; i < n - 1; i++) {
        int a, b;
        cin >> a >> b;
        G[a].push_back(b);
        G[b].push_back(a);
    }

    dfs1(1, 0);
    dfs2(0, 0);

    for(int i = 1; i <= n; i++)
        cout << subcalc(n) - ans[i] << endl;

    return 0;
}

おわりに

コンテスト中は stack じゃなくて vector を用いたのですが、vector の方が実行時間もメモリもいい結果になりました、何故でしょう？(その辺詳しくないのでよくわからない...)

あと、全然関係ない話なんですが、解説記事で <bits/stdc++.h> を使うのは大丈夫なんでしょうか？

2020-04-18

JOI - Spy を bitset でゴリ押す

問題リンク

JOI 2013 春合宿 2日目 3 - Spy

問題概要

JOI 社と IOI 社の木が与えられる
リーダーの配下の全社員が所属するグループが与えられる
2 つの木の対応する頂点について、共通して所属するグループを数える

想定解

JOI のページに載っている解説スライドによると、オイラーツアーと imos 法を使うのが想定解らしいです。

なんか面倒くさそうですね。(ちなみにそんなに面倒ではないです)

bitset 解法

ここからが本題です。

発想

社員 $i$ がプロジェクト $j$ に所属しているかどうかがわかれば楽勝です。これは、最初にリーダーだけにこの情報を入れておき、それぞれのプロジェクトについて木上でimos法的なことをやれば、 $O(NM)$ でできます。

これは遅すぎるので、プロジェクトごとにしていた操作を一括でしたいです。

サイズ $M$ の bitset を $N$ 個用意してこの情報を管理すると、従来では個別にしていたimos法の処理を、bitwise or 演算一回で実現できます。

この超適当高速化により、何と TLE が取れてしまいます。bitset 最強 !!

ちなみに JOI 社と IOI 社の社員が共通して所属しているプロジェクトの数は、bitwise and で求められます。

実装

サイズ $500000$ の bitset が $2000$ 個必要なので、油断していると MLE します。気を付けましょう。

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

constexpr int N = 2000;
constexpr int M = 500000;

int n, m;

int rootj, rooti;
vector<int> J[N], I[N];
bitset<M> joi[N], ioi[N];

queue<int> que;

int main() {

    cin >> n >> m;
    for(int i = 0; i < n; i++) {
        int a, b;
        cin >> a >> b;
        a--;
        b--;
        if(a >= 0) J[a].push_back(i);
        else rootj = i;
        if(b >= 0) I[b].push_back(i);
        else rooti = i;
    }
    for(int i = 0; i < m; i++) {
        int a, b;
        cin >> a >> b;
        joi[a - 1].set(i);
        ioi[b - 1].set(i);
    }

    que.push(rootj);
    while(!que.empty()) {
        int v = que.front();
        que.pop();
        for(int u : J[v]) {
            joi[u] |= joi[v];
            que.push(u);
        }
    }

    que.push(rooti);
    while(!que.empty()) {
        int v = que.front();
        que.pop();
        for(int u : I[v]) {
            ioi[u] |= ioi[v];
            que.push(u);
        }
    }

    for(int i = 0; i < n; i++)
        cout << (joi[i] & ioi[i]).count() << endl;

    return 0;
}