Rust で SkewHeap を書いてみた

Rust

タイトルのまんま．
純粋関数型データ構造っぽさを意識して書いてみました．

use std::rc::Rc;
enum SkewHeap<T: Ord + Clone> {
    Empty,
    Node(T, Rc<SkewHeap<T>>, Rc<SkewHeap<T>>)
}

impl<T: Ord + Clone> Clone for SkewHeap<T> {
    fn clone(&self) -> SkewHeap<T> {
        match *self {
            SkewHeap::Empty => SkewHeap::Empty,
            SkewHeap::Node(ref v, ref l, ref r) => SkewHeap::Node((*v).clone(), (*l).clone(), (*r).clone()),
        }
    }
}

impl<T: Ord + Clone> SkewHeap<T> {
    fn push(&self, val: T) -> SkewHeap<T> {
        self.meld(SkewHeap::Node(val, Rc::new(SkewHeap::Empty), Rc::new(SkewHeap::Empty)))
    }

    fn meld(&self, other: SkewHeap<T>) -> SkewHeap<T> {
        match *self {
            SkewHeap::Empty => other.clone(),
            SkewHeap::Node(ref v1, ref l1, ref r1) => {
                match other {
                    SkewHeap::Empty => self.clone(),
                    SkewHeap::Node(ref v2, ref l2, ref r2) => {
                        if v1 < v2 {
                            let r = r1.clone();
                            //SkewHeap::Node(v1.clone(), l1.clone(), Rc::new(r.meld(other.clone())))
                            SkewHeap::Node(v1.clone(), Rc::new(r.meld(other.clone())), l1.clone())
                        } else {
                            let r = r2.clone();
                            //SkewHeap::Node(v2.clone(), l2.clone(), Rc::new(r.meld(self.clone())))
                            SkewHeap::Node(v2.clone(), Rc::new(r.meld(self.clone())), l2.clone())
                        }
                    }
                }
            }
        }
    }

    fn pop(&self) -> (Option<T>, SkewHeap<T>) {
        match *self {
            SkewHeap::Empty => (None, SkewHeap::Empty),
            SkewHeap::Node(ref v, ref l, ref r) => {
                (Some(v.clone()), l.meld((**r).clone()))
            }
        }
    }
}

使ってみた

試しに以下の問題を解いてみた．
http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=ALDS1_9_C

結果は 3.99 sec で TLE．まあ clone しまくってるのでそれはそう．予想より早い（もっと遅いと思っていた）

追記
木の形偏ってるなあと思っていたら，meld するときに swap するの忘れてた．すると 3.99 sec から 3.07 sec に改善した．

感想

もし競プロならこのままだと使えない．純粋関数型っぽさを捨てれば早いのは書ける．Rust はライフタイムの制約が厳しすぎて，変更が加わらなかったノードは共有するみたいなコードを書くのが難しい．どうかけばいいかわからん．

AOJ 1386 Starting a Scenic Railroad Service

AOJ 競プロ

問題文

http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=1386

解法

一方はいもす法やるだけなのはすぐわかると思います．
もう一方が問題ですが，これも累積和で簡単に求まります．
じつは，乗客 i のデータの区間 [a[i], b[i]] に対して，端点以外で少しでもかぶっている他の乗客の区間の数を M_i とすると，M = max{ M_i } が答えになります．

以下ちゃんとした（仰々しい）証明．
求めたい答えを A とすると，A >= M である．区間 [a[i], b[i]] に少しでもかぶる乗客の集合を S_i (これには乗客 i も含める) とする．S_i のうち，互いに区間がかぶらない乗客が優先的に予約をしていくと考えれば，少なくとも |S_i| 席が必要である．仮に s ( < |S_i| ) 席しかないとする．互いに区間がかぶらない乗客の数が s 人以上であれば，そのうちの s 人で先に席を埋めてしまうと，乗客 i が予約できなくなるので，s 席では足りない．乗客の数が s 人未満でも同じ．よって，A >= |S_i| だから A >= M が示せた．
次に A <= M であることを示す．とはいっても明らかで，ある区間に同時にのる乗客の数以上の席は明らかに必要ない．

以上より，A = M = max{ |S_i| } であり，累積和で求めることができる．
具体的には順方向の累積和 sum[i] ( b[i] を用いる ) と逆方向の累積和 rsum[i] ( a[i] を用いる ) を用意すれば良い．この時，
sum[i] := 区間 [0..i] に完全に含まれる乗客の数
rsum[i] := 区間 [i...] に完全に含まれる乗客の数
になる．

ソースコード

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

int main() {
    int n; cin >> n;
    int MAX = 1e5 + 2;
    vector<int> a(n), b(n);
    vector<int> imos(MAX), sum(MAX), rsum(MAX);
    for(int i = 0; i < n; ++i) {
        cin >> a[i] >> b[i];
        imos[a[i]]++;
        imos[b[i]]--;
        sum[b[i]]++;
        rsum[a[i]]++;
    }
    for(int i = 1; i < MAX; ++i) {
        imos[i] += imos[i - 1];
        sum[i] += sum[i - 1];
    }
    for(int i = MAX - 1; i >= 1; --i) {
        rsum[i - 1] += rsum[i];
    }
    int ans1 = 0, ans2 = *max_element(imos.begin(), imos.end());
    for(int i = 0; i < n; ++i) {
        ans1 = max(ans1, n - sum[a[i]] - rsum[b[i]]);
    }
    cout << ans1 << ' ' << ans2 << endl;
}

感想

本番ではチームメイトが累積和のやり方を考えてくれて，僕が正当性を詰めました．
詰めると言っても流石にここまで丁寧に詰めたわけではないですが…

AOJ1133 Water Tank

AOJ 競プロ

問題文

http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=1133&lang=jp

方針1

いわゆるやるだけ問題ですが，頑張って通して満足するだけで終わると得られるものがなさそうな問題．
こういうので実装方針を詰める練習をしなければいけないと思う（あくまで僕の意見ですが）．

まず，仕切りを外しても状態が変わらないような水槽は統合してしまってよいことがわかる．仕切りを外してよいのは，どちらか一方の水が溢れており，かつ水の高さが等しい時．

次に，シミュレーションするなら1秒毎ではなくて，どこからか水が溢れ始める時点で区切れば良さそうに見える．

溢れた時にどうするかだが，これは蛇口の場所を変えるのと同値であると考えれば見通しが良さそうにみえる．つまり，

  • 水がどちらにもあふれる場合，今見ている水槽にある蛇口を2分割して左右の水槽に分配する
  • 水が左にあふれる場合，今見ている水槽にある蛇口を左に移動させる．右にあふれるときも同様．

蛇口の移動は隣に移動させるだけじゃなくて，連続して移動しうる（移動先がすでに溢れている場合）ので，隣に移す処理を水槽の数だけループを回せば，いずれ蛇口は正しい位置に移動できる．

あとは L 回のクエリを時系列順にソートしておいて，そのタイミングが来たら答えを計算する．

入力サイズはかなり小さいのでよっぽどひどい実装でない限り計算量は気にならない．

ソースコード1

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

constexpr double eps = 1e-6;

struct tank {
    double wall_l, wall_r;
    double in;
    double w, h;
    tank() : wall_l(0), wall_r(0), in(0), w(0), h(0) {}
};

tank merge(tank const& left, tank const& right) {
    tank res;
    res.wall_l = left.wall_l;
    res.wall_r = right.wall_r;
    res.in = left.in + right.in;
    res.w = left.w + right.w;
    res.h = left.h; // (= right.h)
    assert(fabs(left.h - right.h) < eps);
    return res;
}

int main() {
    constexpr double width = 100, height = 50, depth = 30;
    int D; cin >> D;
    while(D--) {
        int N; cin >> N;
        vector<tank> ts(N + 1);
        ts[0].wall_l = ts.back().wall_r = height;
        for(int i = 0; i < N; ++i) {
            int B, H; cin >> B >> H;
            ts[i].w = B;
            ts[i].wall_r = ts[i + 1].wall_l = H;
        }
        ts[N].w = width;
        for(int i = N; i >= 1; --i) {
            ts[i].w -= ts[i - 1].w;
        }
        int M; cin >> M;
        double total_in = 0;
        for(int i = 0; i < M; ++i) {
            int F, A; cin >> F >> A;
            total_in += A;
            int x = 0;
            for(int j = 0; j <= N; ++j) {
                x += ts[j].w;
                if(x > F) {
                    ts[j].in += A / depth;
                    break;
                }
            }
        }

        int L = 0;
        cin >> L;
        vector<tuple<int, int, int>> qs;
        for(int i = 0; i < L; ++i) {
            int P, T; cin >> P >> T;
            qs.emplace_back(T, P, i);
        }
        sort(begin(qs), end(qs));

        vector<double> ans(L);
        double now_t = 0;
        int qi = 0;
        while(qi < L) {
            int T, P, idx;
            tie(T, P, idx) = qs[qi];
            if(T >= width * height * depth / total_in) {
                ans[idx] = height;
                qi++;
                continue;
            }
            double dt = T - now_t;
            for(auto& tk : ts) {
                if(tk.in > 0) {
                    double wall_h = min(tk.wall_l, tk.wall_r);
                    dt = min(dt, (wall_h - tk.h) * tk.w / tk.in);
                }
            }
            for(auto& tk : ts) {
                tk.h += dt * tk.in / tk.w;
            }
            vector<tank> nxt_ts = {ts[0]};
            for(int i = 1; i < (int)ts.size(); ++i) {
                if(fabs(ts[i].h - nxt_ts.back().h) < eps && fabs(ts[i].h - ts[i].wall_l) < eps) {
                    nxt_ts.back() = merge(nxt_ts.back(), ts[i]);
                } else {
                    nxt_ts.push_back(ts[i]);
                }
            }
            ts = move(nxt_ts);
            now_t += dt;
            for(int loop = 0; loop < 10; ++loop) {
                for(int i = 0; i < (int)ts.size(); ++i) {
                    bool to_l = fabs(ts[i].wall_l - ts[i].h) < eps,
                         to_r = fabs(ts[i].wall_r - ts[i].h) < eps;
                    if(to_l && to_r) {
                        ts[i + 1].in += ts[i].in / 2;
                        ts[i - 1].in += ts[i].in / 2;
                        ts[i].in = 0;
                    } else if(to_l) {
                        ts[i - 1].in += ts[i].in;
                        ts[i].in = 0;
                    } else if(to_r) {
                        ts[i + 1].in += ts[i].in;
                        ts[i].in = 0;
                    }
                }
            }
            if(fabs(now_t - T) < eps) {
                double x = 0;
                for(auto& tk : ts) {
                    x += tk.w;
                    if(x > P) {
                        ans[idx] = tk.h;
                        break;
                    }
                }
                qi++;
            }
        }

        for(auto h : ans) {
            cout << fixed << setprecision(6) << h << endl;
        }
    }
}

方針2

さっきのもまあ素直な実装だから辛いと言うほどではないが，もう少し上手く処理できる．
ある蛇口に注目して，初期状態から時間 T だけ水を入れた場合にどうなるか観察する．
小さい視点（直接注いでいる水槽）から視野を広げていって，最終的に全体を眺める感じなので，再帰構造が見えてくる．

pour(pos, l, r, a) := pos 番目の水槽に水量 a だけ流した時，水槽 [l..r) はどうなっているか？また，[l..r) について流しきった時に，a はどれだけ残っているか？

さて，仕切り y の位置で水があふれるということを広い視点で眺めてみる．ここでは左からあふれると仮定する．「水が仕切り y の位置で溢れてくる」ことは「仕切り y から左側で，仕切り y よりはじめて高くなる仕切りまでの水槽を考えた時，それらの水位が仕切り y とおなじになっている」ことと言い換えることができる．
つまり，水槽 [l..r) を眺める時，部分構造として，端を除いた [l..r) の仕切りの中で最も高いものを mid として，[l..mid) と [mid..r) を考えればよいということにほかならない．
そのとき，pos が [l..mid) の方にあるか [mid..r) の方にあるかで，先にどちらを処理するかを決めれば良い．
[l..r) に水を流した後に流すべき水が残っているなら，その水については一段上の再帰段階で処理するものである．

ソースコード2

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

void pour(int pos, int l, int r, double& a, vector<double> const& x, vector<double> const& h, vector<double>& ans) {
    if(r - l > 1) {
        int mid = l + 1;
        for(int i = l + 1; i < r; ++i) {
            if(h[mid] < h[i]) {
                mid = i;
            }
        }
        if(pos < mid) {
            pour(pos, l, mid, a, x, h, ans);
            pour(pos, mid, r, a, x, h, ans);
        } else {
            pour(pos, mid, r, a, x, h, ans);
            pour(pos, l, mid, a, x, h, ans);
        }
    }

    double side_h = min(h[l], h[r]);
    double add = max(0.0, (side_h - ans[l]) * (x[r] - x[l]));
    add = min(add, a);
    a -= add;
    for(int i = l; i < r; ++i) {
        ans[i] += add / (x[r] - x[l]);
    }
}

int main() {
    int D; cin >> D;
    while(D--) {
        int N; cin >> N;
        vector<double> x(N + 2), h(N + 2);
        for(int i = 1; i <= N; ++i) {
            cin >> x[i] >> h[i];
        }
        x[N + 1] = 100;
        h[0] = h[N + 1] = 50;
        int M; cin >> M;
        vector<double> in(N + 1);
        for(int i = 0; i < M; ++i) {
            int F, A; cin >> F >> A;
            int j = upper_bound(begin(x), end(x), F) - begin(x) - 1;
            in[j] += A / 30.0;
        }

        int L; cin >> L;
        while(L--) {
            int P, T; cin >> P >> T;
            vector<double> ans(N + 1);
            for(int i = 0; i < N + 1; ++i) {
                double a = in[i] * T;
                pour(i, 0, N + 1, a, x, h, ans);
            }
            int j = upper_bound(begin(x), end(x), P) - begin(x) - 1;
            cout << fixed << setprecision(6) << ans[j] << endl;
        }
    }
}

感想

本番だったら，実装方針を詰める時間に実装したほうが早いかもしれないので難しいところですが，練習で解くなら実装方針まで考えたい．

2017年の振り返り

年末

はじめに

2017年の振り返りをします．去年の振り返り記事は自分でも読みづらかったので，今年はできるだけ簡潔に書こうと思います．
基本的に競プロ関係に絞って書くことにします．

1月，2月，3月

  • 記憶がない．多分競プロをほとんどやっていない時期．
  • 2月頭から3月頭にかけて短期バイト（300時間ぐらい働いたかな）してお金を稼いだのは覚えている．
  • 3月末には関西系の大学が集まってやる競プロ合宿に参加した．参加後あたりからちゃんと再開した気がします．

4月

  • 新入生プロジェクトで競プロを教えることになったので，資料作成とか問題選定とかやりまくってたかも．
  • AtCoderのレートがこの月に200ぐらい上がっていた（元が低すぎるってそれ一番言われてるから

5月

  • ICPCに意識を向け始めた頃．AOJ-ICPCを下の方から埋めまくっていた気がする．
  • レートは上がりませんでした．悲しいね．

6月

  • チーム練習をはじめかける頃．AOJ-ICPCの虚無実装問題を埋めていたせいもあって実装担当になってしまう．
  • レートは上がりませんでした．なんでや．

7月

  • ICPCの練習をガリガリやる．
  • 勉学が疎かになっていることに気がつく．
  • 国内予選に学内2位で通過する．これはかなり嬉しかった．

8月

  • 競プロの練習（主に実装系）をちょこちょこやっていた．
  • 問題をたくさん解くというよりは，辛い問題を時間をめっちゃかけて通すみたいなことをしていた（これのせいで瞬発力が必要なコンテストが苦手になっていたかもしれない

9月

  • 練習方法は8月と同じ．DPの問題を中心にやってたかな．
  • レートが今（12月現在）と同じぐらいに上がっていた

10月

  • CODEFESTIVAL 2017で予選通過．かなりギリギリだった．（反省して
  • レートはあまり変わらず．

11月

  • 一瞬黄色になる（競プロはじめました）
  • CODEFESTIVAL 本戦で冷える．青に戻る（競プロ引退）
  • CODEFESTIVAL はなんだかんだ楽しいのでみんなも参加しよう！

12月

  • ICPC アジア地区の季節．
  • ミャンマーの Yangon 大会に出て4位だった．あと1問通していればWFだったので悔しいが，初アジアにしては良い成績だったと思う．
  • Tsukuba大会は冷えた．誤読していて，1問解けない問題になっていたのは反省しないとダメ．でも普通に地力が足りない感じがしたので，来年頑張るぞという気持ちになった．
  • Codeforces でやっと div1 に上がる．div2 の A と B からやっと解放されて嬉しい．

まとめ

  • 競プロのレート変動は以下の通り．
    • AtCoder 1523 -> 1945 (+422)
    • Codeforces 0 -> 1952
    • CSAcademy 0 -> 1759
    • TopCoder 0 -> 1403 (出たのは2回だけ．今後出るつもりはあまりない．
  • ちなみに AOJ-ICPC の得点は 150100 点まで上げた．500まではほとんど全部埋めて，550は7割ぐらい埋めた．
  • ICPCが思ってたより楽しかったので，来年はICPCでいい結果を残せるように頑張りたい．（このままだとチームからいらない子宣言を受けるため

それでは皆さん，良いお年を．

The 2017 ACM-ICPC Asia Yangon Regional Programming Contest 参加記

ICPC 競プロ

目次

はじめに

kazuma, nakano, 僕の3人でチーム KazumaDragon としてミャンマーの Regional に参加しました．
ミャンマーで開催されるのが今年が2回目とのことで，まだ記録が少ないと思うので参加記を書こうと思います．
前半はプラクティスとコンテストについて，後半は旅程の全てを（大体）時系列順に箇条書しています．

プラクティス

  • 開始前にスコアボードを見ると5問もある．なんか雑に開始した気がする．
  • Aは線形方程式，Bは式をパースして場合分けを丁寧に頑張るだけ，CDは（僕は）読んでない，Eは基本貪欲に取っていく枝狩り探索？みたいな出題．Bは途中で問題の修正が入った．
  • 意外とまともだなあ．去年も見た目はまともらしかったしね．
  • とりあえず環境を確認する．
  • IntelliJ，NetBeans，Eclipseなどがある．Java勢に優しい．
  • 普通のテキストエディタもターミナルが一緒についてるそこそこ使えるやつがあったのでそれで書くことにした．
  • というかVimがあるって書いてあったのに vim を叩いたら無いって怒られた．困るよ〜．
  • テンプレートを書いて，WAを出すコードを投げる．CE．は？
  • C++11 すら使えないらしい．環境はいいんだからオプションちゃんとつけてほしい．多分最適化オプションもついてないので pragma optimize しましょう！
  • 修正して出す．TLE．なんでやねん（これは僕が提出先を間違えていただけで向こうは悪くない
  • 気づいて再提出．ちゃんとWAが来る．良し．
  • REを出すコードを投げる．REがちゃんと返ってくる．やったぜ．
  • TLE の限界やスタックサイズの確認もする．予想よりまともで安心．手元でちゃんと動くなら大丈夫そう．
  • そろそろAC1個だけ貰いに行くかということで，Aがやるだけなのでちゃんと読む．
  • 行列と列ベクトルのサイズが早速書いてない．Clarの練習用にわざと書いてないんだろうなと解釈する（ほんまか？
  • Clarを投げたら予想通りのサイズで安心．書く．バグる．なんとかAC．
  • 色々あってこの時点で終了まで20分ぐらい？まあACいらんし適当に過ごそうと考える．
  • 終了20分前ぐらいにスクリーンと照明が急に音を立てて落ちる．草．なんで落ちたのか未だに不明．
  • 終了直前にまた照明が音とともに落ちる．なんでや．
  • ちなみに手元のPCは落ちないので安心してください（？）
  • ここで終了．一応結果を伝えると，E問題がめっちゃ通されてました．
  • なんだ問題自体は普通じゃん．難易度もPracticeの割には高かったように思う．
  • 難しかったねーと適当に感想戦をする．

関係ないけど，うちの大学の実験室よりはるかにPCのスペックが良かった．弊大学は†悔い改めて†

本番

  • カウントダウンとともに開始．パスワードを入力してログインするところから始まる．
  • 僕がテンプレートとか用意する間に他の2人に問題を読んでもらう．
  • Practice で作ったファイルが全部残ってて草．これええんか？
  • なんかGがセグツリで高速化する実家DPらしいので書く．初期化部分をミスってバグったがAC．
  • 次にDが素数と合成数列挙するだけと聞いたので書く．WA．やべえ．
  • flush のせいかなと思い flush して提出するもWA（めっちゃもったいない）．うーん？
  • コード読んでる限り変なところは無いので後回しにしてしまう．（なんで問題文を読み返さなかったのか）
  • （他の問題概要を聞いていたが順番を覚えていない．確か I を聞いた気がする…サンプル合わなくてIの誤読に気がついた？だったかな）
  • Aを読んだらやるだけだが実装どうするか迷ってしまう．他の問題考えながらということで後に回す（これも微妙な選択かなあ
  • Dは少し誤読していたらしい．文字列が与えられるんだけど，space を含むらしく getline が必要とのこと．Practiceでもそうだったけどやたら getline 書かされるなあ．直してAC．
  • Fが簡単らしいので概要を聞いて書く．なんか僕の理解が甘かったらしく変なコードを書きかけてしまい，kazuma が見かねて代わりに書く．AC．ごめんなさい．
  • （ここから1時間ぐらい辛かった気がするがなんで辛かったのか覚えていない）
  • Cの概要を聞いたが制約がヤバすぎる．テストケースの数 10^5 ってなんやねん．クエリじゃないんだぞ．
  • しかも各テストケースで 10^10 ぐらいの出力が要求されるらしい．えぇ…．流石に Clar を投げるがよくわからない返答が返ってきて，なんかよくわからないため後回しにすることにした（これが結果的に一番もったいなかった）
  • JとLは見た目がやばくてみんな敬遠していた．（結果的には正しかった
  • Bを読んだので kazuma に伝えたら実家なのでかけるとのこと．僕が書くより早そうだったため任せてしまう．
  • union find木だけ僕が書いたんだけど，結構バグらせてしまった（大反省）．それ以外もちょっとだけバグって時間をロスするが，一応ACする．
  • 裏で簡単だと聞いていた H の紙コーディングをしていたため，その後すぐにACする．
  • nakano が I を頑張って書いていた．Iには全く関わっていないので，裏でAを紙コーディングする．
  • 紙コーディングが終わって書く．ちょっとバグったけどすぐ直してAC．
  • この時点で10位ぐらい？初アジアにしてはいいんではということで少し安心する．
  • Eの概要を聞いて真面目に考える．3次元空間上の点を，最小限の直線で全て貫くという問題．
  • この間 kazuma は K問題を，nakano は I （と K）を考察していた．
  • 点の数 n <= 100 なためフローが生えかけたが無理なので（それはそう）棄却する．
  • こんなんNP困難やろという気持ちになる．適当に枝狩りしかないが n <= 100 はやばそうなので一旦逃げる．
  • kazuma が E をちょっと考えて最小費用流でいける（僕が棄却したのと全く同じやつ）という意見をくれた．なぜが行けると勘違いして（は？？？）書いてしまう．
  • ライブラリ移すパートでバグらせる．なんとか直してサンプルチェック．合わない．当たり前や．
  • これ無理やんけとなったので，あとに回す．
  • Kをちょっと聞いたところ，10^8 のオーダーでエラトステネスっぽいことをするらしい．まあ無理だよね
  • I はバグっているらしいし，ここらへんかなり辛くなってくる．解ける問題が無い．（この時僕の頭にC問題の文字はなかった
  • kazuma がエスパーする．「10^8 じゃなくて 10^7 で通るんでは？ｗ」とか言って投げる．
  • 僕はさすがに無理だと思っていたが AC する．流石に草．
  • もはや書いてある制約が何も信じられない．そしてここで僕がエスパーする．
  • 僕「Eは n <= 100 じゃなくて n <= 10 とかやろｗ」
  • kazuma は流石にありえないやろ，と言って嫌そうな顔をしていたが，僕の独断により n <= 20 ぐらいの bitDP 解をちゃっと書く．投げる．AC．
  • もう顔中草まみれや．
  • とりあえず nakano の I を祈る．めっちゃバグっていたが AC した．さすがプロ．
  • Iが通った時点で9完，残り15分ぐらいだったので，もう書けないかなとなって感想戦をしていた．
    • 本番の問題よりPracticeの方が難しくない？みたいなことを話していた気がする（これは嘘で，不正ACをしているため
  • なんか終了5分前ぐらいで謎の封筒を渡されたり，写真を取られまくったりする．順位表が凍結されている意味とは…
  • 終了．終わった直後は満足していた．

終わった後に気がついたんですが，問題文が書いてある前に注意書きみたいなページがあって，そこにジャッジが投げうる結果がすべて丁寧に書かれていた．こういうのはPracticeで書いてくれたほうがうれしいですね．

本番の問題概要

自分で読んだのは結局ABだけなので雑にまとめます．本文は公式ページから読めるけどね．

  • A問題．完全二分木をトーナメント表みたいな形式で出力する．表の深さ N <= 13．
    • 再帰でいい感じに書いた．出力が多いので fast IO を使うと安心っぽい．
  • B問題．友人関係と敵対関係，および推移律的なルール群が与えられるので，各クエリで与えられた2人の関係を答える．関係の数は 50個以下．
    • 冷静に考えると2部グラフ判定するだけ．UFで適当に．サイズが 10^5 でも解ける．想定はクエリごとにDFSで探索とかかな．
  • C問題．グリッド状のタイルを，あるルールに従って色塗りしていく．各時刻で新たに塗られるマスを出力していく．タイルの幅と高さはそれぞれ 10^5 ，テストケースの数は 10^5個
    • 制約がヤバイ問題その1．実装はやるだけですが若干めんどくさいか．Clarを投げるのは最低限必要で，あとはStandingsをみて解ける問題か確認するのが大切．実際うちのチーム以外の上位陣は通しているしね．
  • D問題．文字列が与えられるので，各文字を 8bit 整数とみて01ビット列に直す．その後はそれに合わせて合成数と素数を出力するだけ．入力サイズはめっちゃ小さい．
  • E問題．3次元上にある点をできるだけ少ない点で貫くときの，最小の直線の数を求める．点の数 n <= 100
    • 制約がやばい問題2．多分枝刈りが想定だが，エスパー力も大切（いいえ）．assert(n <= 26) してREせず通ったため，書かれている制約の最大値が本当に入力に存在するとは限らないらしい．
  • F問題．2つの商品があって，それぞれコストと利益が「問題分に」与えられているので，あるコスト以下で利益を最大化する．
    • 入力サイズが小さいので全通り試すと通ります．問題分が無駄に長かった．
  • G問題．数列に含まれる単調非減少列の中で，総和が最大のものを求める． N <= 10^5
    • 典型すぎる．セグツリで高速化するDPで．
  • H問題．シード値と b が与えられ，それらから数列 a_n を作っていく．i < j で a_i = a_j となるタイミングを検出せよ．ただし，a_{i+1} = (a_i を b 進数で表したときの各桁の平方和を10進数で表したもの) とする．b <= 17．
    • bが小さいので愚直に1つずつ計算していくだけですぐ衝突する．
  • I問題．一直線上に N 地点 Hyperloop がある．各 Hyperloop 間の距離は d_i である．i 番目の Hyperloop では，ある時間（任意に選べる．0でも良い）の間加速度 a_i で加速できる（加速中はその場にとどまっているみたいな感じです）．このとき，初期地点から最終地点まで行くためにかかる最短の時間を求めよ．テストケース T <= 90, N <= 10^3, a_i <= 10^4, d_i <= 10^4
    • まともに難しい問題1．O(N^2) のDPで解いたらしい．O(N^2)のDPにする前は，嘘貪欲とか，頑張って場合分けするとかやっていてバグったらしい．このセットの中だと一番解きがいがある問題っぽい？
  • J問題．文字列 $S = S_0S_1 \ldots S_{N-1}$ のハッシュを $H(S) = \sum b^{n-i-1} \times D(S_i) \mod m $ によって定める．ただし $D(a) = 0, D(b) = 1, \ldots, D(z) = 25$である．ここで，h, b, m, n が与えられる．長さ n の文字列で，ハッシュ値が h となるものは何通りあるか求めよ．
    • まともに難しい問題2．本番はどのチームも解いていない．噂によれば FFT とダブリングで解く？みたいなことを聞いた気がする．
  • K問題．[l, r] に含まれる自然数で，約数の総和が 3 で割り切れるものの個数を求める．1 <= l <= r <= 10^8，テストケースの数は20個．
    • 制約がヤバイ問題その3．制約を信じるなら線形で前処理して各テストケースO(1)しかないがわからない．エラトステネスににた感じの処理でオーダーがO(nloglogn)ぐらいには落とせたらしいが，それでもやばいね．
  • L問題．正五角形に同じサイズの正方形を（問題文の図に書いてある詰め方で）8個詰めるとき，詰め込める最大の正方形の大きさを求める，みたいな問題．
    • 本番では避けていた（というかほとんど読んでない．Standingsみても手を付けているチームは少なかった）．二分探索で頑張るか，手計算で頑張るか．めんどくさそう．

結果

A,B,D,E,F,G,H,I,Kの9完遅解きで4位でした．ちなみにI問題のFA＆唯一のAC．150ドルGET．日本人のスポンサー（？）の方と一緒に写真を撮った．
1位も9完だったので，僕がCを書いていれば1位だったと思うとチームのみんなには申し訳ないと思っていた．
D の誤読がなければ確実に3位には入れたため，結果を見たときは嬉しさと同時に悔しさが残る…．まあ結果論だし，今の結果に納得はしています．

旅程まとめ

7日（前々日）
  • 飛行機は8日朝だが，家から間に合わないことに気がつく．
  • 空港近くの友人宅に泊めてもらう．夜ふかしした．
8日（前日）
  • 7時ぐらいに空港着．
  • 受付でWAが生える．向こうのミスっぽいが焦る．
  • なんかいい感じにいけるらしいのでセーフ．幸先悪いなあ．（こういうことがあるので早めに空港には行きましょう
  • 出国時に荷物検査で引っかかる．筆箱にカッターナイフがあるのを忘れていた．
  • とりあえず北京につく．乗り継ぎが8時間ぐらいあった．（乗り継ぎが長いとつらいので，飛行機のチケットは早めに取りましょうね．
  • ミャンマーには結局24時ぐらいについた．ICPCの人たちが出迎えてくれた．
  • タクシーを捕まえてくれたんだけど，早速車の治安が悪い．空港前がすでにカオス．
  • ホテル着．さすがにすぐに寝る．
  • 結局この日は友人宅での朝ごはんと，機内食 x 2 しか食べていない．
9日（Practice当日）
  • 6時半おき．早すぎるからもっと遅くしてほしい．
  • ホテルにバスが迎えに来てくれる．
  • 相変わらず車の治安がアレ．10秒に一回はクラクションがなる．
  • 大学着．大学内に普通に犬が徘徊していて笑う．
  • Practiceを適当にやる（内容は上に書きました）
  • なんか向こうが観光の手配もしてくれるらしい．シュエダゴン・パゴダに案内される．
  • でかい．修行僧がタブレットでなんかしていて，すごいなあとなる（語彙力が無い
  • 外の露店の揚げ物を買って食べる(2000キャットぐらい．日本円換算はだいたい10分の1すれば良いです．つまり200円．）美味しいが油が強かった．（胸焼けした
    • 果物とかはお腹をこわす可能性があるらしいので，怖い人はやめておくのがよいです．
  • ホテルに帰る．近くに外国人向けの店があったのでそこで晩御飯（14000キャット？）．さすがに美味しかった．
  • チームで若干明日の戦略を考えて，早めに寝る．
10日（コンテスト本番）
  • 6時15分起き．なんでこんなに早いんだ．
  • 同じホテルの他の人々がこない．競プロerは万国共通で集合が下手らしい（要出典）．20分ぐらい遅れる．
  • 2件目のホテルでも人々が集合時間にこない．頼むよ〜．
  • 予定より大幅に遅れて大学につくとコーヒーとパンが配られる．おいしいパンだった．
  • コンテスト開始時間がガバガバになっているのに何のアナウンスもない．大丈夫か？
  • 待っていたら唐突に大声でカウントダウンが始まる．カウントダウン開始が何の前触れもなく3秒前に行われるってどうなんだ．
  • コンテストの内容は上に書いた．
  • コンテスト終了後は大学でお昼ご飯が配られる．まあまあ美味しかった．
  • その後は観光に連れて行ってくれる．Taukkyan War Cemetery という共同墓地とショッピングモール．
    • 太平洋戦争時の連合国軍戦没者の共同墓地っぽい？
  • 墓地なのに沢山の人がにこやかに写真を取っていて少し驚く．
  • ショッピングモールで人権を得る（SIMを買う）
  • ショッピングモール付近は車の治安がやばすぎて，もはや僕達を回収してくれるバスがどこにいるのかわからない．
  • 結局出発が30分ぐらい遅れる．しかも一部の人の回収に失敗していて草．そりゃそうなるわ．
  • 閉会式の会場につく．めっちゃいいホテル．
  • 席が余っていなくて，VIP席に案内されてしまう．しかも主催者テーブルっぽい．
  • 偉い人の話を聞いてリザルトを見る．結構盛り上がっていた．
  • その後は突然POPなミュージックとともに前で踊りが始まる．VIP席（舞台に近い）にいたせいか巻き込まれて踊ることになった．
  • ビュッフェ形式のはずなんだけど，VIP席に座っているのでホテルの人が料理を運んできてくれる．最高に運がいい．
  • 当然料理は美味しかった．
  • 主催者の人とちょっと話をする．日本の東京は苦手らしい（人が多いため）．わかるなあ．
  • あとは適当に写真を取ったりしてホテルに帰る．早起きする必要がないので適当にすごす．
11日
  • 今日は何もないので飛行機の時間までブラブラすることに．
  • ホテルまでICPCの人たちが迎え（タクシー）に来てくれるらしいので，チェックアウトした後またホテルに戻る必要があった．
  • 13時ぐらいにチェックアウト．荷物を預けてダウンタウンの方へ．
  • もちろんタクシーを捕まえる．8000キャットで乗せてくれた．
  • 前日に，お土産を買う店をコーチが聞いてくれたらしいが，月曜日が定休日らしい．運が悪い．
  • 中心部に近づくと，車の量が激しくなってきた．
  • 日本人もよく行くという，Monsoon という店でご飯を食べる．チキンカレー(6800キャット) とお酒(5000キャット)を食べた．美味しい．
  • その後は適当にぶらつく．
  • しかし暑すぎて辛くなってきたため，適当なカフェに入ってスムージー(2500キャット)を頼んで良い時間まで粘る
  • その後はスーパーを見つけてお土産を買って帰る．大体 3000 キャットぐらい使った．
  • 変なオジサンに「オンナノコどう？」って聞かれた．（いら）ないです．
  • 晩御飯は一風堂を見つけてしまったので吸引される．美味しい．
  • 一部日本語で接客していた．「イラッシャイマセ」「麺カタメ」「カエダマ」など．
  • タクシーを捕まえてホテルまで送ってもらう．1つ目のタクシーはなぜか理由も話さず断られてしまったらしいが，2つ目のタクシーは5000キャットで乗せてくれた．
  • 飛行機にのって爆睡する（機内食を逃す
12日
  • 朝6時北京着．ミャンマーとの寒暖差40度ぐらいありそう．凍え死にそうになる
  • 8時40分北京発，機内食を食べて関空へ．
  • 12時30分ぐらいに関空着．もちろん爆睡していた．
  • あとは自宅へ帰って終わり

感想

・ミャンマーの人たちはみんな優しかった．普段から温かく接してくれる．
・コンテストはある意味楽しかったけど，まだおすすめはしにくいです．エスパーしてWFとか狙うならアリかな．僕らでも狙えたぐらいだし．
・コンテスト環境自体は悪くなかったです．
・あとは治安ですが，変なところに行かなければ，治安は悪いとは感じなかったです．
・車の運転はみんな荒いです．バスとか一般車両とか関係ない．むしろバスのほうが荒いんでは…．というわけで酔い止めがあると安心かも？
・色んな意味で他ではできない体験だと思うので，興味がある人は参加してみてはどうでしょうか？

AOJ 0537 Bingo

AOJ 競プロ

問題文

http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=0537

解説

言い換えると
$1 \leq a_1 < a_2 < \ldots < a_n \leq M $
$a_1 + a_2 + \ldots + a_n = S$
をみたす $a_n$ の作り方を求める問題で，O(NMS) の解法はすぐわかると思いますが，実は O(NS) で解けます．
分割数のイメージでやるとよいです．DPでやることには変わりません．
dp[i][j] := i 個の異なる数（M以下の数）で，総和を j にする組み合わせ
とすると，遷移は
dp[i][j] = dp[i - 1][j - i] + dp[i][j - i] - dp[i - 1][j - M - 1]
となります．
第1項は，すでに出来ている i - 1個のそれぞれに 1 を加算し，i 番目に 1 を付け加えるという操作を表します．
第２項は，すでに出来ている i 個の数のそれぞれに 1 を加算してできるという意味を表します．
最後の項は，1を加算したことで M を超えるような場合の数を取り除くためのものです．dp[i][j] で M を超えるとしたら，遷移の仕方からその値は M + 1 で，かつその1つだけです．そのような場合の数は，他の i - 1 個の総和が j - M - 1 で，かつ M を超えるものが無い場合なので，dp[i - 1][j - M - 1] に対応します．

以上で O(NS) で解けました．

ソースコード

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

using pii = pair<int, int>;
using vi = vector<int>;
using ll = long long;

constexpr int mod = 1e9 + 7;

int main() {
    int N, M, S;
    while(cin >> N >> M >> S, N) {
        vector<vector<int>> dp(N * N + 1, vector<int>(S + 1));
        dp[0][0] = 1;
        for(int i = 1; i <= N * N; ++i) {
            for(int j = 0; j <= S; ++j) {
                if(i <= j) {
                    dp[i][j] += dp[i][j - i] + dp[i - 1][j - i];
                }
                if(j - M - 1 >= 0) {
                    dp[i][j] -= dp[i - 1][j - M - 1];
                }
                dp[i][j] = (dp[i][j] + mod) % mod;
            }
        }
        cout << dp[N * N][S] << endl;
    }
}

感想

制約を N <= 100, S <= 10^5, M <= 10^5 にするだけで解けなくなる人が出てきそう．

AOJ 1281 The Morning after Halloween

AOJ 競プロ

問題文

http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=1281

解法

この問題はやるだけなんですが，TLEとMLEをうまく回避するのが大切な問題です．定数倍遅くなりそうな部分はできるだけ排除していく必要があります．
基本BFSをやっていくだけなのですが，最短距離を short で持つようにするとMLEが防げます．
遷移する部分は，とりあえず3つ文字があると仮定した 5^3 のループ（動かない＋4方向に動く）を書いて，適宜つじつまを合わせる実装が楽だと思います．
移動先が壁かどうかの判定を，面倒だからと一番深いループの位置でやるとTLEするので，各文字の遷移先を決めるループごとに枝刈りしないといけません．

あとは変なことを書かなければぎりぎり通ると思います（白目）．

ソースコード

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

using pii = pair<int, int>;

constexpr int dx[5] = {0, 0, 1, 0, -1};
constexpr int dy[5] = {0, 1, 0, -1, 0};

short d[256][256][256];

void init() {
    for(int i = 0; i < 256; ++i) {
        for(int j = 0; j < 256; ++j) {
            for(int k = 0; k < 256; ++k) {
                d[i][j][k] = 10000;
            }
        }
    }
}

bool move_check(int prev1, int to1, int prev2, int to2) {
    return to1 != to2 && (prev1 != to2 || prev2 != to1);
}

int main() {
    int w, h, n;
    while(cin >> w >> h >> n, n) {
        init();
        vector<string> c(h);
        vector<pii> cs1, cs2;
        cin.ignore(1000, '\n');
        for(int i = 0; i < h; ++i) {
            getline(cin, c[i]);
            for(int j = 0; j < w; ++j) {
                if('a' <= c[i][j] && c[i][j] <= 'z') {
                    cs1.emplace_back(c[i][j], i * w + j);
                }
                if('A' <= c[i][j] && c[i][j] <= 'Z') {
                    cs2.emplace_back(c[i][j], i * w + j);
                }
            }
        }
        sort(begin(cs1), end(cs1));
        sort(begin(cs2), end(cs2));
        array<int, 3> s = {255, 255, 255}, g = {255, 255, 255};
        for(int i = 0; i < n; ++i) {
            s[i] = cs1[i].second;
            g[i] = cs2[i].second;
        }

        queue<pair<array<int, 3>, short>> que;
        d[s[0]][s[1]][s[2]] = 0;
        que.emplace(s, 0);
        int res = 0;
        while(!que.empty()) {
            auto now = que.front().first;
            auto cost = que.front().second;
            que.pop();
            if(now == g) {
                res = cost;
                break;
            }
            for(int i = 0; i < 5; ++i) {
                int ny0 = now[0] / w + dy[i], nx0 = (now[0] % w) + dx[i];
                if(c[ny0][nx0] == '#') {
                    continue;
                }
                for(int j = 0; j < 5; ++j) {
                    int ny1 = now[1] / w + dy[j], nx1 = (now[1] % w) + dx[j];
                    if(n >= 2 && c[ny1][nx1] == '#') {
                        continue;
                    }
                    for(int k = 0; k < 5; ++k) {
                        int ny2 = now[2] / w + dy[k], nx2 = (now[2] % w) + dx[k];
                        if(n == 3 && c[ny2][nx2] == '#') {
                            continue;
                        }
                        array<int, 3> nxt = {ny0 * w + nx0,
                                             (n >= 2 ? ny1 * w + nx1 : 255),
                                             (n == 3 ? ny2 * w + nx2 : 255)};
                        bool move_ok = true;
                        for(int l = 0; n != 1 && l < n; ++l) {
                            move_ok &= move_check(now[l], nxt[l], now[(l + 1) % n], nxt[(l + 1) % n]);
                        }
                        if(move_ok && d[nxt[0]][nxt[1]][nxt[2]] == 10000) {
                            d[nxt[0]][nxt[1]][nxt[2]] = cost + 1;
                            que.emplace(nxt, cost + 1);
                        }
                    }
                }
            }
        }
        cout << res << endl;
    }
}

感想

まあ，最初サボりすぎてTLE食らったんですけどね．実装はきれいに書けたほうだと思う．（速度が早いとは言ってない）
ちなみに 5.50 s / 8.00 s です．あぶねえな．
ケースによるけど，n が小さいならループを回さないようにしたほうが早くはなると思う．でも全部 n == 3 だと意味ないからそういうふうには書かなかった．

A* とか 両側探索だと多少早いのかな？