ICPC Domestic G: 数式探し

a * b + c * d * eみたいに+と*のみからなる式が与えられた時に,いろんな部分文字列を高速に評価するのが本質です。

こういう変なのはad-hocにやろうとすると大体大変だしバグると詰むんですが,SegTreeで強引にやってしまえばノード2個のマージに落とせるため,(SegTreeが思考停止で書けるという前提のもとでは)思考停止で掛けてそこまでバグりません

↓頑張ってコメントを足したコードです

#include <bits/stdc++.h>

using namespace std;
using ll = long long;
template<class T> using V = vector<T>;
template<class T> using VV = V<V<T>>;
constexpr ll TEN(int n) { return (n == 0) ? 1 : 10 * TEN(n-1); }

//こういうのはenumを使ったほうがいいのかもしれません
const int PLUS = -1; 
const int MUL = -2;

const ll INF = TEN(9) + TEN(4);


// 数式の情報を表すノードです
struct D {
    // 数式の中に+が入っていないかのフラグです。これがtrueだと a * b * c * ... * z みたいに単一の項であることを表します    
    bool f = true;

    // この数式は l + m + rですよという値です。f = trueの場合mに値が入っていて,l, rは0です
    ll l = 0, m = 0, r = 0;
};


// 根性
D merge(D l, D r, int op) {
    D d;
    if (op == PLUS) {
        d.f = false;
        if (l.f && r.f) {
            d.l = l.m;
            d.r = r.m;
            d.m = 0;
        } else if (l.f) {
            d.l = l.m;
            d.m = min(INF, r.l + r.m);
            d.r = r.r;
        } else if (r.f) {
            d.l = l.l;
            d.m = min(INF, l.m + l.r);
            d.r = r.m;
        } else {
            d.l = l.l;
            d.m = min(INF, l.m + l.r + r.l + r.m);
            d.r = r.r;
        }
    } else {
        assert(op == MUL);
        d.f = l.f && r.f;
        if (l.f && r.f) {
            d.l = 0;
            d.m = min(INF, l.m * r.m);
            d.r = 0;
        } else if (l.f) {
            d.l = min(INF, l.m * r.l);
            d.m = r.m;
            d.r = r.r;            
        } else if (r.f) {
            d.l = l.l;
            d.m = l.m;
            d.r = min(INF, l.r * r.m);
        } else {
            // 両方単一項ではなくて,l * rとやる場合です。
            // l.l + l.m + l.r * r.l + r.m + r.r なので,l.m ~ r.mが圧縮できて以下のようになります
            d.l = l.l;
            d.m = min(INF, l.m + l.r * r.l + r.m);
            d.r = r.r;
        }
    }
    return d;
}


// SegTreeです,僕は定数倍が必要ないならポインタベースのほうが書きやすいと強硬に主張しています
// このSegTreeの要素数は数字の個数で,葉以外のノードがそれぞれopを持っています
struct Node {
    using NP = Node*;
    NP l, r; int sz;
    D d; // そのノードの数式の値
    int op; // 葉以外が持っていて,PLUSかMULです

    Node(int _sz, const V<ll> &v, int off = 0) : sz(_sz) {
        if (sz == 1) {
            assert(v[off] > 0);
            d = D{true, 0, v[off], 0};
            return;
        }
        int lsz = sz/2;
        l = new Node(lsz, v, off);
        r = new Node(sz-lsz, v, off + 2*lsz);
        op = v[off + 2*lsz-1];//
        assert(op == MUL || op == PLUS);
        d = merge(l->d, r->d, op);
    }

    // a番目の数字からb-1番目の数字までの数式を取り出して,評価します
    D get(int a, int b) {
        // 単位元が無いので単位元がないタイプのsegtreeを書きましょう
        if (b <= 0 || sz <= a) assert(false);
        if (a <= 0 && sz <= b) return d;
        if (b <= sz/2) return l->get(a, b);
        if (sz/2 <= a) return r->get(a-sz/2, b-sz/2);
        D ld = l->get(a, b);
        D rd = r->get(a-sz/2, b-sz/2);
        return merge(ld, rd, op);
    }
};


ll n;
string s;
int p;

ll ans; // グローバル変数で,答えはここにどんどん足しこまれていきます


// vは{数字, op, 数字, op, 数字, op, 数字, ..., 数字}みたいになっています
// 副作用として答えをansに足しこんで,最後に数式全体を評価した値を返します
ll solve2(V<ll> v) {
    assert(v.size() % 2);
    int m = int(v.size()) / 2 + 1; // 数字の個数
    auto tr = new Node(m, v);

    //a番目の数字からb-1番目の数字を評価して返す
    auto eval = [&](int a, int b) {
        auto d = tr->get(a, b);
        return min(INF, d.l + d.m + d.r);
    };
    for (int i = 0; i < m; i++) {
        int l, r, a, b;
        l = i, r = m+1;
        while (r-l > 1) {
            int md = (l+r)/2;
            if (eval(i, md) < n) {
                l = md;
            } else {
                r = md;
            }
        }
        a = r;
        l = i; r = m+1;
        while (r-l > 1) {
            int md = (l+r)/2;
            if (eval(i, md) <= n) {
                l = md;
            } else {
                r = md;
            }
        }
        b = r;
        ans += b-a;
    }
    return eval(0, m);
}

// 数式全体を評価した値を返します,最後に呼んでいるsolve2(v)の内側でansに答えが足し込まれます
ll solve() {
    V<ll> v;
    while (p != int(s.size()) && s[p] != ')') {
        char c = s[p];
        if (c == '(') {
            p++;
            v.push_back(solve());
            assert(s[p] == ')'); p++;
            continue;
        }
        if (isdigit(c)) {
            p++;
            v.push_back(c - '0');
            continue;
        }
        if (c == '*') {
            p++;
            v.push_back(MUL);
            continue;
        }
        if (c == '+') {
            p++;
            v.push_back(PLUS);
            continue;
        }
        assert(false);
    }
    return solve2(v);
}

bool first() {
    cin >> n;
    if (!n) return false;
    cin >> s; p = 0;

    ans = 0;
    solve();
    cout << ans << endl;
    return true;
}

int main() {
    while (first()) {}
}

AGC 025

A

うん(ループを1からn-2まで回しWA)

B

A, A+B, B, 0 → A, Bが独立
 → AC

C

数直線をジグザグして移動距離の総和を考える →区間が全部点だったら?
 → ARC 087 Fに酷似,各[i, i+1]ごとに左右の個数に注目すると自明な上界が出る
  →区間区間だったら?    →かぶってる区間を取り除けば同じ

D

解決不可能

F

見るからに得意,線形 or 軽いlog?

操作の経過を想像 →(1, 1)が上の桁へ登っていく,下の桁から確定されていく

加算, log →加算器?分割統治?

分割統治するとどうなる?
→長さLの区間は繰り上がりを無視すると高々L回の操作で安定する
 →すごい分割統治っぽい性質
  →繰り上がりを無視してシミュレーションしたあとに繰り上がり操作をしても不変,とかだとすごい嬉しいなあ
   →不変でした

安定した数列に対して,繰り上がりを足す,を高速にシュミレートすればいい →操作の経過を想像
 →非(0, 0)のペアってそんなに増えなさそう
  →非(0, 0)のペアの個数でならし計算量?
   →ならせました

CF #485

Um_nik回

A

制約がO((N+M)K)と言っている
→ K回幅優先できそうだしこれだろう
 → 一応sortじゃなくてnth_element使っとくか(logが消えます)

B

オッ乱択
→ ランダムスワップの回数が増えるとどうなる?
 → a[i] = iの要素数が減っていくんじゃないか?
  → とりあえず実験してみるか
   → いや3nはともかく7n+1ってなんだよ
    → なんで7n回じゃないんだ?+1回でなんか本質的に変わるのか?偶奇?
     → そういえばswapは置換なので偶置換奇置換という概念があった

C

こういう2n頂点4n辺(n=20ぐらい)のグラフを仮想的に考えてやるやつは,結構ロシア合宿とかで見る
→ 大体本質的に見る必要のある辺だけ注目したり,追加頂点を作って辺をまとめたりする
 → 今回は後者っぽい?うまくまとめたいね
  → 00110から辺を貼れる頂点は??00?
   → ?が出てきたので高速ゼータ変換系を疑う,??001みたいに?を途中まで1に変換したやつを状態に持つ?
    → できそうだけど,よく考えると状態数n * 2nってメモリの確保すらしんどくないか?
     → ということは状態数O(2n)のままでなんとかなるんだろう

状態数O(2n)でなんとかやりたい → ??00?は流石に用意しないとどうしようもなくない?  → ?0の混合だけでなんとかなる?   → (??00? -> 0?00?, ?000?, ??000, 11001)みたいな遷移かー

D

だいたいlogとか考えると解ける?
→どうやっても3xとの比較が必要じゃない?
 →やめるか

E

gcd(a_i, x)の積
→ a_i, xの値が107と中途半端
 → 約数の個数系?

まずパスクエリをどう分解する?
→ 逆元は?存在するね
 → オイラーツアー?
  → オイラーツアーとか木を状態持ちながらdfsとかでいいね

整理
→ 数が追加されたり削除されたりクエリが飛んできたりする
 → 適時gcd(a_i, x)の積を求めよ

数が追加された時,クエリxの答えはどうなる?
→ 6を追加すると?12を追加すると?4を追加すると?(実験)
 →もしかして素因数ごとに分解するだけ?

実装が大変
→ところでジャッジ壊れてない?
 →うーんもうめちゃくちゃ

D言語の競技プログラミング用ライブラリを作ってみた

タイトルに反して実は作り始めたのは1.5年ぐらい前ですが…

結構安定してきたんで紹介をします。でも使うのはオススメできないかも(いろいろ壊れてるかもしれないため)。要するにせっかく作ったから見てくれというやつです。

準備

  • まずD言語コンパイラをインストールします
  • D言語のパッケージ管理システムdubをインストールします(https://code.dlang.org/)

  • お好きなところにA.dを作って,sample.dをコピペします(このリポジトリをcloneする必要はないです)

  • dub build --single A.dと打ちます

  • ./Aができない→どうしてこんなことに…
  • ./Aができた→こちらを想定します

sample.dは以下のようになっているはずです

/+ dub.sdl:
    name "A"
    dependency "dunkelheit" version="1.0.0"
+/

import std.stdio, std.algorithm, std.range, std.conv;
import dkh.foundation, dkh.scanner;

int main() {
    Scanner sc = new Scanner(stdin);
    scope(exit) assert(!sc.hasNext);
    int a, b;
    int[] c;
    sc.read(a, b, c);
    writeln(a, b, c);
    return 0;
}

このコードは,整数2個と配列1個を入力して出力するコードです。例えば'./A'を実行して

1 2
3 4 5

と入力すれば,

12[3, 4, 5]

と出力されるはずです

dependency "dunkelheit" version="1.0.0"でversion1.0.0を指定しています。もし今後後方互換性壊したりしても,とりあえずv1.0.0を指定しておけばv1.0.0が動く!すごい!

ソースコード結合

提出するときにはソースコードを1つにする必要があります。ここで

dub run dunkelheit:combine -- -i=A.d -o=A_submit.d -c -u

と打つと,A_submit.dが出来ます。これをそのまま提出すれば動くはずです。多分。

ドキュメント

ライブラリにはドキュメントがついています(ついていない部分もあります)。 https://yosupo06.github.io/dunkelheit/で見ることが出来ます。

機能紹介

いくつか機能を紹介します。

Scanner(dkh.scanner)

一番使います。

サンプルのように読み込みたいものを全部引数に入れてsc.read()を呼べばよいです。

scope(exit)はこのスコープ(= int main)を抜けたときに実行するという意味で,sc.hasNextは全部読み込み終わったかを返すので,要するにscope(exit) assert(!sc.hasNext)はmain関数を抜けたときに全部読み込み終わってるかチェックしてくれます。

また,配列型は,「次のトークンから行が変わるまで全部読み込む」をやるので,

N M
a_1, a_2, ..., a_N

みたいなのを読み込みたいときに便利です(sc.read(N, M, a))。

N M
a_1 b_1
a_2 b_2
:
a_N b_N

みたいなのはどうしようもないです。

Segtree(dkh.container.segtree)

やっぱりライブラリと言ったらsegtree, segtreeと言ったらライブラリみたいなところがあるよね。

D言語はラムダを短くかけるので,

auto seg = LazySeg!(int, int, (a, b) => max(a, b), (a, b) => a+b, (a, b) => a+b, 0, 0)(n); でstarry sky treeが出来ます。

auto seg = LazySeg!(int, int, max, "a+b", "a+b", 0, 0)(n) とも書けます。

dkh.datastructure.segtree のexamplesに詳しく書いています。seg[0..3].sum()区間取得とかseg[0..2] += 10区間加算とかお気に入り(自画自賛)

modint(dkh.modint)

scannerの次ぐらいに使います。自動mod取り構造体とも呼ばれます。

alias Mint = ModInt!(10^^9 + 7)

で,

Mint a = Mint(10);
Mint b = Mint(11);
writeln(a+b); //21
writeln(a-b); //1000000006
writeln(a*b); // 110
writeln(a/b); // 逆元も
writeln(a^^b); // べき乗も!

のように使えます。また,dkh.numeric.convolutionをimportすればfftも使えます

Mint[] a, b;
writeln(multiply(a, b));

とか

CI

D言語にはunittestを書きやすい支援機能がついているので,使いました。 githubにpushするたびにdroneが走って,いろんなバージョンでチェックしてくれます。

f:id:yosupo:20180529021956p:plain

↑こんな感じ

なので一度潰したバクは(理論上)再発しないですね!安心!

なお,CIにはhttps://github.com/drone/droneを使ってます,便利

CF Avito Code Challenge 2018

AB

はい

C

ちょっとすき,条件がつよいから結構Noが多そう
→サンプルの図を見ると次数>=3が2個以上がたいへんあやしく

D

ちょっとすき,値が大きい + 2進数を感じさせる演算 + maximize
→これAGCで見た
 →上bitから貪欲するとDPです
  →250(は?)(きらい(手のひら返し))

E

すき →クエリを選んで,全体maxをxにする?
 →まずどれかの要素がxにならないといけない
  →よく考えるとどれかの要素がxにできたら全体maxもxにできる
   →全体maxと言いつつ,要素ごとにほとんど独立の問題

要素ごとに独立に考えられる
→90度回転待ったなし
 →戻したい雰囲気がある…あるね?
  →bool DPで戻したいときはmodにするのが鉄板で

G

問題を想像する
→かなりならしを感じる
 →ならしたい…ならしたくない?ならせるね

ならせる
→ここから方針を間違えてしまい…

F

円環はダメ
→列に展開したい…
 → bを3週させて(b[i]-L, b[i], b[i]+L)考えると…?

自由度が一見高いように見えて,さすがにminimizeしてることとか使うと自由度が下がるはず
→どうやらbをrotateしてa[i]-b[i]みたいな感じで結ぶのしか考えなくて良くなる
 →O(N2)

この2個+二分探索をまとめると?
→ウニウニいい感じに動いていきます,完全マッチング作れますか,マッチングは一個ずつ進んでいくパターンしか考えなくていい
 →a[0]と結ぶやつを全部試して,同時並行シミュレーション?
  →できそう
   →本当に通るかな?

ARC 098

いつもはvmware+linux+vscodeで出ていたんだけど,今回はwindows+wsl+clionで参加(したかった)

F

お金を配りながら移動していく,ただし移動するときには頂点ごとにしきい値がある
→サンプル1を書いてみて想像をする
 →どうやらお金はありすぎて困ることはない
  →二分探索?

二分探索できるのでとりあえず二分探索してみる(logは定数なため)
→最初のお金Zが決まるから可能か?を求める
 →お金を配ると結局どうなる?
  →移動可能範囲が狭まっていく
   →移動可能な範囲が狭まっていくなか,うまく全部の頂点を辿れるか?
    →ものがstrictに減っていく時は逆から考えると良い(一般に減らしていくより増やしていくほうが簡単なため)

ゴールから考えるとどうなる?
→最初のお金が決まっているため最後のお金も当然決まる
 →お金を頂点から回収していって,だんだん移動可能範囲が増えていく
  →どうやら多項式にはなった(TLEだけど)

どうやらゴール位置が重要っぽい
→例えばゴール位置を決め打つと簡単に計算できるか?
 →priority_queueとか使って探索していくとうまくやると行けそう
  →じゃあどうやって複数のゴール位置についてやる?
   →ゴール位置が複数あると,複数位置からじわじわ探索が広がっていって,衝突したらmergeみたいな雰囲気がありそう
    →データ構造をマージする一般的なテク?

制約もそれっぽいし,解法はデータ構造をマージする一般的なテクだろうと想像がつく
→log 3個?
 →流石にデマパートはlog 2個からは落とせなそう(なんか隣のやつをsortして持っておくみたいな操作が必要そう),じゃあ二分探索やめるしかない?
  →二分探索やめるか

二分探索をやめる
→最初に持っている額を決め打てない
 →最初は0円スタートで,足りなくなるたびに適時無からお金を生成する感じで

まとめる
→ゴールから考える
→最初は0円スタート
→それぞれの頂点について,「もしこの頂点がゴールだったら?」を並列にシミュレーションする感じ
 →シミュレーションそれぞれについて,できる限り進めて,進まなくなったら「無からお金をいくら生成すればシミュレーション進みます」を計算してpriority_queueに突っ込む,それが最小の額だけ無からお金を生成して,シミュレーションを進める
  →これを繰り返せばなんとかなりそう,色々大変だけど計算量もなんとかなる?
   →AC

C

累積和流行ってる?

D

0いるか?僕はいらないと思います

E

えー全然わからない,おわりです →よく考える
 →最大と最小の両方に自由度があるのなに?
  →よくみるとN=2000
   →最大か最小どっちか固定して,それぞれO(N)に違いない,自由度1ならなんとかなるだろ

どっちを固定したい?
→最大固定はよくわからないけど,最小固定はうれしさがある(部分列にいくつかの要素を含められないという条件になるため)

最小を固定してみる
→いくつかの要素が取れなくなる
 →要するに数列が分解される
  →いくつかの数列が与えられる,取り除いたやつの最大値を最小化

可能かどうかの判定は?
→数列の要素数から簡単にわかる

最大値の最小化は?
→そもそも最小値は絶対取り除けるんだから,最大値の最小化もクソもなくないか?
 →[1], [100, 100, 100, 100]とかになると1を取れなくなるのか
  →連結成分ごとに取り除ける個数が決まっていて,そのなかではかなり自由?(APC Dを思い出すなあ(唐突な宣伝))
   →正しそう

AGC 024

E

解けません,全然解けません,おわりです

D

問題の理解が大変

とりあえず最小値を求めないといけない
→AGCで無向木の意味不明な性質を求められたらとりあえず直径に注目しろという法則があり
 →(直径+1)/2色は絶対必要なことがわかる
  →なので(直径+1)/2色で塗り分けられることがわかる(理由: AGC)

最小値は求まったので(求まったとは?)葉の個数を数えればいい
→よくわからないよくわからない
 →サンプルを実際に書いて眺める
  →なんか深さiはa_i分木みたいなのを作る?
   →ちょうど答えがいい感じのサイズ(250)になったので,正しい(強気)

F

読解が大変
→高速ゼータ変換部分列版をしろという問題
 →高速ゼータ変換を一般化した論文があるんですが,それだとうまくいかない
  →そもそも何がしたいのか?
   →文字列が1個あったとき,部分列を1回ずつ列挙する方法は?(ここで経由する状態がシンプルだといい)
    →普通に先頭から0か1をとっていけばいいですね
     →AC

A

A問題なのにサンプルの出力にUnfairが無いため,Unfairを出力することはない

とりあえず適当に手で試す
→ああ-1倍されるのか
 →AC

B

AtCoderでこれと似たような問題で,残すやつに注目するとLISという問題があったはず
→残すやつに注目すると?
 →ああ単調増加
  →AC

C

二次元平面(X: i, Y: a_i)を想像する
→階段がはやせる,階段しかはやせない
 →階段をはやして数列を作れるか?
  →a[i]より2以上a[i+1]の方が大きかったらダメ,あとa_1 != 0でもダメ(こっちはサンプルからわかる)
   →これを満たしていれば作れる,作り方も自然なので数えるのは簡単
    →AC