hogecoder

つたじろう(Tsuta_J) 競技プログラミングの記録

four-t practice 2019 #01

2019 年 2 月 10 日 (日) に 2016 Dalian Regional を vjudge で解いたのでその時の立ち回りのメモです

メモ

開始。TAB が A を見て、rsk0315 が B を見て、自分が C を見る。B は正規表現ぽいらしい。自分も見てみてひと目で Shift-or っぽいと思ったがなぜか可能性を捨てる (は?) これ無限回反省すべきで、これのせいでペナルティがひどいことになった。

C は実験すると Girigiri Happy New Year Contest の B と同じ形になることがわかった (というか問題設定含めて全く同じ問題) が、制約がやたら大きいのでどちらにしろ処理できない、放置

順位表を見ると H, I, J がやたら解かれていたので見たら本当に簡単だったので通す (開始 1 時間くらいで通す形になったのでもう少し早い段階で順位表を確認すべき)

D を TAB と rsk0315 が考えていたけど TLE が取れないらしい。自分も考察してみたらもう少し軽そうな別の解法を思いついたのでそっちで書いたら通った、よくよく考えたら数学問で自分が通すのかなり珍しい (この問題でペナルティがかなりついた、提出する際はもっと慎重になるべきなのかもしれないがジャッジが壊れていることもあるのでどうにも難しい)

F を rsk0315 が実装したけど通らないらしい。問題概要を聞いてコーナーになりそうなところをエスパーしながらペアプロすると直る、AC (ペアプロする前に自分が何やってたか思い出せないんだけど、なんか詰まってそうだったら早めにパソコンの方まで行くべきなんですよね、簡単なことのようで難しいんだけど)

A の問題文が不明瞭らしいので全員で読むが不明瞭すぎる。YES, NO の問題なのに YES, NO の条件がよくわからない。とりあえずサンプルに合うように好意的に解釈するとそれっぽいアルゴリズムが生えるので書く、通る (??)

B に戻ったら約 4 時間前にふと思ったことがやっぱりあってそうなことに気づくので書く 通る もったいなさすぎる・・・

残っているのは C, E, G, K だが C は制約が大きすぎ、E, K は問題不明瞭、G は良問なんだけど解けないという感じに

C は確か黄金比が関係していることだけ覚えていて、しかし自分は黄金比を知らないのでチームメイトに聞く rsk0315 が式を書いてくれる (神か?) 実験をすると黄金比を掛けて切り捨てしたものが関係していそうなことに気づくも、制約が大きいので結局どうするんだろうなあと考えていたらコンテストが終了した いろいろ調べたけど結局 C は多倍長使わないと解けないらしい (えぇ・・・)

反省

B 問題の処理が最悪すぎて実質 250 分くらい余計にペナルティを負った。つらすぎる

あと全体的に立ち回りが良くなくて、例えば H, I, J を通すのが遅かったり通すまでのペナルティが多かったりする。もう少し自分がセット全体を見て、優先順位に関して敏感になるべきな気がした、これはかなり反省です

G が解けなかったのは完全に実力不足で、こういう系統は自分が通せるようにならないとダメなやつなのでちゃんとやる (復習しました)

C の黄金比の話をチームメイトにふったのも終盤の話で、もっと早く言うべきだった 多倍長関係がアレだけど早い段階で対処していれば通ったかもしれないなあ・・・。

まあ結論としては自分の立ち回りがひどかったです、チーム連携難しい。A, D, F のアシストができたところが唯一よかった点かな

Educational Codeforces Round 8 F: Bear and Fair Set

問題概要

原文 → Problem - F - Codeforces

 5 の倍数  n と、整数  b, q が与えられるので、以下を全て満たす正の整数集合を構築できるかどうか判定せよ。

  • 素数 n で、値は全て  b 以下で相異なる
  •  \left\{ 0, 1, 2, 3, 4 \right\} の各元  r について、要素を  5 で割ったあまりが  r になるような、集合内の要素の数はちょうど  \frac{n}{5} 個である
  • 以下の  q 個の条件を全て満たす
    • 集合内の  1 から  \mathrm{upto}_i までの整数を全て数えた結果が  \mathrm{quantity}_i である

解説

まず、各条件を  \mathrm{upto}_i の値でソートします。すると、 \left[ 1, b \right] はいくつかの区間に分かれることになり、各区間内で数をいくつ選べば良いかもわかります。

以下のようにグラフを作り、最大フローが  n であるかどうかで判定可能です。

  • source に「余りが  r」を表す頂点をそれぞれつなげ、その頂点集合を  A とする。容量はすべて  \frac{n}{5}
  • sink に、各区間に対応するような頂点をつなげ、その頂点集合を  B とする。容量はその区間内で選ぶべき個数になる。
  •  A に属する頂点と  B に属する頂点との間は、対応する区間内にあまりが  r である要素がいくつあるかに応じて容量を設定してつなげる

f:id:tsutaj:20190126171705j:plain

また、Hall の結婚定理を使っても解くことができます。 A の頂点部分集合  A' 全てに対して、 A' B を結ぶ辺として使用される本数の最小値・最大値を求め、これをそれぞれ  E_{\min}, E_{\max} とします (下限が 0 でないことに注意)。条件を満たすような集合が存在する、つまり適切なマッチングが存在するための必要十分条件は、 E_{\min} \leq \frac{n}{5} \times |A'| \leq E_{max} になります (詳しくは Hall の結婚定理 を調べてください)。この方針でやると  O(2^{K} b) (この問題において  K = 5) で解けます。

ソースコード

以下の実装は普通にフローを流す方の解法です。

// フロー略
const int K = 5;
signed main() {
    int N, B, Q; scanf("%lld%lld%lld", &N, &B, &Q);

    vector< tuple<int, int> > queries;
    for(int i=0; i<Q; i++) {
        int upto, quan; scanf("%lld%lld", &upto, &quan);
        queries.emplace_back(upto, quan);
    }
    queries.emplace_back(B, N);
    sort(queries.begin(), queries.end());

    Flow<int> fl(K + queries.size() + 2);
    int source = K + queries.size(), sink = source + 1;

    // source <-> A
    for(int i=0; i<K; i++) {
        fl.add_edge(source, i, N / K);
    }

    bool ok = true;
    int pre_num = 0, pre_quan = 0;
    for(size_t x=0; x<queries.size(); x++) {
        auto q = queries[x];
        int upto, quan; tie(upto, quan) = q;
        if(pre_quan > quan) ok = false;
        int cap = quan - pre_quan;
        
        vector<int> cnt(K);
        for(int i=pre_num+1; i<=upto; i++) {
            int mod = i % K; cnt[mod]++;
        }

        // A <-> B
        for(int i=0; i<K; i++) {
            fl.add_edge(i, K + x, cnt[i]);
        }
        // B <-> sink
        fl.add_edge(K + x, sink, cap);

        pre_num = upto, pre_quan = quan;
    }

    int res = ok ? fl.max_flow(source, sink) : -1;
    printf("%s\n", res == N ? "fair" : "unfair");
    return 0;
}

Hall の結婚定理を用いた解法は公式の実装がわかりやすいです。

Educational Codeforces Round 8 E: Zbazi in Zeydabad

問題概要

原文 → Problem - E - Codeforces

'.' または 'z' のマスのみからなる  N \times M の盤面が与えられる。この盤面内に存在する「Z 型」の正方形領域がいくつ存在するか求めよ。

Z 型の正方形領域の定義

  • 最も上と最も下の行は全て 'z'
  • 反対角成分は全て 'z'
  • それ以外は 'z' でも '.' でもよい

解説

以下の説明では、座標の上下方向を  x と、左右方向を  y として、 x y 列目の座標を  (x, y) と表しています。

まず、前処理をして以下の値を簡単に得られるようにしておきます。

  •  zl_{ij}: 座標  (i, j) の左に 'z' が何連続しているか
  •  zr_{ij}: 座標  (i, j) の右に 'z' が何連続しているか
  •  zld_{ij}: 座標  (i, j) の左下 (反対角成分に対応) に 'z' が何連続しているか

各座標  (i, j) について、その座標を正方形領域の右上としたときにどれくらいの大きさの Z 型が作れるかを考えます。まず、大きさの最大値は  s = \min(zl_{ij}, zld_{ij}) 以下であることがわかります。あとは距離  s-1 以内に存在する左下の候補を高速に求められれば、この問題が解けたことになります。

では、左下の候補はどのように求めればよいでしょうか?反対角線ごとに独立に処理する、つまりある  A という整数を決めた際に、 i + j = A を満たす座標についてまとめて処理することにします。以下で扱う座標  (i, j) は、全て  i + j = A を満たす (同じ反対角線上に属する) ものとします。

反対角線ごとに、右の列から左の列に向けて平面走査することを考えます。各座標  (i, j) について、その座標を左下として利用するときの、正方形領域の右上の座標としてありえる  y 座標最大  j_{\max} を求めてみましょう。これはすでに「座標の右に 'z' が何連続しているか」を求めていますので、 j_{\max} = j + zr_{ij} - 1 と求められます。また、右上の座標としてありえる  y 座標最小  j_{\min} は明らかに  j です。よって、 j \leq y \leq j + zr_{ij} - 1 の範囲で、座標  (i, j) が左下の座標として用いられる可能性があります。

あとはこれを考慮しつつ SegmentTree などによる高速化を考えます。左下の座標として使用できるときはセグ木に要素を追加しておいて、使用できなくなった場合は削除します。追加してから削除するまでの間に、右上の座標の候補が来る場合があるため、その場合は左下としてありえる候補を区間加算で得ます。

言語化が難しすぎるのでソースコード見てください・・・。

ソースコード

// BIT 略

int lft[3010][3010], rgh[3010][3010], dig[3010][3010];

signed main() {
    int H, W; cin >> H >> W;
    vector<string> vs(H, string(W, '.'));

    for(int i=0; i<H; i++) {
        cin >> vs[i];
    }

    for(int i=H-1; i>=0; i--) {
        for(int j=0; j<W; j++) {
            if(vs[i][j] == '.') lft[i][j] = dig[i][j] = 0;
            else {
                if(j == 0) lft[i][j] = 1;
                else lft[i][j] = lft[i][j-1] + 1;

                if(i == H-1 or j == 0) dig[i][j] = 1;
                else dig[i][j] = dig[i+1][j-1] + 1;
            }
        }
        for(int j=W-1; j>=0; j--) {
            if(vs[i][j] == 'z') rgh[i][j] = (j == W-1) ? 1 : rgh[i][j+1] + 1;
        }
    }

    int ans = 0;
    for(int A=0; A<=H+W; A++) {
        BIT<int> bit(H+W);

        vector< tuple<int, int, int> > tups;
        for(int x=0; x<H; x++) {
            int y = A - x;
            if(y < 0 or y >= W) continue;

            tups.emplace_back(-(y + rgh[x][y] - 1), 0, x);
            tups.emplace_back(- y                 , 1, x);
            tups.emplace_back(- y                 , 2, x);
        }

        sort(tups.begin(), tups.end());
        for(auto e : tups) {
            int x = get<2>(e), y = A - x, query = get<1>(e);
            if(query == 0) bit.add(x+1,  1);
            if(query == 1) ans += bit.sum(x+min(dig[x][y], lft[x][y])) - bit.sum(x);
            if(query == 2) bit.add(x+1, -1);
        }
    }
    cout << ans << endl;
    return 0;
}