TCO18 R3A Medium ProductThreshold

http://community.topcoder.com/stat?c=problem_statement&pm=14949 TCO18 Algorithm Round 3A Editorials - Topcoder 2.0

問題

積がlimit以下になるような連続した部分列の数を求めよ

解法

0を含む区間は条件を満たすので、0を含む区間だけ先に計算し、以後0を含まない区間のみ計算する。 ある区間の積を考えたときに条件を満たさない可能性があるのは区間の積が正のときだけ。

cnt(s,i)[0,i)の積の符号がsとなるiの数とする。 積が負になる場合は必ずlimit以下となるので、s[0,i)の積の符号とすると、積の絶対値がlimit超えないように尺取りしつつ\displaystyle \sum_{l,r} cnt(-s,r)+cnt(s,r)-cnt(s,l)で条件を満たす区間の数が求まる。

一言

配列は乱数で生成するので手を抜いても大丈夫かと思ったが駄目なケースがあった。

package main.tasks;

import java.util.*;

public class ProductThreshold {
    public long subarrayCount(int N, int limit, int[] Aprefix, int spread, int offset) {
        long[] ary = new long[N];
        for (int i = 0; i < Aprefix.length; i++) {
            ary[i] = Aprefix[i];
        }
        long seed = Math.abs(ary[Aprefix.length - 1]);
        for (int i = Aprefix.length; i < N; i++) {
            seed = (seed * 1103515245 + 12345) & ((1L<<31)-1);
            ary[i] = seed % spread + offset;
        }
        return solve(N, limit, ary);
    }

    long solve(int N, int limit, long[] ary) {
        List<Integer> zero = new ArrayList<>();
        zero.add(-1);
        for (int i = 0; i < N; i++) {
            if (ary[i] == 0) zero.add(i);
        }
        long ans = 0;
        for (int idx = 1; idx < zero.size(); idx++) {
            long i = zero.get(idx - 1);
            long j = zero.get(idx);
            long k = zero.get(idx);
            ans += (N - k) * (j - i);
        }

        sum = new long[2][N+1];
        zero.add(N);
        for (int i = 0; i + 1 < zero.size(); i++) {
            ans += solve(zero.get(i) + 1, zero.get(i + 1), limit, ary);
        }
        return ans;
    }

    long[][] sum;
    long solve(int l, int r, int limit, long[] ary) {
        long ans = 0;
        sum[0][l] = sum[1][l] = 0;
        long mul = 1;
        for (int i = l, j = l, p = 0; j < r; j++) {
            sum[p][j+1]++;
            for (int k = 0; k < 2; k++) sum[k][j+1] += sum[k][j];
            if (ary[j] < 0) p ^= 1;
            mul *= ary[j];
            for (; Math.abs(mul) > limit; i++) {
                mul /= ary[i];
            }
            ans += sum[p^1][j+1] + sum[p][j+1] - sum[p][i];
        }
        return ans;
    }

    static void dump(Object... o) { System.err.println(Arrays.deepToString(o)); }
}

ARC094 D - Worst Case

本番解けず。 1ステップでも考察入ると解けなくなるのは克服したい。

解法

自分より上位にn人存在しうるか、を二分探索して解いた。この問題は

  • n人の人が上位にいるとき、自分の順位を除いて、1回目に1位だった人は2回目n位、1回目2位だった人は2回目n-1位…という順位をとるのが最善

という単純な事実に気づけば後は二分探索で簡単に答えが求まる。 n人全員調べるとTLEなので、順位の積が最大になるのは真ん中あたりの人なので真ん中あたりの人だけ調べればいい。

Submission #2787487 - AtCoder Regular Contest 094

TCO18 MM R1 RoadsAndJunctions

方針

序盤

置く候補を全探索し、置いたときにスコアが大きくなる順に置いて行った。 盤面がでかくて全探索できないときは探索する点を間引いた。

終盤

  1. 焼き鈍しを9400ms実行。遷移は以下の3つで、失敗確率0での解を求めた。

    • ランダムにjunctionを置く
    • 隣へ移動する
    • junctionの削除
  2. 失敗確率も考慮し、期待値が低くなるように1.で求めた点を多重化

反省点

  • yoursの期待値の最小化ではなく、(yours^-2)の期待値を最大化をする発想がなかった
  • 期待値の計算が適当
  • GCEでテストできるようにしていたが、環境構築に失敗していて、最終日までその失敗に気づかなかった(ずっと初期に書いたコードでテストされていた、途中でおかしいなとは思ったんですけどね…)
  • パラメータの調整の時間がもったいなかった(雑で良いので自動調整できるようにしたい)

良かったところ

  • 1週間頑張れた(えらい)
  • EMSTのO(nlogn)解法のような、面白そうだけど効果が薄そうな実装はせず、より効果の高そうな方針の検討に時間を割いた。(初期頂点から構成されるMSTの最長辺の長さで平面を分割するお手軽高速化は行ったけど、よく考えると非常に遅くなるケースあるしやらないほうが良かったな…)

ローカル1000ケースで評価して焼き鈍し解法のほうがよかったのでそっちを投げたけど、standingsでは下がっていた。もしかしてTLEしていたのかな。

別に着るわけじゃないだけどTシャツ獲得を目標にして残りを頑張ろう。

復習

  • 自動調整できるようにする
  • 期待値計算の見直し
  • (yours^-2)の期待値を最大化をしてみる
  • コードの書き直し

GCJ 2018メモ

GCJは今年からサーバーサイドでジャッジされる形式に変わったのでJavaで参加するときのメモ。

  • クラス名はSolutionクラス
  • テスターは以下のような形で実行
python3 testing_tool.py java -cp ../bin Solution

アドベントカレンダーに合わせてローグライクゲームのAIを作るコンテスト開こうかと思いましたが頓挫しました

この記事は Competitive Programming Advent Calendar 2017 - Adventar の 21日目の記事として書かれました。 (診断人さん主催お疲れ様です&ありがとうございます)

(本文略)

まとめ

明日は kmjp_pc さんの記事です!楽しみですね!

OCamlのsetの実装の軽い紹介

Competitive Programming Advent Calendar 2016 - Adventar 1日目の記事です。

OCamlのsetがsplit/merge可能なAVL木になっているので、それの簡単な紹介です。 ちなみに、上の一文でこの記事の9割は終わったも同然です。

いくつかコアの関数を軽く紹介。計算量でh(t)って書いてあるのは、AVL木 t の高さのこと

balance

  • |h(n.l) - h(n.r)| = 3 のときに、木を回転させて |h(n.l) - h(n.r)| < 3 にする。
  • 計算量は O(1)
  • OCamlの実装だと、balという名前がついている
  • OCamlのset実装のAVLは、|Balance factor| <= 2 が不変条件になっているので注意。 gist.github.com

join(Node l, Node v, Node r)

  • l, v, r の並びでマージする関数
  • h(l), h(r) は任意で、h(v) = 1
  • 計算量は O(|h(l) - h(r)|)

gist.github.com

merge(Node l, Node r)

  • 2つのAVL木 l, r をマージする関数
  • 計算量は O(max(h(l), h(r)))
  • OCamlの実装だと、concatという名前がついている

gist.github.com

split(Node t, int k)

  • AVL木 t を [0,k), [k,size(n)) で分割する関数
  • 計算量は O(h(t))
    • (splitで再帰しながらjoinを呼んでおり一見 O(h(t)) に見えないが、joinしていく木の高さが徐々に高くなっていき、O(h1 + (h2 - h1) + (h3 - h2) + ...) = O(h(t)) となるのが面白い)

gist.github.com

性能

コピー&ペーストで、AVLとRBSTの性能を計測してみました。

問題
copypaste: コピー&ペースト - 2012年 日本情報オリンピック春合宿OJ | AtCoder
JOI 2011-2012 春季トレーニング合宿 問題

AVLによる解答 Submission #1000130 - 2012年 日本情報オリンピック春合宿OJ | AtCoder
RBSTによる解答 Submission #1000163 - 2012年 日本情報オリンピック春合宿OJ | AtCoder

AVLのほうがRBSTより速い(やけに実行速度が速いけど、昔よりジャッジが早くなってたりする?)

反省

  • 本当は図を入れたりして、どんな操作か丁寧に説明したかったのですが、間に合わず😞

明日の担当は tubo28 さんと snuke さんです。

参考(といいつつ自分はあんまり見てない)

Codeforces Round #372 (Div. 1) B. Complete The Graph

codeforces.com

Codeforces Round #372 Editorial - Codeforces

解法

辺のコストを1つあげると、最短経路のコストは0か1増加する。 広義単調増加なので、割り当てるコストの総和を2分探索で求めればよい。 辺のコストの割り当て方は適当でよい。

gist.github.com