four-t practice 2019 #02

2019 年 2 月 23 日 (土) に 2017 Beijing Regional を vjudge で解いたのでその時の立ち回りのメモです

メモ

開始。前回の反省を踏まえて、自分は後ろの問題から目を通していき、rsk0315 が前から目を通していき、TAB が A に目を通すことにした。A 問題が文字列なので rsk0315 に早速パス、TAB が代わりに前からざっと見る。題意の把握までちゃんとやろうとなるとそれなりに時間がかかる・・・。G が幾何なので TAB に投げつつ、問題をざっと見ていく。見た結果 E, F が簡単そうということになったのでそこからとりかかる。通る。H と J が解けそうだけどすぐにはやりかたがわからない。

前半に実装がやばそうな問題がいくつかあったらしく、それを rsk0315 が考えることに。自分は後ろの方の考察を、TAB は G の考察をやっていた。E, F を通してから次の提出に 2 時間近く要しているが考察したり実装したりがそれなりにあったのでこれは仕方ない気がする。前回の反省を活かして考察中でも画面はちょこちょこ確認するようにした (TAB が実装していた G のデバッグを手伝うなどした)

G が通り、それからしばらくして実装ゲーの D も通る。幾何と実装がちゃんと通ってすごい、チームメイトがつよつよで助かりますね (tsutaj 何もしてなくない？)

H, J は解法自体は思いつくけど時間制限的に厳しそうという感じ。大きいケースは多くないそうなのでこれでもいけるんちゃうか？みたいな感じで J を書いたら通って草 ( でも が通る場合があるぞい)

あと I の解法っぽいものも思いついたので TLE に気をつけながら書いたら通った。

この時点で残り 1 時間。これまた実装ゲーっぽい A 問題を rsk0315 が Python で華麗に通す (すごい) あと H も実はこれで間に合うんちゃうか？みたいな感じで書いたら通って草 ( でも が通る場合があるぞい)

終わってみると 8 完でそこそこ解けた (やばそうな計算量の提出が 2 問通っているので微妙だが)。でも C の Mo っぽい問題できなかったのはアレだし、B も知識が足りなかった。今回のセットは変な問題はなかったしちゃんと復習したいですね・・・。

反省

今回は問題概要を 2 人がかりで両側探索したけど、簡単枠が真ん中に存在したせいで発見が遅れた (おいおい) これどうすればいいんですかね・・・。もうすこし雑な問題概要の把握でもいいのかもしれないけど、誤読したらヤバいし怖いですね。

解ける問題を落としたり後回しにしたりとかは特になかった気がする。これ以上スピードをあげるには単純に実力が必要

誰がどの問題を担当するかも割と理想的に回った気がして、幾何は TAB に・文字列とか実装とかを rsk0315 に投げて自分はよくわからない DP とかそのへんをやるのが定着しつつある。ただ分業するのはいいんだけど一緒に考察する練習とかももっとやりたいなあと思う

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

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

• 要素数は で、値は全て 以下で相異なる
• の各元 について、要素を で割ったあまりが になるような、集合内の要素の数はちょうど 個である
• 以下の 個の条件を全て満たす
  • 集合内の から までの整数を全て数えた結果が である

解説

まず、各条件を の値でソートします。すると、 はいくつかの区間に分かれることになり、各区間内で数をいくつ選べば良いかもわかります。

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

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

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

ソースコード

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

// フロー略
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 の結婚定理を用いた解法は公式の実装がわかりやすいです。